Является ли A * лучшим алгоритмом поиска пути?

Ответ 1

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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