15 Эвристическая головоломка

Question

15 Puzzle - это классическая задача для моделирования алгоритмов, связанных с эвристикой. Обычно используемая эвристика для этой задачи включает подсчет количества неуместных плиток и определение суммы манхэттенских расстояний между каждым блоком и его положением в конфигурации цели. Обратите внимание, что оба допустимы, то есть они никогда не переоценивают количество оставленных ходов, что обеспечивает оптимальность для некоторых алгоритмов поиска, таких как A *.

• То, что Heuristic вы считаете правильным, A*, кажется, работает хорошо, у вас есть пример, может быть, в c или java?

Answer 1

Эвристический

Мой эвристический выбор заключается в том, чтобы найти, является ли сумма всех инверсий в перестановке нечетной или четной - если она четная, то 15-головоломка разрешима.

Число инверсий в перестановке равно числу ее обратных перестановок (Skiena 1990, p. 29; Knuth 1998).

Только если я знаю, что это можно решить, имеет смысл решать это. Задача состоит в том, чтобы уменьшить количество обратных и решаемых задач. Чтобы найти решение должно быть не более 80 ходов.

Еще больше помощи

Уравнение для перестановки:

Факториалы в диапазоне от 0 до 16: {1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000}. Если вам нужно больше из них, поиск WolframAlpha для Range [1,20]!

Если вы хотите узнать больше об этом, прочитайте: 15Puzzle .

Answer 2

Пятнадцать реализаций головоломки на C ++ с использованием A * algorihtm https://gist.github.com/sunloverz/7338003