Comment l'algorithme de Dijkstra et A-Star se comparent-ils?

154

Je regardais ce que faisaient les gars du concours Mario AI et certains d'entre eux ont construit de très bons robots Mario en utilisant l'algorithme de cheminement A * (A-Star).

texte alternatif
( Vidéo de Mario A * Bot en action )

Ma question est la suivante: comment A-Star se compare-t-il à Dijkstra? En regardant par-dessus eux, ils semblent similaires.

Pourquoi quelqu'un utiliserait-il l'un sur l'autre? Surtout dans le contexte du cheminement dans les jeux?

KingNestor
la source
47
xkcd.com/342
SLaks
@SLaks A * utilise plus de mémoire que dijkstra? Comment se fait-il si un seul chemin prometteur de nœuds pendant que dijkstra les essaie tous?
Poutrathor

Réponses:

177

Dijkstra est un cas particulier pour A * (lorsque l'heuristique est nulle).

leiz
la source
1
Dans dijkstra, nous ne considérons que la distance de la source, non? Et le sommet minimum est pris en considération?
Kraken
4
Je pensais que A * est un cas particulier pour Dijkstra où ils utilisent une heuristique. Depuis Dijkstra était là d'abord afaik.
Madmenyo
46
@MennoGouw: Oui, l'algorithme de Dijkstra a été développé en premier; mais c'est un cas particulier de l'algorithme plus général A *. Il n'est pas du tout inhabituel (en fait, probablement la norme) que des cas particuliers soient d'abord découverts, puis généralisés par la suite.
Pieter Geerkens
1
Excellente réponse pour tous ceux qui connaissent l'heuristique;)
lindhe
1
A * et l'utilisation de l'heuristique sont bien discutés dans le livre de Norvig et Russel sur l'IA
BoltzmannBrain
113

Dijkstra:

Il dispose d' une fonction de coût, ce qui est une réelle valeur des coûts de la source à chaque nœud: f(x)=g(x).
Il trouve le chemin le plus court de la source à tous les autres nœuds en ne considérant que le coût réel.

Une recherche:

Il a deux fonctions de coût.

  1. g(x): même que Dijkstra. Le coût réel pour atteindre un nœud x.
  2. h(x): coût approximatif d'un nœud xà l'autre. C'est une fonction heuristique. Cette fonction heuristique ne doit jamais surestimer le coût. Cela signifie que le coût réel pour atteindre le nœud d'objectif à partir du nœud xdoit être supérieur ou égal h(x). C'est ce qu'on appelle l'heuristique admissible.

Le coût total de chaque nœud est calculé par f(x)=g(x)+h(x)

Une recherche * ne développe un nœud que si cela semble prometteur. Il se concentre uniquement pour atteindre le nœud cible à partir du nœud actuel, et non pour atteindre tous les autres nœuds. Il est optimal, si la fonction heuristique est admissible.

Donc, si votre fonction heuristique est bonne pour estimer le coût futur, vous devrez explorer beaucoup moins de nœuds que Dijkstra.

Shahadat Hossain
la source
20

Ce que l'affiche précédente a dit, et parce que Dijkstra n'a pas d'heuristique et à chaque étape, il choisit les arêtes avec le moindre coût, il a tendance à "couvrir" une plus grande partie de votre graphique. Pour cette raison, Dijkstra pourrait être plus utile que A *. Un bon exemple est lorsque vous avez plusieurs nœuds cibles candidats, mais que vous ne savez pas lequel est le plus proche (dans le cas A *, vous devrez l'exécuter plusieurs fois: une fois pour chaque nœud candidat).

ttvd
la source
17
S'il y a plusieurs nœuds de but potentiels, on pourrait simplement changer la fonction de test d'objectif pour les inclure tous. De cette façon, A * n'aurait besoin d'être exécuté qu'une seule fois.
Brad Larsen
9

L'algorithme de Dijkstra ne serait jamais utilisé pour la recherche de chemin. Utiliser A * est une évidence si vous pouvez trouver une heuristique décente (généralement facile pour les jeux, en particulier dans les mondes 2D). En fonction de l'espace de recherche, l'approfondissement itératif A * est parfois préférable car il utilise moins de mémoire.

Grenouille poilue
la source
5
Pourquoi Dijkstra ne serait-il jamais utilisé pour la recherche de chemin? Peux-tu élaborer?
KingNestor
2
Parce que même si vous pouvez trouver une mauvaise heuristique, vous ferez mieux que Dijkstra. Parfois même si c'est inadmissible. Cela dépend du domaine. Dijkstra ne fonctionnera pas non plus dans des situations de faible mémoire, contrairement à IDA *.
Shaggy Frog
J'ai trouvé les diapositives ici: webdocs.cs.ualberta.ca/~jonathan/PREVIOUS/Courses/657/Notes/…
davidtbernal
7

Dijkstra est un cas particulier pour A *.

Dijkstra trouve les coûts minimaux du nœud de départ à tous les autres. A * trouve le coût minimum du nœud de départ au nœud d'objectif.

L'algorithme de Dijkstra ne serait jamais utilisé pour la recherche de chemin. En utilisant A *, on peut trouver une heuristique décente. En fonction de l'espace de recherche, le A * itératif est préférable car il utilise moins de mémoire.

Le code de l'algorithme de Dijkstra est:

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

Le code de l'algorithme A * est:

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
la source
sauter les voisins qui sont déjà dans un ensemble fermé donnera un résultat sous-optimal. L'essayer sur ce graphique (c'est un exemple de vidéo youtube, ignorer la langue) donnera une mauvaise réponse.
itsjwala
5

Dijkstra trouve les coûts minimaux du nœud de départ à tous les autres. A * trouve le coût minimum du nœud de départ au nœud d'objectif.

Par conséquent, il semblerait que Dijkstra serait moins efficace lorsque tout ce dont vous avez besoin est la distance minimale d'un nœud à un autre.

Robert
la source
2
Ce n'est pas vrai. Standard Dijkstra est utilisé pour donner le chemin le plus court entre deux points.
Emil
3
Veuillez ne pas vous tromper, Dijkstra donne le résultat de s à tous les autres sommets. Ainsi, cela fonctionne plus lentement.
Ivan Voroshilin
Je seconde le commentaire de @Emil. Tout ce que vous avez à faire est de vous arrêter lorsque vous supprimez le nœud de destination de la file d'attente prioritaire et vous disposez du chemin le plus court de la source à la destination. C'était en fait l'algorithme original.
seteropere
Plus précisément: si une cible est spécifiée, Dijkstra trouve le chemin le plus court vers tous les nœuds qui se trouvent sur des chemins plus courts que le chemin vers la cible spécifiée. Le but de l'heuristique de A * est d'élaguer certains de ces chemins. L'efficacité de l'heuristique détermine le nombre d'élagages.
Waylon Flinn
@seteropere, mais que se passe-t-il si votre nœud de destination est le dernier nœud recherché? C'est certainement moins efficace, car l'heuristique d'A * et le choix d'un nœud prioritaire sont ce qui permet de s'assurer que le nœud de destination recherché n'est pas le dernier nœud de la liste
Knight0fDragon
5

Vous pouvez considérer A * comme une version guidée de Dijkstra. Cela signifie qu'au lieu d'explorer tous les nœuds, vous utiliserez une heuristique pour choisir une direction.

Pour le dire plus concrètement, si vous implémentez les algorithmes avec une file d'attente prioritaire, la priorité du nœud que vous visitez sera fonction du coût (coût des nœuds précédents + coût pour arriver ici) et de l'estimation heuristique d'ici au but. À Dijkstra, la priorité n'est influencée que par le coût réel des nœuds. Dans les deux cas, le critère d'arrêt atteint l'objectif.

gitfredy
la source
2

L'algorithme de Dijkstra trouve définitivement le chemin le plus court. D'autre part, A * dépend de l'heuristique. Pour cette raison, A * est plus rapide que l'algorithme de Dijkstra et donnera de bons résultats si vous avez une bonne heuristique.

Hani
la source
4
A * donne les mêmes résultats que Dijkstra, mais plus rapidement lorsque vous utilisez une bonne heuristique. Un algorithme * impose certaines conditions pour fonctionner correctement, telles que la distance estimée entre le nœud actuel et le nœud final doit être inférieure à la distance réelle.
Alexandru
4
A * est garanti de donner le chemin le plus court lorsque l'heuristique est admissible (sous-estime toujours)
Robert
1

Si vous regardez le psuedocode pour Astar:

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

Considérant que, si vous regardez la même chose pour Dijkstra :

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

Donc, le fait est qu'Astar n'évaluera pas un nœud plus d'une fois,
car il pense que regarder un nœud une fois est suffisant, en raison
de son heuristique.

OTOH, l'algorithme de Dijkstra n'hésite pas à se corriger, au cas où
un nœud réapparaît.

Ce qui devrait rendre Astar plus rapide et plus adapté à la recherche de chemin.

simplfuzz
la source
7
Ce n'est pas vrai: A * peut regarder les nœuds plus d'une fois. En fait, Dijkstra est un cas spécial de A * ...
Emil
2
Vérifiez celui-ci pour plus de précisions: stackoverflow.com/questions/21441662/…
spiralmoon
Tous les algorithmes de recherche ont une "frontière" et un "ensemble visité". Aucun des deux algorithmes ne corrige le chemin vers un nœud une fois qu'il est dans l'ensemble visité: par conception, ils déplacent les nœuds de la frontière vers l'ensemble visité dans l'ordre de priorité. Les distances minimales connues aux nœuds ne peuvent être mises à jour que lorsqu'ils se trouvent à la frontière. Dijkstra est une forme de recherche «best-first», et un nœud ne sera jamais revisité une fois placé dans l'ensemble "visité". A * partage cette propriété et utilise un estimateur auxiliaire pour choisir les nœuds de la frontière à prioriser. en.wikipedia.org/wiki/Dijkstra%27s_algorithm
pygosceles
0

Dans A *, pour chaque nœud, vous vérifiez les connexions sortantes pour leur.
Pour chaque nouveau nœud, vous calculez le coût le plus bas jusqu'à présent (csf) en fonction des poids des connexions à ce nœud et des coûts que vous avez dû atteindre le nœud précédent.
En outre, vous estimez le coût du nouveau nœud au nœud cible et l'ajoutez au csf. Vous avez maintenant le coût total estimé (etc.). (etc = csf + distance estimée à la cible) Ensuite, vous choisissez parmi les nouveaux nœuds celui avec le plus bas, etc.
Faites la même chose que précédemment jusqu'à ce que l'un des nouveaux nœuds soit la cible.

Dijkstra fonctionne presque de la même manière. Sauf que la distance estimée à la cible est toujours de 0, et l'algorithme s'arrête d'abord lorsque la cible n'est pas seulement l'un des nouveaux nœuds , mais aussi celui avec le csf le plus bas.

A * est généralement plus rapide que dijstra, bien que ce ne soit pas toujours le cas. Dans les jeux vidéo, vous préférez souvent l'approche «assez proche pour un jeu». Par conséquent, le chemin optimal "assez proche" de A * suffit généralement.

keinabel
la source
-1

L'algorithme de Dijkstra est définitivement complet et optimal pour que vous trouviez toujours le chemin le plus court. Cependant, cela a tendance à prendre plus de temps car il est principalement utilisé pour détecter plusieurs nœuds de but.

A* searchd'autre part, les valeurs heuristiques, que vous pouvez définir pour atteindre votre objectif plus près, comme la distance de Manhattan par rapport à l'objectif. Il peut être optimal ou complet, ce qui dépend de facteurs heuristiques. c'est nettement plus rapide si vous n'avez qu'un seul nœud d'objectif.

Stase
la source