Я читал в одной из моих книг по ИИ, что популярные алгоритмы (A-Star, Dijkstra) для поиска путей в симуляции или играх также используются для решения известной "15-головоломки".
Может ли кто-нибудь дать мне несколько указателей на то, как я уменьшу 15-головоломку до графика узлов и ребер, чтобы применить один из этих алгоритмов?
Если бы я рассматривал каждый node в графике как состояние игры, то не могло бы ли это дерево стать достаточно большим? Или это просто способ сделать это?
Хорошая эвристика для A-Star с 15 головоломками - это количество квадратов, которые находятся в неправильном месте. Поскольку вам нужно по крайней мере 1 перемещение за квадрат, что неуместно, количество квадратов на месте гарантировано будет меньше или равно количеству ходов, необходимых для решения головоломки, что делает его подходящей эвристикой для A-Star.
Быстрый поиск в Google включает пару статей, которые подробно описывают это: один на Параллельный комбинаторный поиск, а один на Поиск по карте памяти с внешней памятью
Общее эмпирическое правило, когда дело доходит до алгоритмических проблем: кто-то, вероятно, сделал это перед вами, и опубликовал свои выводы.
Это задание для проблемы с 8-головоломкой, в которой подробно обсуждалось использование алгоритма A *, но также довольно просто:
http://www.cs.princeton.edu/courses/archive/spring09/cos226/assignments/8puzzle.html
Теоретико-теоретический способ решения проблемы состоит в том, чтобы представить каждую конфигурацию платы как вершину графа, а затем использовать первый поиск с обрезкой на основе чего-то вроде Манхэттенского расстояния доски для получения кратчайшего пути от начальной конфигурации до решения.
Одна из проблем с этим подходом заключается в том, что для любой платы n x n, где n > 3 игровое пространство становится настолько большим, что неясно, как вы можете эффективно отмечать посещенные вершины. Другими словами, нет очевидного способа оценить, совпадает ли текущая конфигурация платы с той, которая ранее была обнаружена путем прохождения другого пути. Другая проблема заключается в том, что размер графа растет так быстро с помощью n (примерно примерно (n^2)!), что он просто не подходит для атаки brue-force, поскольку количество путей становится вычислительно неосуществимым для прохождения.
Настоящая статья Ian Parberry Алгоритм реального времени для (n^2 − 1) - Головоломка описывает простой жадный алгоритм, который итеративно приходит к решению завершая первую строку, затем первый столбец, затем вторую строку... Он приходит к решению почти сразу, однако решение далеко не оптимально; по сути, он решает проблему так, как человек мог бы без использования вычислительной мускулатуры.
Эта проблема тесно связана с проблемой решения кубика Рубика. График всей игры утверждает, что он слишком велик, чтобы решить силу brue, но существует довольно простой 7-ступенчатый метод, который может быть использован для решения любого куба примерно за 1 ~ 2 минуты от обычного человека. Этот путь, конечно, неоптимальный. Обучая распознавать шаблоны, определяющие последовательности движений, скорость может быть уменьшена до 17 секунд. Однако этот подвиг Джири несколько сверхчеловек!
Метод Parberry описывает перемещение только одной плитки за раз; можно предположить, что алгоритм может быть улучшен за счет использования ловкости Jiri и одновременного перемещения нескольких фрагментов. Это не привело бы к тому, что, как утверждает Парберри, уменьшить длину пути от n^3, но это снизит коэффициент для первого члена.
Помните, что A * будет искать через проблемное пространство, идущее вниз по наиболее вероятному пути к цели, как определено вашим heurestic.
Только в худшем случае это приведет к заполнению всего проблемного пространства, это имеет тенденцию происходить, когда нет реального решения вашей проблемы.
Просто используйте дерево игры. Помните, что дерево является специальной формой графика.
В вашем случае листья каждого node будут игрой после того, как вы сделаете один из ходов, доступных в текущем node.
Здесь вы идете http://www.heyes-jones.com/astar.html
Кроме того. помните, что по алгоритму A-Star, по крайней мере, вам нужно будет выяснить допустимую эвристику, чтобы определить, приближается ли следующий следующий шаг к завершенному маршруту, чем другой шаг.