Было бы приемлемо разместить границы вокруг моей области поиска пути?

Question

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

Возможное решение этой проблемы - разместить невидимые (как пользователь их не видит, но алгоритм видит) стены вокругвсю область поиска пути, убедившись, что начальный узел, конечный узел и все узлы стены находятся внутри этих стен, с заполнением 2-3 пробелами или около того.Что-то вроде:

_________________________________
|                               |
|              S  |             |
|            _____|   _____     |
|                     | E |     |
|                     |___|     |
|_______________________________|

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

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

Answer 1

Разве вы не знаете точно, где находится конечный узел?Если вы это сделаете, просто проверьте, окружен ли он, прежде чем выполнять ваш алгоритм.

Answer 2

Смотрите также мой комментарий на ваш вопрос.После ввода я придумал, что может быть хорошим решением.Это для случая, когда вы не знаете свой конечный узел и ничего не можете сделать с позицией вашего конечного узла, как предложено выше.

Вы также можете сделать что-то вроде: «Я нашел закрытое поле вмое поле и никакой путь после x времени, поэтому с y% вероятностью я могу сказать, что пути нет, и обновите y% , чтобы увеличить со временем, ноникогда не достигнет 100%.

Может быть хорошим решением, которое находится в середине ограничения области поиска и ничего не делает.

Answer 3

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

Answer 4

У меня была похожая проблема, и вот что я сделал:

1. Алгоритм запуска для n итераций, начиная с A, для поиска B.
2. Алгоритм запуска для n итераций, начиная с B в поисках A.

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

Хитрость здесь, конечно, в том, чтобы найти хорошее значение для n . Я сделал несколько проходов с увеличением n и кэшировал результаты (мой график не сильно изменился).