Как сравниваются алгоритм Дейкстры и A-Star?

154

Я смотрел на то , что делали парни в AI Mario Competition , и некоторые из них построили довольно симпатичных ботов Mario, используя алгоритм A * (A-Star) Pathing.

альтернативный текст
( Видео Марио A * Bot In Action )

Мой вопрос, как A-Star сравнивается с Dijkstra? Глядя на них, они кажутся похожими.

Зачем кому-то использовать один над другим? Особенно в контексте путей в играх?

KingNestor
источник
47
xkcd.com/342
SLaks
@SLaks A * использует больше памяти, чем dijkstra? Как получилось, если узлы обещают только путь, а dijkstra пробует их все?
Poutrathor

Ответы:

177

Дейкстра является частным случаем для A * (когда эвристика равна нулю).

leiz
источник
1
В dijkstra мы рассматриваем только расстояние от источника, верно? А минимальная вершина учитывается?
Кракен
4
Я думал, что A * - особый случай для Дейкстры, где они используют эвристику. Так как Дейкстра был там первым афаиком.
Madmenyo
46
@MennoGouw: Да, алгоритм Дейкстры был разработан первым; но это частный случай более общего алгоритма A *. Совсем нет ничего необычного (на самом деле, вероятно, норма), когда специальные случаи сначала обнаруживаются, а затем обобщаются.
Питер Гиркенс,
1
Отличный ответ для всех, кто знает эвристику;)
Линде
1
A * и использование эвристики хорошо обсуждаются в книге Норига и Рассела об искусственном интеллекте
BoltzmannBrain,
113

Дейкстр:

Он имеет одну функцию стоимости, которая представляет реальную стоимость затрат от источника к каждому узлу: f(x)=g(x).
Он находит кратчайший путь от источника к каждому другому узлу, учитывая только реальную стоимость.

Поиск:

Имеет две функции стоимости.

  1. g(x): так же, как Дейкстра. Реальная стоимость достижения узла x.
  2. h(x): приблизительная стоимость от узла xк узлу цели. Это эвристическая функция. Эта эвристическая функция никогда не должна переоценивать стоимость. Это означает, что реальная стоимость достижения узла цели из узла xдолжна быть больше или равна h(x). Это называется допустимым эвристическим.

Общая стоимость каждого узла рассчитывается по f(x)=g(x)+h(x)

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

Поэтому, если ваша эвристическая функция хороша для приближения будущей стоимости, вам нужно будет исследовать намного меньше узлов, чем Дейкстра.

Шахадат Хоссейн
источник
20

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

ttvd
источник
17
Если есть несколько потенциальных целевых узлов, можно просто изменить функцию целевого тестирования, чтобы включить их все. Таким образом, A * нужно будет запустить только один раз.
Брэд Ларсен
9

Алгоритм Дейкстры никогда не будет использоваться для поиска пути. Использование A * не представляет никакой сложности, если вы можете придумать приличную эвристику (обычно легко для игр, особенно в 2D-мирах). В зависимости от пространства поиска, итеративное углубление A * иногда предпочтительнее, поскольку оно использует меньше памяти.

Лохматая лягушка
источник
5
Почему Дейкстра никогда не будет использоваться для поиска пути? Можете ли вы уточнить?
KingNestor
2
Потому что даже если ты сможешь придумать паршивую эвристику, ты справишься лучше, чем Дейкстра. Иногда, даже если это недопустимо. Это зависит от домена. Dijkstra также не будет работать в ситуациях с нехваткой памяти, тогда как IDA * будет работать.
Лохматая лягушка
Я нашел слайды здесь: webdocs.cs.ualberta.ca/~jonathan/PREVIOUS/Courses/657/Notes/…
davidtbernal
7

Дейкстра - особый случай для А *.

Дейкстра находит минимальные затраты от стартового узла до всех остальных. A * находит минимальную стоимость от начального узла до целевого узла.

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

Код для алгоритма Дейкстры:

// A C / C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

#include <stdio.h>
#include <limits.h>

// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
 // Initialize min value
 int min = INT_MAX, min_index;

  for (int v = 0; v < V; v++)
   if (sptSet[v] == false && dist[v] <= min)
     min = dist[v], min_index = v;

   return min_index;
}

 int printSolution(int dist[], int n)
 {
  printf("Vertex   Distance from Source\n");
  for (int i = 0; i < V; i++)
     printf("%d \t\t %d\n", i, dist[i]);
  }

void dijkstra(int graph[V][V], int src)
{
 int dist[V];     // The output array.  dist[i] will hold the shortest
                  // distance from src to i

 bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
                 // path tree or shortest distance from src to i is finalized

 // Initialize all distances as INFINITE and stpSet[] as false
 for (int i = 0; i < V; i++)
    dist[i] = INT_MAX, sptSet[i] = false;

 // Distance of source vertex from itself is always 0
 dist[src] = 0;

 // Find shortest path for all vertices
 for (int count = 0; count < V-1; count++)
 {
   // Pick the minimum distance vertex from the set of vertices not
   // yet processed. u is always equal to src in first iteration.
   int u = minDistance(dist, sptSet);

   // Mark the picked vertex as processed
   sptSet[u] = true;

   // Update dist value of the adjacent vertices of the picked vertex.
   for (int v = 0; v < V; v++)

     // Update dist[v] only if is not in sptSet, there is an edge from 
     // u to v, and total weight of path from src to  v through u is 
     // smaller than current value of dist[v]
     if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                                   && dist[u]+graph[u][v] < dist[v])
        dist[v] = dist[u] + graph[u][v];
 }

 // print the constructed distance array
 printSolution(dist, V);
 }

// driver program to test above function
int main()
 {
 /* Let us create the example graph discussed above */
 int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                  {4, 0, 8, 0, 0, 0, 0, 11, 0},
                  {0, 8, 0, 7, 0, 4, 0, 0, 2},
                  {0, 0, 7, 0, 9, 14, 0, 0, 0},
                  {0, 0, 0, 9, 0, 10, 0, 0, 0},
                  {0, 0, 4, 14, 10, 0, 2, 0, 0},
                  {0, 0, 0, 0, 0, 2, 0, 1, 6},
                  {8, 11, 0, 0, 0, 0, 1, 0, 7},
                  {0, 0, 2, 0, 0, 0, 6, 7, 0}
                 };

dijkstra(graph, 0);

return 0;
}

Код для алгоритма A *:

class Node:
def __init__(self,value,point):
    self.value = value
    self.point = point
    self.parent = None
    self.H = 0
    self.G = 0
def move_cost(self,other):
    return 0 if self.value == '.' else 1

def children(point,grid):
x,y = point.point
links = [grid[d[0]][d[1]] for d in [(x-1, y),(x,y - 1),(x,y + 1),(x+1,y)]]
return [link for link in links if link.value != '%']
def manhattan(point,point2):
return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[0])
def aStar(start, goal, grid):
#The open and closed sets
openset = set()
closedset = set()
#Current point is the starting point
current = start
#Add the starting point to the open set
openset.add(current)
#While the open set is not empty
while openset:
    #Find the item in the open set with the lowest G + H score
    current = min(openset, key=lambda o:o.G + o.H)
    #If it is the item we want, retrace the path and return it
    if current == goal:
        path = []
        while current.parent:
            path.append(current)
            current = current.parent
        path.append(current)
        return path[::-1]
    #Remove the item from the open set
    openset.remove(current)
    #Add it to the closed set
    closedset.add(current)
    #Loop through the node's children/siblings
    for node in children(current,grid):
        #If it is already in the closed set, skip it
        if node in closedset:
            continue
        #Otherwise if it is already in the open set
        if node in openset:
            #Check if we beat the G score 
            new_g = current.G + current.move_cost(node)
            if node.G > new_g:
                #If so, update the node to have a new parent
                node.G = new_g
                node.parent = current
        else:
            #If it isn't in the open set, calculate the G and H score for the node
            node.G = current.G + current.move_cost(node)
            node.H = manhattan(node, goal)
            #Set the parent to our current item
            node.parent = current
            #Add it to the set
            openset.add(node)
    #Throw an exception if there is no path
    raise ValueError('No Path Found')
def next_move(pacman,food,grid):
#Convert all the points to instances of Node
for x in xrange(len(grid)):
    for y in xrange(len(grid[x])):
        grid[x][y] = Node(grid[x][y],(x,y))
#Get the path
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
#Output the path
print len(path) - 1
for node in path:
    x, y = node.point
    print x, y
pacman_x, pacman_y = [ int(i) for i in raw_input().strip().split() ]
food_x, food_y = [ int(i) for i in raw_input().strip().split() ]
x,y = [ int(i) for i in raw_input().strip().split() ]

grid = []
for i in xrange(0, x):
grid.append(list(raw_input().strip()))

next_move((pacman_x, pacman_y),(food_x, food_y), grid)
Джон Баллер
источник
Пропуск соседа, который уже находится в закрытом наборе, даст субоптимальный результат. Попытка сделать это на этом графике (это пример видео на YouTube, игнорируйте язык) даст неправильный ответ.
Дживала
5

Дейкстра находит минимальные затраты от стартового узла до всех остальных. A * находит минимальную стоимость от начального узла до целевого узла.

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

Роберт
источник
2
Это неправда. Стандартный Dijkstra используется, чтобы дать кратчайший путь между двумя точками.
Эмиль
3
Пожалуйста, не вводите в заблуждение, Дейкстра дает результат от s ко всем остальным вершинам. Таким образом, это работает медленнее.
Иван
Я второй комментарий @Emil. Все, что вам нужно сделать, это остановиться при удалении узла назначения из очереди приоритетов, и у вас будет кратчайший путь от источника к месту назначения. Это был оригинальный алгоритм на самом деле.
Четверг
Точнее: если указана цель, Dijkstra находит кратчайший путь ко всем узлам, которые лежат на пути короче, чем путь к указанной цели. Цель эвристики в A * - обрезать некоторые из этих путей. Эффективность эвристики определяет, сколько подрезано.
Уэйлон Флинн
@seteropere, но что, если целевой узел является последним узлом, который ищется? Это определенно менее эффективно, так как эвристика A * и выбор приоритетных узлов помогают убедиться, что искомый узел назначения не является последним узлом в списке
Knight0fDragon
5

Вы можете считать A * управляемой версией Dijkstra. То есть вместо изучения всех узлов вы будете использовать эвристику для выбора направления.

Говоря более конкретно, если вы реализуете алгоритмы с приоритетной очередью, то приоритет посещаемого узла будет зависеть от стоимости (стоимость предыдущих узлов + стоимость, чтобы добраться сюда) и эвристической оценки отсюда к цели. Находясь в Дейкстре, приоритет зависит только от фактической стоимости узлов. В любом случае, критерий остановки достигает цели.

gitfredy
источник
2

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

Хани
источник
4
A * дает те же результаты, что и Дейкстра, но быстрее, когда вы используете хорошую эвристику. Алгоритм * налагает некоторые условия для правильной работы, например, предполагаемое расстояние между текущим узлом и конечным узлом должно быть меньше реального расстояния.
Александру
4
* Гарантированно даст кратчайший путь, когда эвристика допустима (всегда недооценивает)
Роберт
1

Если вы посмотрите на psuedocode для Astar :

foreach y in neighbor_nodes(x)
             if y in closedset
                 continue

Принимая во внимание, если вы посмотрите на то же самое для Дейкстры :

for each neighbor v of u:         
             alt := dist[u] + dist_between(u, v) ;

Итак, суть в том, что Astar не будет оценивать узел более одного раза,
так как считает, что достаточно посмотреть на узел один раз из-
за его эвристики.

OTOH, алгоритм Дейкстры не стесняется исправлять себя, в случае,
если узел снова появляется.

Что должно сделать Астар быстрее и более подходящим для поиска пути.

simplfuzz
источник
7
Это не так: A * может просматривать узлы более одного раза. На самом деле Дейкстра - это особый случай А * ...
Эмиль
2
Проверьте это для уточнения: stackoverflow.com/questions/21441662/…
spiralmoon
Все алгоритмы поиска имеют «границу» и «посещенный набор». Ни один из алгоритмов не исправляет путь к узлу, как только он находится в посещаемом наборе: по замыслу они перемещают узлы из границы в посещаемый набор в порядке приоритета. Минимальные известные расстояния до узлов могут быть обновлены только тогда, когда они находятся на границе. Dijkstra's - это форма поиска по принципу «лучший сначала», и узел никогда не будет повторно посещаться, когда он будет помещен в «посещенный» набор. A * разделяет это свойство и использует вспомогательный оценщик, чтобы выбрать, какие узлы на границе установить приоритеты. en.wikipedia.org/wiki/Dijkstra%27s_algorithm
pygosceles
0

В A * для каждого узла вы проверяете исходящие соединения на свои.
Для каждого нового узла вы рассчитываете наименьшую стоимость (csf) на данный момент в зависимости от веса соединений с этим узлом и затрат, которые вы должны были достичь на предыдущем узле.
Кроме того, вы оцениваете стоимость от нового узла до целевого узла и добавляете это к csf. Теперь у вас есть приблизительная общая стоимость (и т. Д.). (и т. д. = csf + предполагаемое расстояние до цели) Затем вы выбираете из новых узлов тот, который имеет самый низкий уровень и т. д.
Делайте то же самое, что и раньше, пока один из новых узлов не станет целью.

Дейкстра работает почти так же. За исключением того, что предполагаемое расстояние до цели всегда равно 0, и алгоритм сначала останавливается, когда целью является не только один из новых узлов , но и узел с самым низким значением csf.

A * обычно быстрее, чем dijstra, хотя это не всегда так. В видеоиграх вы часто предпочитаете подход «достаточно близко для игры». Поэтому обычно достаточно «близкого» оптимального пути из A *.

keinabel
источник
-1

Алгоритм Дейкстры определенно завершен и оптимален, так что вы всегда найдете кратчайший путь. Однако это, как правило, занимает больше времени, поскольку используется в основном для обнаружения нескольких целевых узлов.

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

стаз
источник