Обрезка болота / тупика на картах без сетки
Существуют ли какие-либо алгоритмы для нахождения и предотвращения проблемных областей ( болота, тупики) при поиске пути при использовании не сеточных карт? Существует множество доступных сеток, которые либо избегают этих областей, либо псевдо-избегают этих областей с помощью рекурсии точек перехода и т. Д., Но мне еще предстоит найти что-нибудь полезное для квадродеревьев, навигационных сеток или других неоднородных карт.
2 ответа
Обнаружение тупика и Болота не зависят от сетки. Они просто оцениваются на сеточных картах.
Такая вещь, вероятно, существует - сотни статей о поиске путей и планировании движения публикуются каждый год, но я думаю, что вам нужно задать себе более серьезный вопрос - зачем вам это делать?
Идея перехода к представлению навигационной сетки или разреженной сетки состоит в том, чтобы сократить время, необходимое для поиска решения, путем уменьшения числа узлов в графе. Если ваш поиск слишком медленный, просто обрежьте количество узлов и ребер в вашем графике. Удаляя любые тупики из поиска в автономном режиме еще до того, как вы начнете, вы уменьшите накладные расходы на каждый поиск.
Если даже после того, как вы сократили график, поиск все еще идет медленно, и вы можете допустить приблизительные решения проблем поиска, рассмотрите возможность использования взвешенного A*, где вы перепланируете уменьшение коэффициента инфляции, пока не получите оптимальную стоимость.
Алгоритмы планирования полны компромиссов, просто убедитесь, что вы понимаете плюсы и минусы того, что вы решите делать.
И последнее замечание: убедитесь, что вы правильно реализовали примитивы в планировщике, который вы используете - алгоритмы, такие как A*, зависят от правильной реализации очередей приоритетов, в частности, убедитесь, что ключ уменьшения равен O(log n) или лучше.