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

Question

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

Спасибо.

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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