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

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

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

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

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.

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

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.

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)

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.

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.

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.

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.

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.

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.