A * лучший алгоритм поиска пути?

Question

Обычно говорят, что A * - лучший алгоритм для решения задач поиска пути.

Есть ли ситуации, когда A * является не лучшим алгоритмом для поиска решения?

Насколько хорош * по сравнению с BFS, DFS, UCS и т. Д.?

Answer 1

Короткий ответ - да, есть ситуации, в которых A * не лучший алгоритм для решения проблемы.Однако существует несколько способов оценить, что составляет алгоритм best для поиска решения.

Если вы рассматриваете best с точки зрения производительности множественного поиска из одного источника по многим адресатам , то вам следует рассмотреть возможность использования более подходящего подхода (* Алгоритм Дейкстры ).

Если вы рассматриваете best с точки зрения производительности , то в некоторых особых случаях DFS и BFS будут значительно превосходить A *.Исходя из прошлого опыта, это происходит для очень маленьких, почти тривиальных графов, но для более сильного утверждения потребуется тщательное тестирование и профилирование.

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

Если вы рассматриваете best вВ терминах полнота , то есть будет ли алгоритм всегда находить путь к цели, если такой путь существует.Если это так, то A * эквивалентен любому другому полному алгоритму (например, поиск в ширину).

Если вы рассматриваете best в случаях, когда некоторые из веса на графике отрицательны , тогда вам нужно будет использовать специальный алгоритм для решения этих проблем (например, bellman-ford )

Если вы считаете лучшим в случаях, когда эвристика недоступна , тогда вы должны вернуться к h(x,y)=0 forall states x and y.В этом случае A * эквивалентен лучшему первому поиску.

Если вы рассматриваете best в случаях, связанных с планированием движения в непрерывных конфигурационных пространствах , тогда A * можетработать адекватно в низких измерениях, но хранение графа поиска начинает становиться нецелесообразным при больших измерениях, и необходимость использования вероятностно полных алгоритмов возрастает (например, RRT , Bi-RRT, RDT)

Если вы рассматриваете лучший в тех случаях, когда график является частично наблюдаемым , вы знаете только подмножество всех возможных вершин и ребер в графе в любое время, и вам нужночтобы изменить состояние, чтобы наблюдать больше графика, вам нужен альтернативный алгоритм, разработанный для этого (например, Keonig's Lifelong Planning A *, LPA *, делает именно это).

Если вы рассматриваете лучший в тех случаях, когда график меняется со временем , что часто встречается в робототехнике, когда вы включаете движущееся препятствиеs, тогда вам нужен алгоритм, который предназначен для этого (например, D * Стента или D * -Lite Кенига и Лихачева).

Answer 2

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

Кроме того, его часто легко ускорить.Например, если вы умножаете допустимую эвристику на константу c, вы можете гарантировать, что стоимость результирующей последовательности узлов не более чем в c раза превосходит оптимальный результат.

Например, возьмите потрясающая статья Иана Дэвиса (написана для Star Trek Armada).* Используется с иерархическим набором путевых точек, что приводит к грубому пути.Затем, чтобы сгладить путь, они снова запускают A * на новом сгенерированном графе, содержащем узлы на пути и те, которые находятся поблизости, чтобы получить более разумный путь.Наконец, они используют резиновые ленты для удаления избыточных узлов.

Итак, A * - это не решение для всего, но это очень универсальный инструмент.

Answer 3

Чрезвычайно простая альтернатива (без споров с эвристикой) - Совместная диффузия .Он отлично работает, когда вам нужно нацелиться на одну цель или любого члена группы, без разбора , и в этом случае может быть быстреечем A *.Она имитирует игру «Ты становишься теплее / холоднее».

Совместная диффузия создает одну тепловую карту на «группу», на которую вы хотите нацелиться ... если вы хотите отслеживать конкретную цель, относитесь к ней как к своейсгруппировать, создав тепловую карту только для этой цели;Доменом Collaborative Diffusion являются такие игры, как футбол (где обе команды агентов отслеживают мяч и стойку ворот, в частности, всего 3 карты влияния), или Pacman (аналогичные, несколько агентов отслеживают Pac), или армейские игры, в которых есть одна комбинированная тепловая карта, представляющая тело (совокупность) каждой армии, как определено каждым агентом в этой армии, так что одна армия может приближаться к «другой армии», а не к «конкретным подразделениям в другой армии».Эта общность может позволить повысить производительность.

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

Лучше всего подходит, когда карты достаточно плотно заполнены множеством движущихся единиц, что оправдывает обширную диффузию, которая должна происходить по всему пространству поиска при каждом обновлении.Ясно, что хорошо настроенный подход A * может быть на порядок дешевле в большой разреженной карте, где у нас есть только одна единица, нацеленная только на одну другую единицу, потому что с A * в этом случае вы работаете только над дробьютайлов карты между искателем и целью;в то время как с Collaborative Diffusion вы вместо этого распространяетесь по всей карте, просто чтобы сделать то же самое, что делает ее гораздо более дорогостоящей.

Answer 4

Я вижу вопрос старый, но, возможно, это практическое решение будет кому-то полезно.Недавно я обнаружил очень хороший открытый исходный код, написанный на python

код содержит следующие алгоритмы поиска пути:

• A *
• Dijkstra
• Best-First
• Двунаправленный A *
• Поиск в ширину (BFS)
• Итеративное углубление A * (IDA *)

Изменение размера и значений матрицы позволяет почувствовать разницу между различными алгоритмами поиска пути.Как упоминается в Википедии : «A * завершена и всегда найдет решение, если оно существует»