Ранний останов Алгоритма Звезды для недостижимой цели в бесконечной сетке

Question

Я следую псевдокоду в Википедии, чтобы реализовать алгоритм * с приоритетной очередью, чтобы найти кратчайший путь от одного источника к другому месту назначения в бесконечной большой сетке .Проблема возникла, когда цель недостижима, например, окружен стенами (без бесконечных длинных стен) , алгоритм не остановится, поэтому он попадает в бесконечный цикл .Моя интуитивно понятная мысль о решении - выполнить некоторую предварительную обработку, такую ​​как добавление границ на основе источника и места назначения, или проверить, окружен ли пункт назначения (это будет непросто) перед поиском.Какие-нибудь предложения для недостижимой ранней остановки?Спасибо.

Answer 1

Пока у вас нет бесконечных стен, вы можете запустить A * от источника до пункта назначения и одновременно запустить A * от пункта назначения до источника.

Если пункт назначения окружен стенами, то в конечном итоге у пункта назначения -> источника A * не останется опций.

Если источник окружен стенами, то, в конечном счете, источник-> пункт назначенияУ * закончатся варианты.

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

Answer 2

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

Как уже говорилось, проблема, похоже, не имеет простого решения.Возможно, вы сможете сделать больше, если сможете предоставить дополнительную информацию о вашей настройке.Например, если все стены представляют собой отрезки, то вы можете использовать алгоритмы вычислительной геометрии (сметание угла?), Чтобы увидеть, окружена ли точка стенами.