¿Cómo se compara el algoritmo de Dijkstra y A-Star?

Estaba mirando lo que los muchachos en la competencia Mario AI han estado haciendo y algunos de ellos han construido algunos robots de Mario bastante buenos utilizando el algoritmo de ruta A * (A-Star).

( Video de Mario A * Bot en acción )

Mi pregunta es, ¿cómo se compara A-Star con Dijkstra? Mirándolos, parecen similares.

¿Por qué alguien usaría uno sobre el otro? ¿Especialmente en el contexto de la ruta en los juegos?

Dijkstra es un caso especial para A * (cuando la heurística es cero).

Dijkstra:

Tiene una función de coste, que es valor coste real de la fuente a cada nodo: f(x)=g(x).
Encuentra la ruta más corta desde el origen hasta todos los demás nodos considerando solo el costo real.

Una búsqueda:

Tiene dos funciones de costo.

1. g(x): igual que Dijkstra. El costo real para llegar a un nodo x.
2. h(x): costo aproximado de nodo xa nodo objetivo. Es una función heurística. Esta función heurística nunca debe sobreestimar el costo. Eso significa que el costo real para alcanzar el objetivo de nodo a nodo xdebe ser mayor o igual h(x). Se llama heurística admisible.

El costo total de cada nodo se calcula mediante f(x)=g(x)+h(x)

Una búsqueda * solo expande un nodo si parece prometedor. Solo se enfoca para alcanzar el nodo objetivo desde el nodo actual, no para alcanzar todos los demás nodos. Es óptimo, si la función heurística es admisible.

Entonces, si su función heurística es buena para aproximar el costo futuro, entonces necesitará explorar muchos menos nodos que Dijkstra.

Lo que decía el póster anterior, además porque Dijkstra no tiene heurística y en cada paso escoge bordes con el menor costo, tiende a "cubrir" más de su gráfico. Debido a eso, Dijkstra podría ser más útil que A *. Un buen ejemplo es cuando tiene varios nodos objetivo candidatos, pero no sabe cuál es el más cercano (en el caso A *, tendría que ejecutarlo varias veces: una vez para cada nodo candidato).

El algoritmo de Dijkstra nunca se usaría para encontrar rutas. El uso de A * es obvio si puedes encontrar una heurística decente (generalmente fácil para juegos, especialmente en mundos 2D). Dependiendo del espacio de búsqueda, a veces es preferible la profundización iterativa A * porque usa menos memoria.

Dijkstra es un caso especial para A *.

Dijkstra encuentra los costos mínimos desde el nodo inicial hasta todos los demás. A * encuentra el costo mínimo desde el nodo inicial hasta el nodo objetivo.

El algoritmo de Dijkstra nunca se usaría para encontrar el camino. Usar A * one puede llegar a una heurística decente. Dependiendo del espacio de búsqueda, es preferible A * iterativo porque usa menos memoria.

El código para el algoritmo de Dijkstra es:

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

El código para el algoritmo A * es:

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 encuentra los costos mínimos desde el nodo inicial hasta todos los demás. A * encuentra el costo mínimo desde el nodo inicial hasta el nodo objetivo.

Por lo tanto, parecería que Dijkstra sería menos eficiente cuando todo lo que necesita es la distancia mínima de un nodo a otro.

Puede considerar A * una versión guiada de Dijkstra. Es decir, en lugar de explorar todos los nodos, utilizará una heurística para elegir una dirección.

Para decirlo más concretamente, si está implementando los algoritmos con una cola de prioridad, entonces la prioridad del nodo que está visitando será una función del costo (costo de nodos anteriores + costo para llegar aquí) y la estimación heurística desde aquí a la meta. Mientras que en Dijkstra, la prioridad solo está influenciada por el costo real para los nodos. En cualquier caso, el criterio de detención es alcanzar la meta.

El algoritmo de Dijkstra encuentra el camino más corto definitivamente. Por otro lado, A * depende de la heurística. Por esta razón, A * es más rápido que el algoritmo de Dijkstra y dará buenos resultados si tiene una buena heurística.

Si nos fijamos en el psuedocode de Astar:

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

Mientras que, si nos fijamos en lo mismo para Dijkstra :

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

Entonces, el punto es que Astar no evaluará un nodo más de una vez,
ya que cree que mirar un nodo una vez es suficiente, debido
a su heurística.

OTOH, el algoritmo de Dijkstra no es tímido para corregirse, en caso de
que aparezca un nodo nuevamente.

Lo que debería hacer que Astar sea más rápido y más adecuado para encontrar rutas.

En A *, para cada nodo verifica las conexiones salientes para sus.
Para cada nuevo nodo, calcula el costo más bajo hasta ahora (csf) dependiendo de los pesos de las conexiones a este nodo y los costos que tuvo que alcanzar el nodo anterior.
Además, estima el costo desde el nuevo nodo hasta el nodo de destino y agrega esto al csf. Ahora tiene el costo total estimado (etc.). (etc = csf + distancia estimada al objetivo) A continuación, elija entre los nuevos nodos el que tenga el más bajo, etc.
Haga lo mismo que antes hasta que uno de los nuevos nodos sea ​​el objetivo.

Dijkstra funciona casi igual. Excepto que la distancia estimada al objetivo siempre es 0, y el algoritmo se detiene primero cuando el objetivo no es solo uno de los nuevos nodos , sino también el que tiene el csf más bajo.

A * suele ser más rápido que dijstra, aunque este no siempre será el caso. En los videojuegos, a menudo prefieres el enfoque de "lo suficientemente cerca para un juego". Por lo tanto, la ruta óptima "lo suficientemente cerca" de A * generalmente es suficiente.

El algoritmo de Dijkstra es definitivamente completo y óptimo para que siempre encuentre el camino más corto. Sin embargo, tiende a tomar más tiempo ya que se usa principalmente para detectar múltiples nodos de objetivo.

A* searchpor otro lado, importa con valores heurísticos, que puede definir para alcanzar su objetivo más cerca, como la distancia de Manhattan hacia el objetivo. Puede ser óptimo o completo, lo que depende de factores heurísticos. definitivamente es más rápido si tiene un nodo de objetivo único.