Sign in or Join FriendFeed
FriendFeed is the easiest way to share online. Learn more »
Vyacheslav Matyukhin
https://github.com/berekuk... - набросал по мотивам ai-class'а решатель пятнашек с помощью A*-поиска.
Perl 5.14, Moose. Работает, но медленно. Для 3*3 решает за разумное время, для 4*4 приходится указывать вес (http://en.wikipedia.org/wiki...) и ограничиваться неоптимальным решением, иначе фронтир дорастает до 500к объектов (дальше ждать не стал, чтобы не повесить комп по памяти). - Vyacheslav Matyukhin
Больше всего по производительности все упиралось в выбор следующего пути, потому что в список фронтиров надо уметь быстро добавлять новый в произвольное место, а выбирать минимальный по цене. Только сейчас дошло, что это какое-нибудь B-дерево нужно, но поскольку в перле я такой структуры не знаю, то в итоге разложил фронтиры по bucket'ам, благо множество возможных значений цены небольшое. - Vyacheslav Matyukhin