Я решаю задачу из 8 головоломок, в которой мне нужно расположить плитки в правильном порядке с наименьшей стоимостью пути. для моей эвристики я объединил количество неуместных плиток + расстояние в n плиток до целевой позиции.
цель
1 2 3
8 0 4
7 6 5
для такой головоломки
1 2 3
7 8 4
6 0 5
он отлично работает
но с этой конфигурацией
1 3 4
8 0 2
7 6 5
он бесконечно выбирает эту комбинацию как самую короткую
1)
1 0 4
8 3 2
7 6 5
2)
1 3 4
8 0 2
7 6 5
затем 1) затем 2)
Если вы посмотрите псевдокод алгоритма в wikipedia, вы заметите вещь, которую они назвали closedSet. Это коллекция, в которой вы можете хранить состояния, которые уже были развернуты (состояния, для которых были созданы преемники). Затем цикл по всем преемникам (или соседям в псевдокоде) начинается с этого:
if neighbor in closedSet
continue // Ignore the neighbor which is already evaluated.
Цель этого фрагмента кода - предотвратить возникновение именно вашей проблемы.
Обратите внимание, что ваш выбор структуры данных для closedSet существенно повлияет на время выполнения вашего алгоритма. Это не должно быть что-то вроде списка, где проверка того, есть ли уже объект в нем, требует перебора всего списка. Вместо этого вы захотите посмотреть что-то вроде хеш-карты / набора (точная терминология зависит от вашего выбора языка программирования).
