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

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://sofes.miximages.com/algorithm/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?

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

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

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

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.

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

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:

 // AC / C++ program for Dijkstra's single source shortest path algorithm. // The program is for adjacency matrix representation of the graph #include  #include  // 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:oG + oH) #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 a todos los demás. A * encuentra el costo mínimo desde el nodo de inicio hasta el nodo objective.

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.

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

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.

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.

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

A* search otra parte, A* search que ver con los valores heurísticos, que puede definir para alcanzar su objective 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 objective.

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 objective y lo agregas al csf. Ahora tiene el costo total estimado (etc.). (etc = csf + distancia estimada al objective) 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 objective.

Dijkstra funciona casi igual. Excepto que la distancia estimada al objective siempre es 0, y el algoritmo se detiene cuando el objective 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.

    Intereting Posts