Я смотрел на то , что делали парни в AI Mario Competition , и некоторые из них построили довольно симпатичных ботов Mario, используя алгоритм A * (A-Star) Pathing.
( Видео Марио A * Bot In Action )
Мой вопрос, как A-Star сравнивается с Dijkstra? Глядя на них, они кажутся похожими.
Зачем кому-то использовать один над другим? Особенно в контексте путей в играх?
Ответы:
Дейкстра является частным случаем для A * (когда эвристика равна нулю).
источник
Дейкстр:
Он имеет одну функцию стоимости, которая представляет реальную стоимость затрат от источника к каждому узлу:
f(x)=g(x)
.Он находит кратчайший путь от источника к каждому другому узлу, учитывая только реальную стоимость.
Поиск:
Имеет две функции стоимости.
g(x)
: так же, как Дейкстра. Реальная стоимость достижения узлаx
.h(x)
: приблизительная стоимость от узлаx
к узлу цели. Это эвристическая функция. Эта эвристическая функция никогда не должна переоценивать стоимость. Это означает, что реальная стоимость достижения узла цели из узлаx
должна быть больше или равнаh(x)
. Это называется допустимым эвристическим.Общая стоимость каждого узла рассчитывается по
f(x)=g(x)+h(x)
* Поиск только расширяет узел, если он кажется многообещающим. Он фокусируется только на достижении целевого узла с текущего узла, а не на всех остальных узлах. Оптимально, если допустима эвристическая функция.
Поэтому, если ваша эвристическая функция хороша для приближения будущей стоимости, вам нужно будет исследовать намного меньше узлов, чем Дейкстра.
источник
То, что сказал предыдущий автор, плюс к тому, что у Дейкстры нет эвристики, и на каждом шаге она выбирает ребра с наименьшими затратами, что имеет тенденцию «покрывать» больше вашего графика. Из-за этого Dijkstra может быть более полезным, чем A *. Хорошим примером является случай, когда у вас есть несколько целевых узлов-кандидатов, но вы не знаете, какой из них является ближайшим (в случае A * вам придется запускать его несколько раз: один раз для каждого узла-кандидата).
источник
Алгоритм Дейкстры никогда не будет использоваться для поиска пути. Использование A * не представляет никакой сложности, если вы можете придумать приличную эвристику (обычно легко для игр, особенно в 2D-мирах). В зависимости от пространства поиска, итеративное углубление A * иногда предпочтительнее, поскольку оно использует меньше памяти.
источник
Дейкстра - особый случай для А *.
Дейкстра находит минимальные затраты от стартового узла до всех остальных. A * находит минимальную стоимость от начального узла до целевого узла.
Алгоритм Дейкстры никогда не будет использоваться для поиска пути. Используя A *, можно придумать приличную эвристику. В зависимости от пространства поиска предпочтительным является итеративный A *, поскольку он использует меньше памяти.
Код для алгоритма Дейкстры:
Код для алгоритма A *:
источник
Дейкстра находит минимальные затраты от стартового узла до всех остальных. A * находит минимальную стоимость от начального узла до целевого узла.
Поэтому может показаться, что Dijkstra будет менее эффективным, когда все, что вам нужно, это минимальное расстояние от одного узла до другого.
источник
Вы можете считать A * управляемой версией Dijkstra. То есть вместо изучения всех узлов вы будете использовать эвристику для выбора направления.
Говоря более конкретно, если вы реализуете алгоритмы с приоритетной очередью, то приоритет посещаемого узла будет зависеть от стоимости (стоимость предыдущих узлов + стоимость, чтобы добраться сюда) и эвристической оценки отсюда к цели. Находясь в Дейкстре, приоритет зависит только от фактической стоимости узлов. В любом случае, критерий остановки достигает цели.
источник
Алгоритм Дейкстры определенно находит кратчайший путь. С другой стороны, A * зависит от эвристики. По этой причине A * быстрее алгоритма Дейкстры и даст хорошие результаты, если у вас хорошая эвристика.
источник
Если вы посмотрите на psuedocode для Astar :
Принимая во внимание, если вы посмотрите на то же самое для Дейкстры :
Итак, суть в том, что Astar не будет оценивать узел более одного раза,
так как считает, что достаточно посмотреть на узел один раз из-
за его эвристики.
OTOH, алгоритм Дейкстры не стесняется исправлять себя, в случае,
если узел снова появляется.
Что должно сделать Астар быстрее и более подходящим для поиска пути.
источник
В A * для каждого узла вы проверяете исходящие соединения на свои.
Для каждого нового узла вы рассчитываете наименьшую стоимость (csf) на данный момент в зависимости от веса соединений с этим узлом и затрат, которые вы должны были достичь на предыдущем узле.
Кроме того, вы оцениваете стоимость от нового узла до целевого узла и добавляете это к csf. Теперь у вас есть приблизительная общая стоимость (и т. Д.). (и т. д. = csf + предполагаемое расстояние до цели) Затем вы выбираете из новых узлов тот, который имеет самый низкий уровень и т. д.
Делайте то же самое, что и раньше, пока один из новых узлов не станет целью.
Дейкстра работает почти так же. За исключением того, что предполагаемое расстояние до цели всегда равно 0, и алгоритм сначала останавливается, когда целью является не только один из новых узлов , но и узел с самым низким значением csf.
A * обычно быстрее, чем dijstra, хотя это не всегда так. В видеоиграх вы часто предпочитаете подход «достаточно близко для игры». Поэтому обычно достаточно «близкого» оптимального пути из A *.
источник
Алгоритм Дейкстры определенно завершен и оптимален, так что вы всегда найдете кратчайший путь. Однако это, как правило, занимает больше времени, поскольку используется в основном для обнаружения нескольких целевых узлов.
A* search
с другой стороны, это касается эвристических ценностей, которые вы можете определить, чтобы достичь своей цели ближе, например, манхэттенского расстояния до цели. Он может быть либо оптимальным, либо полным, что зависит от эвристических факторов. это определенно быстрее, если у вас есть один целевой узел.источник