Почему мой алгоритм a-star расширяет слишком много узлов, несмотря на правильную эвристику?

Question

Я выполняю задание, в котором мне нужно использовать звездочку, чтобы решить головоломку 15 (в C).

Эвристическая функция: Манхэттенское расстояние (так называемое расстояние такси).

Нам дан пример ввода / вывода, где плата решается в 22 * ​​1014 * движениях и после расширения 395 узлов (состояний платы) (т.е. мы должны были смотреть на потомков 395 узлов)

Под «правильной» эвристикой я подразумеваю, что моя функция такая же, как и функция, используемая для получения выходных данных выборки, и выдает правильное расстояние.

Проблема в мое решение расширяет более 400 узлов , чтобы найти решение ( это оптимально 22 хода, но другой ).

Я заметил, что число меняется в зависимости от порядка, в котором я генерирую дочерние узлы (переместить плитку пространства вверх, влево, вниз, вправо или в других направлениях).

Существует 24 способа переместить космическую плитку вверх, вниз, влево и вправо для генерации дочерних элементов, и я попробовал все из них, но ни один из них не расширил 395 узлов.

Почему это происходит?

Терминология:

• узел: каждый узел представляет собой конфигурацию доски из 15 головоломок
• children: конфигурации, которые вы можете достичь, перемещая пространство плитка вверх, вниз, влево или вправо от текущего узла

PS: я использую двоичную кучу для открытого списка, если это имеет значение

Спасибо

Answer 1

Ммм ... В идеальном случае A * не зависит от порядка, в котором вы производите детей.К сожалению, если в «очереди» два или более узлов с одинаковым эвристическим значением distance-plus-cost , алгоритм может выбрать «случайно» один из этих узлов и найти другое решение (и исследовать другой путь поиска).

Я думаю, что вы можете попробовать:

• Проверьте эвристическую функцию "расстояние плюс стоимость".(стоимость каждого действия 1? Вы правильно суммируете расстояние каждого квадрата от их правильного положения?)
• Проверьте свою кучу.Это возвращает правильные узлы?Сколько узлов с одинаковым эвристическим значением вы можете иметь на одном шаге?

Это единственное, что я могу вам сказать с этой информацией.:)