Como o algoritmo de Dijkstra e a A-Star se comparam?

Eu estava olhando o que os caras da competição Mario AI estavam fazendo e alguns deles criaram alguns bots Mario muito legais, utilizando o algoritmo de localização A * (A-Star).

( Vídeo de Mario A * Bot Em Ação )

Minha pergunta é: como o A-Star se compara ao Dijkstra? Olhando por cima deles, eles parecem semelhantes.

Por que alguém usaria um sobre o outro? Especialmente no contexto de participar de jogos?

Dijkstra é um caso especial para A * (quando a heurística é zero).

Dijkstra:

Tem uma função de custo, que é o valor custo real da origem para cada nó: f(x)=g(x).
Ele encontra o caminho mais curto da origem para todos os outros nós, considerando apenas o custo real.

Uma pesquisa:

Tem duas funções de custo.

1. g(x): o mesmo que Dijkstra. O custo real para alcançar um nó x.
2. h(x): custo aproximado do nó xao nó da meta. É uma função heurística. Essa função heurística nunca deve superestimar o custo. Isso significa que o custo real para alcançar o nó da meta a partir do nó xdeve ser maior ou igual h(x). É chamado de heurística admissível.

O custo total de cada nó é calculado por f(x)=g(x)+h(x)

Uma pesquisa * expande apenas um nó se parecer promissor. Ele se concentra apenas em alcançar o nó do objetivo a partir do nó atual, e não em todos os outros nós. É ideal se a função heurística for admissível.

Portanto, se sua função heurística for boa para aproximar o custo futuro, será necessário explorar muito menos nós que o Dijkstra.

O que o pôster anterior disse, mais porque o Dijkstra não tem heurística e a cada passo escolhe arestas com o menor custo, ele tende a "cobrir" mais do seu gráfico. Por isso, o Dijkstra poderia ser mais útil que o A *. Um bom exemplo é quando você tem vários nós de destino candidatos, mas não sabe qual deles é o mais próximo (no caso A *, você teria que executá-lo várias vezes: uma vez para cada nó candidato).

O algoritmo de Dijkstra nunca seria usado para encontrar caminhos. Usar A * é um acéfalo se você conseguir uma heurística decente (geralmente fácil para jogos, especialmente em mundos 2D). Dependendo do espaço de pesquisa, o Aprofundamento Iterativo A * às vezes é preferível porque utiliza menos memória.

Dijkstra é um caso especial para A *.

Dijkstra encontra os custos mínimos do nó inicial para todos os outros. A * encontra o custo mínimo do nó inicial ao nó do objetivo.

O algoritmo de Dijkstra nunca seria usado para encontrar caminhos. O uso de A * pode gerar uma heurística decente. Dependendo do espaço de pesquisa, é preferível o iterativo A *, pois utiliza menos memória.

O código para o algoritmo de Dijkstra é:

// 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;
}

O código para o algoritmo 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)

Dijkstra encontra os custos mínimos do nó inicial para todos os outros. A * encontra o custo mínimo do nó inicial ao nó do objetivo.

Portanto, parece que o Dijkstra seria menos eficiente quando tudo o que você precisa é a distância mínima de um nó para outro.

Você pode considerar A * uma versão guiada do Dijkstra. Significado, em vez de explorar todos os nós, você usará uma heurística para escolher uma direção.

Em termos mais concretos, se você estiver implementando os algoritmos com uma fila de prioridade, a prioridade do nó que você está visitando será uma função do custo (nós anteriores custa + custo para chegar aqui) e a estimativa heurística daqui para o objetivo. Enquanto estiver em Dijkstra, a prioridade é influenciada apenas pelo custo real dos nós. Em ambos os casos, o critério de parada está atingindo a meta.

O algoritmo de Dijkstra encontra definitivamente o caminho mais curto. Por outro lado, A * depende da heurística. Por esse motivo, A * é mais rápido que o algoritmo de Dijkstra e fornecerá bons resultados se você tiver uma boa heurística.

Se você olhar para o psuedocode para Astar:

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

Visto que, se você olhar o mesmo para Dijkstra :

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

Portanto, o ponto é que o Astar não avaliará um nó mais de uma vez,
pois acredita que olhar um nó uma vez é suficiente, devido
às suas heurísticas.

OTOH, o algoritmo de Dijkstra não tem vergonha de se corrigir, caso
um nó apareça novamente.

O que deve tornar o Astar mais rápido e mais adequado para encontrar o caminho.

Em A *, para cada nó, você verifica as conexões de saída.
Para cada novo nó, você calcula o menor custo até agora (csf), dependendo dos pesos das conexões com esse nó e dos custos que você tinha para alcançar o nó anterior.
Além disso, você estima o custo do novo nó para o nó de destino e o adiciona ao csf. Agora você tem o custo total estimado (etc). (etc = csf + distância estimada para o destino) Em seguida, escolha entre os novos nós aquele com o menor, etc.
Faça o mesmo que antes, até que um dos novos nós seja o destino.

Dijkstra funciona quase da mesma forma. Exceto que a distância estimada para o destino é sempre 0 e o algoritmo para primeiro quando o destino não é apenas um dos novos nós , mas também aquele com o csf mais baixo.

A * é geralmente mais rápido que dijstra, embora nem sempre seja esse o caso. Nos videogames, você costuma usar a abordagem "perto o suficiente para um jogo". Portanto, o caminho ótimo "próximo o suficiente" de A * geralmente é suficiente.

O algoritmo de Dijkstra é definitivamente completo e ideal para você sempre encontrar o caminho mais curto. No entanto, costuma demorar mais, pois é usado principalmente para detectar vários nós de meta.

A* searchpor outro lado, importa com valores heurísticos, que você pode definir para atingir seu objetivo mais próximo, como a distância de manhattan em direção ao objetivo. Pode ser ideal ou completo, dependendo de fatores heurísticos. é definitivamente mais rápido se você tiver um único nó de objetivo.