investigacion - dijkstra algorithm

¿Cómo se comparan el algoritmo de Dijkstra y la estrella A?

Question

Estaba viendo lo que han estado haciendo los muchachos en el Concurso de Mario AI y algunos de ellos han construido algunos bots de Mario bastante bonitos utilizando el algoritmo de Pathing A * (A-Star).

texto alternativo http://julian.togelius.com/mariocompetition2009/screen1.png
( Video de Mario A * Bot en acción )

Mi pregunta es, ¿cómo se compara A-Star con Dijkstra? Al mirar sobre ellos, parecen similares.

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

Answer 1

Dijkstra:

Tiene una función de costo, que es el valor de costo real desde la fuente hasta cada nodo: f(x)=g(x) .
Encuentra la ruta más corta desde la fuente a cada otro nodo al considerar solo el costo real.

Una búsqueda:

Tiene dos funciones de costo.

1. g(x) : lo mismo que Dijkstra. El costo real para llegar a un nodo x .
2. h(x) : costo aproximado del nodo x al nodo objetivo. Es una función heurística. Esta función heurística nunca debería sobreestimar el costo. Esto significa que el costo real para llegar al nodo objetivo desde el nodo x debe ser mayor que o igual a 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 A * solo expande un nodo si parece prometedor. Solo se enfoca para llegar al nodo objetivo desde el nodo actual, no para llegar a todos los otros nodos. Es óptimo, si la función heurística es admisible.

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

Answer 2

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

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

Answer 3

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

Answer 4

Dijkstra es un caso especial para A *.

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

El algoritmo de Dijkstra nunca se usará para encontrar rutas. Usar A * uno puede venir con una heurística decente. Dependiendo del espacio de búsqueda, es preferible la iterativa A * 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)

Answer 5

El algoritmo de Dijkstra encuentra definitivamente el camino más corto. 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 tienes una buena heurística.

Answer 6

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

A* search otra parte, A* search que ver con los valores heurísticos, que puede definir para alcanzar su objetivo más cerca, como la distancia de Manhattan hacia la meta. Puede ser óptimo o completo, que depende de factores heurísticos. es definitivamente más rápido si tienes un único nodo objetivo.

Answer 7

El algoritmo de Dijkstra nunca se usará para la identificación de caminos. Usar A * es una obviedad si se puede obtener una heurística decente (generalmente fácil para juegos, especialmente en mundos 2D). Dependiendo del espacio de búsqueda, Iterative Deepening A * es a veces preferible porque usa menos memoria.

Answer 8

En A *, para cada nodo verifica las conexiones salientes para su.
Para cada nuevo nodo, se calcula el costo más bajo hasta el momento (csf) según los pesos de las conexiones a este nodo y los costos que tuvo que alcanzar el nodo anterior.
Además, estimas el costo del nuevo nodo al nodo objetivo y lo agregas 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 cuando el objetivo no es solo uno de los nodos nuevos , 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 "lo suficientemente cerca para un juego". Por lo tanto, el camino óptimo "suficientemente cerca" de A * es suficiente.

Answer 9

Lo que dijo el cartel anterior, además porque Dijkstra no tiene heurística y en cada paso elige los 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 tienes varios nodos objetivo candidatos, pero no sabes cuál es el más cercano (en el caso A * tendrías que ejecutarlo varias veces: una vez por cada nodo candidato).

Answer 10

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

Para decirlo de manera más concreta, si está implementando los algoritmos con una cola de prioridad, entonces la prioridad del nodo que está visitando será una función del costo (los nodos anteriores cuestan + costo para llegar aquí) y la estimación heurística de 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 el objetivo.

Answer 11

Si miras el psuedocode para Astar:

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

Mientras que, si mira 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
un nodo aparece de nuevo.

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