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

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

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

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

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

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

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

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

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

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

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

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

Спасибо


artificial-intelligence algorithm path-finding a-star graph-algorithm
person Babak    schedule 22.10.2011    source источник
comment
@duffymo не ИИ, просто вычисления II   -  person Babak    schedule 22.10.2011
comment
Разница может заключаться просто в том, что в их примере решения используется немного более умная эвристика (например, заглядывание вперед для более быстрого определения тупиков). Пока различия в расширенных узлах так малы, как они звучат в вашем описании (насколько больше 400?) и решение по-прежнему оптимально, я бы не стал слишком беспокоиться об этом.   -  person    schedule 22.10.2011
comment
@delnan Я уверен, что это не оптимизировано, и это просто манхэттенское расстояние. Одним из требований является то, что программа должна расширять такое же количество узлов, и говорят, что если это не так, то это неправильно. Вот почему я беспокоюсь об этом. Изменяя направление генерации потомков, я мог получить от 420 до 670 иш.   -  person Babak    schedule 22.10.2011
comment
@delnan извините, я исправляюсь. НЕ сказано, что они должны быть одинаковыми.   -  person Babak    schedule 22.10.2011

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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

person Davide Aversa    schedule 24.10.2011