* Алгоритм поиска застревает

Question

Я пытаюсь реализовать алгоритм поиска A *. Сейчас я просто пытаюсь найти хороший путь в окружении стен. Стены генерируются случайным образом, и в некоторых случаях мой путь застревает. Если поиск сталкивается со стеной перед ним и со всех сторон (кроме той, которая привела его в этот беспорядок), он останавливается. Что я могу сделать, чтобы предотвратить это? Я использую систему баллов «по прямой линии» для моего значения H, которая игнорирует стены и просто оценивает, как много потребуется, чтобы добраться до пункта назначения. Это иногда приводит его в эту ловушку.

Спасибо.

Answer 1

Недооценка расстояния является «правильной» для A *.

Но, похоже, у вас проблема с глубиной / шириной.

При оценке опций с заданной позиции вы должны добавить их в список опций, чтобы проверить и отсортировать их по баллам. Не должно быть никаких причин, по которым вы бы проверяли опции, доступные в данной позиции, сразу после того, как вы оценили эту позицию - то есть все опции из каждой позиции должны попасть в один и тот же список. Таким образом, когда вы попадаете в тупик, он просто не генерирует дополнительные параметры, и вы продолжаете, беря следующий наиболее высоко оцененный вариант из списка и оценивая его.

Answer 2

Думая о пространстве состояний как направленный ациклический граф, если A * встречает конечный узел, который не является терминальным узлом, это не должно быть проблемой, так как этот узел просто будет уже перемещен в закрытый список .

Если ваша реализация A * немедленно останавливается после обнаружения нетерминального (целевого) конечного узла, и в открытом списке все еще есть другие узлы, тогда ваша реализация A * неверна.

Answer 3

Если это зашло в тупик, это не должно быть проблемой. Ваш алгоритм A * должен просто найти следующий неблокированный узел с наименьшей эвристикой и начать все сначала.