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

154

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).

texto alternativo
( 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?

KingNestor
fonte
47
xkcd.com/342
SLaks
@ Slaks A * usa mais memória do que dijkstra? Como é que se um * único caminho promete nós enquanto dijkstra tenta todos eles?
Poutrathor 31/12/18

Respostas:

177

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

leiz
fonte
1
Em dijkstra, consideramos apenas a distância da fonte, certo? E o vértice mínimo é levado em consideração?
precisa
4
Eu pensei que A * é um caso especial para Dijkstra, onde eles usam uma heurística. Desde Dijkstra foi o primeiro auge.
Madmenyo
46
@MennoGouw: Sim, o algoritmo de Dijkstra foi desenvolvido primeiro; mas é um caso especial do algoritmo mais geral A *. Não é incomum (de fato, provavelmente a norma) que casos especiais sejam descobertos primeiro e depois generalizados.
Pieter Geerkens
1
Ótima resposta para quem conhece heurística;) #
lindhe
1
A * e o uso de heurísticas são discutidos bem de Norvig e Russel livro AI
BoltzmannBrain
113

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.

Shahadat Hossain
fonte
20

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).

ttvd
fonte
17
Se houver vários nós de objetivos em potencial, pode-se simplesmente alterar a função de teste de objetivos para incluir todos eles. Dessa forma, o A * precisaria ser executado apenas uma vez.
Bradrars Larsen
9

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.

Shaggy Frog
fonte
5
Por que Dijkstra nunca seria usado para encontrar caminhos? Você pode elaborar?
KingNestor
2
Porque mesmo se você conseguir uma péssima heurística, terá melhor desempenho do que Dijkstra. Às vezes, mesmo que seja inadmissível. Depende do domínio. Dijkstra também não funcionará em situações de pouca memória, enquanto o IDA * funcionará.
12269 Shaggy Frog
7

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)
John Baller
fonte
pular o vizinho que já está no conjunto fechado dará subótimo. Experimentá-lo neste gráfico (é um exemplo de vídeo do youtube, ignore o idioma) dará uma resposta errada.
itsjwala
5

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.

Robert
fonte
2
Isso não é verdade. Dijkstra padrão é usado para fornecer o caminho mais curto entre dois pontos.
Emil
3
Por favor, não confunda, o Dijkstra's dá resultado de s para todos os outros vértices. Assim, funciona mais devagar.
Ivan Voroshilin
Eu segundo comentário @Emil. Tudo o que você precisa fazer é parar ao remover o nó de destino da fila de prioridade e você possui o caminho mais curto da origem ao destino. Na verdade, esse era o algoritmo original.
Seteropere 26/08/16
Mais precisamente: se um destino for especificado, o Dijkstra encontrará o caminho mais curto para todos os nós que se encontram em caminhos mais curtos que o caminho para o destino especificado. O objetivo da heurística em A * é podar alguns desses caminhos. A eficácia da heurística determina quantas são podadas.
Waylon Flinn
@etereter, mas e se o seu nó de destino for o último nó pesquisado? É definitivamente menos eficiente, uma vez que A * 's heurísticas e escolher um nós prioritários são o que ajuda a garantir que o nó de destino procurou não é o último nó na lista
Knight0fDragon
5

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.

gitfredy
fonte
2

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.

Hani
fonte
4
A * fornece os mesmos resultados que Dijkstra, mas mais rápido quando você usa uma boa heurística. Um algoritmo * impõe algumas condições para funcionar corretamente, como a distância estimada entre o nó atual e o nó final deve ser menor que a distância real.
289 Alexandru Alexandru
4
A * é garantido para dar o caminho mais curto quando a heurística é admissível (sempre subestima)
Robert
1

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.

simplfuzz
fonte
7
Isso não é verdade: A * pode olhar para os nós mais de uma vez. Na verdade, Dijkstra é um caso especial de A * ...
Emil
2
Verifique este aqui para esclarecimentos: stackoverflow.com/questions/21441662/…
spiralmoon
Todos os algoritmos de pesquisa têm uma "fronteira" e um "conjunto visitado". Nenhum algoritmo corrige o caminho para um nó, uma vez que está no conjunto visitado: por design, eles movem os nós da fronteira para o conjunto visitado na ordem de prioridade. As distâncias mínimas conhecidas para os nós podem ser atualizadas apenas enquanto estiverem na fronteira. O Dijkstra's é uma forma de busca pela melhor primeira vez, e um nó nunca será revisitado depois de colocado no conjunto "visitado". A * compartilha essa propriedade e usa um estimador auxiliar para escolher quais nós na fronteira priorizar. en.wikipedia.org/wiki/Dijkstra%27s_algorithm
pygosceles
0

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.

keinabel
fonte
-1

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.

Estase
fonte