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

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

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

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

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

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


java algorithm path-finding a-star gridworld
person Lewis    schedule 29.12.2010    source источник
comment
Это вопрос с субъективным ответом. Правильно ли это сделать? В некоторых случаях это так, а в некоторых нет. Зависит от ограничений проекта. Нужно ли искать путь? Если да, возникают ли у вас ситуации, подобные описанным выше, и сможете ли вы решить их, сказав, что пути нет? Если да, то нужно какое-то ограничение. Если нет, то нет :).   -  person bastijn    schedule 29.12.2010
comment
Пользователь может упорядочить среду так, как ему нравится, так что да, я должен уметь справляться с плохими путями. Поиск пути с обеих сторон одновременно кажется / я был убежден, что это, вероятно, лучший способ сделать это, хотя мне, возможно, придется немного реорганизовать свой код, чтобы заставить его работать. Ну хорошо :D   -  person Lewis    schedule 29.12.2010

Ответы (4)


arrow_upward
2
arrow_downward

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

person Gabi Purcaru    schedule 29.12.2010
comment
Проблема в том, что он не может быть немедленно окружен. Это может быть 10, 20, 50 узлов во всевозможных странных формах. - person Lewis; 29.12.2010
comment
@Lewis В этом случае сделайте A * как с начала, так и с конца, и остановитесь, когда у вас будет место встречи или когда очередь пуста (в этом случае одно из них заключено). Обратите внимание, что если вы это сделаете то, что вы предложили, может быть действительный путь за пределами вашей области, поэтому вы можете пропустить действительные пути - person Gabi Purcaru; 29.12.2010
comment
Да, вы, конечно, правы, и, глядя на этот метод снова, кажется, что он, вероятно, будет более эффективным, чем то, что я предложил в вопросе. Но, просто для удовольствия, будет ли работать метод окружения прямоугольной стеной? - person Lewis; 29.12.2010
comment
@Lewis, это сработает примерно в 99% случаев, если у вас достаточно большая окружающая стена (по крайней мере, IMO) - person Gabi Purcaru; 29.12.2010
comment
Звучит отлично. Тогда я воспользуюсь вашим методом, так как он лучше. Спасибо! - person Lewis; 29.12.2010

arrow_upward
1
arrow_downward

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

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

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

person bastijn    schedule 29.12.2010
comment
Это хорошее решение, особенно если я хочу, чтобы пользователь мог видеть статистику во время работы алгоритма. A * требует, чтобы конечный узел был известен (в противном случае потребуется что-то вроде алгоритма Дейкстры), поэтому, к счастью, у меня есть доступ к конечному узлу. - person Lewis; 29.12.2010
comment
И это правда, я давно не пользовался A* :). - person bastijn; 29.12.2010

arrow_upward
0
arrow_downward

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

  1. Запустить алгоритм для n итераций, начиная с A, ища B.
  2. Запустите алгоритм для n итераций, начиная с B, ища A.

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

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

person Mizipzor    schedule 31.01.2012

arrow_upward
0
arrow_downward

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

person Tom Whittock    schedule 31.01.2012