Wie ist der Vergleich zwischen Dijkstra's Algorithmus und A-Star?

Question

Ich habe mir angesehen, was die Jungs in der Mario AI Wettbewerb und einige von ihnen haben einige ziemlich tolle Mario-Bots gebaut, die den A* (A-Star) Pathing Algorithm verwenden.

( Video von Mario A* Bot in Aktion )

Meine Frage ist, wie sich A-Star mit Dijkstra vergleichen lässt? Wenn ich sie mir ansehe, scheinen sie ähnlich zu sein.

Warum sollte jemand das eine dem anderen vorziehen? Vor allem im Zusammenhang mit der Wegfindung in Spielen?

Answer 1

Dijkstra ist ein Spezialfall für A* (wenn die Heuristik Null ist).

Answer 2

Dijkstra:

Es hat eine Kostenfunktion, die den realen Kostenwert von der Quelle zu jedem Knoten darstellt: f(x)=g(x) .
Es findet den kürzesten Weg von der Quelle zu jedem anderen Knoten, wobei nur die tatsächlichen Kosten berücksichtigt werden.

A*-Suche:

Sie hat zwei Kostenfunktionen.

1. g(x) dasselbe wie Dijkstra. Die tatsächlichen Kosten, um einen Knoten zu erreichen x .
2. h(x) Ungefähre Kosten vom Knoten x zum Zielknoten. Es handelt sich um eine heuristische Funktion. Diese heuristische Funktion sollte die Kosten niemals überschätzen. Das heißt, die tatsächlichen Kosten für das Erreichen des Zielknotens vom Knoten x sollte größer oder gleich sein h(x) . Sie wird als zulässige Heuristik bezeichnet.

Die Gesamtkosten eines jeden Knotens werden wie folgt berechnet f(x)=g(x)+h(x)

Bei der A*-Suche wird ein Knoten nur dann erweitert, wenn er vielversprechend erscheint. Sie konzentriert sich nur darauf, den Zielknoten vom aktuellen Knoten aus zu erreichen, nicht darauf, alle anderen Knoten zu erreichen. Sie ist optimal, wenn die heuristische Funktion zulässig ist.

Wenn Ihre heuristische Funktion also gut ist, um die zukünftigen Kosten zu approximieren, dann müssen Sie viel weniger Knoten erkunden als Dijkstra.

Answer 3

Was der Vorposter sagte, und weil Dijkstra keine Heuristik hat und bei jedem Schritt die Kanten mit den geringsten Kosten auswählt, neigt er dazu, mehr von Ihrem Graphen "abzudecken". Aus diesem Grund könnte Dijkstra nützlicher sein als A*. Ein gutes Beispiel ist, wenn Sie mehrere Zielknoten haben, aber nicht wissen, welcher am nächsten liegt (im Falle von A* müssten Sie die Suche mehrmals durchführen: einmal für jeden Zielknoten).

Answer 4

Dijkstras Algorithmus würde niemals für die Wegfindung verwendet werden. Die Verwendung von A* ist ein Kinderspiel, wenn man eine gute Heuristik entwickeln kann (was bei Spielen, insbesondere in 2D-Welten, in der Regel einfach ist). Je nach Suchraum ist die iterative Vertiefung von A* manchmal vorzuziehen, da sie weniger Speicherplatz benötigt.

Answer 5

Dijkstra ist ein Spezialfall von A*.

Dijkstra findet die minimalen Kosten vom Startknoten zu allen anderen. A* findet die minimalen Kosten vom Startknoten zum Zielknoten.

Dijkstras Algorithmus würde niemals für die Pfadfindung verwendet werden. Mit A* kann man eine vernünftige Heuristik entwickeln. Je nach Suchraum ist der iterative A*-Algorithmus vorzuziehen, da er weniger Speicherplatz benötigt.

Der Code für Dijkstras Algorithmus lautet:

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

Der Code für den A*-Algorithmus lautet:

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)