Wie vergleichen sich Dijkstras Algorithmus und A-Star?

Ich habe mir angesehen, was die Jungs vom Mario AI-Wettbewerb gemacht haben, und einige von ihnen haben einige hübsche Mario-Bots mit dem A * (A-Star) Pathing-Algorithmus gebaut.

( Video von Mario A * Bot in Aktion )

Meine Frage ist, wie vergleicht sich A-Star mit Dijkstra? Wenn man sie betrachtet, scheinen sie ähnlich zu sein.

Warum sollte jemand einen über den anderen verwenden? Besonders im Zusammenhang mit dem Pathing in Spielen?

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

Dijkstra:

Es hat eine Kostenfunktion, die den tatsächlichen 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, indem nur die tatsächlichen Kosten berücksichtigt werden.

Eine Suche:

Es hat zwei Kostenfunktionen.

1. g(x): wie Dijkstra. Die tatsächlichen Kosten, um einen Knoten zu erreichen x.
2. h(x): ungefähre Kosten von Knoten xzu Zielknoten. Es ist 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 von Knoten xsollten größer oder gleich sein h(x). Es heißt zulässige Heuristik.

Die Gesamtkosten jedes Knotens werden von berechnet f(x)=g(x)+h(x)

Eine * Suche erweitert einen Knoten nur, wenn er vielversprechend erscheint. Es konzentriert sich nur darauf, den Zielknoten vom aktuellen Knoten aus zu erreichen, nicht alle anderen Knoten. Es ist optimal, wenn die heuristische Funktion zulässig ist.

Wenn Ihre heuristische Funktion also gut ist, um die zukünftigen Kosten zu schätzen, müssen Sie viel weniger Knoten als Dijkstra untersuchen.

Was das vorherige Poster gesagt hat, und weil Dijkstra keine Heuristik hat und bei jedem Schritt Kanten mit den geringsten Kosten auswählt, neigt es dazu, mehr von Ihrem Diagramm "abzudecken". Aus diesem Grund könnte Dijkstra nützlicher sein als A *. Ein gutes Beispiel ist, wenn Sie mehrere Kandidatenzielknoten haben, aber nicht wissen, welcher am nächsten liegt (in A * müssten Sie ihn mehrmals ausführen: einmal für jeden Kandidatenknoten).

Der Dijkstra-Algorithmus würde niemals zur Pfadfindung verwendet werden. Die Verwendung von A * ist ein Kinderspiel, wenn Sie eine anständige Heuristik erstellen können (normalerweise einfach für Spiele, insbesondere in 2D-Welten). Abhängig vom Suchraum ist die iterative Vertiefung A * manchmal vorzuziehen, da weniger Speicher benötigt wird.

Dijkstra ist ein Sonderfall für A *.

Dijkstra findet die Mindestkosten vom Startknoten zu allen anderen. A * ermittelt die Mindestkosten vom Startknoten zum Zielknoten.

Der Dijkstra-Algorithmus würde niemals zur Pfadfindung verwendet werden. Mit A * kann man eine anständige Heuristik erstellen. Abhängig vom Suchraum ist iteratives A * vorzuziehen, da es weniger Speicher benötigt.

Der Code für den Dijkstra-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)

Dijkstra findet die Mindestkosten vom Startknoten zu allen anderen. A * ermittelt die Mindestkosten vom Startknoten zum Zielknoten.

Daher scheint Dijkstra weniger effizient zu sein, wenn Sie nur den Mindestabstand von einem Knoten zum anderen benötigen.

Sie können A * als geführte Version von Dijkstra betrachten. Das heißt, anstatt alle Knoten zu erkunden, verwenden Sie eine Heuristik, um eine Richtung auszuwählen.

Genauer gesagt, wenn Sie die Algorithmen mit einer Prioritätswarteschlange implementieren, hängt die Priorität des Knotens, den Sie besuchen, von den Kosten (Kosten der vorherigen Knoten + Kosten, um hierher zu gelangen) und der heuristischen Schätzung von hier aus ab zum Ziel. In Dijkstra wird die Priorität nur durch die tatsächlichen Kosten für die Knoten beeinflusst. In beiden Fällen erreicht das Stoppkriterium das Ziel.

Dijkstras Algorithmus findet definitiv den kürzesten Weg. Andererseits hängt A * von der Heuristik ab. Aus diesem Grund ist A * schneller als der Dijkstra-Algorithmus und liefert gute Ergebnisse, wenn Sie eine gute Heuristik haben.

Wenn Sie sich den Pseudocode für Astar ansehen :

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

Wenn Sie sich für Dijkstra dasselbe ansehen :

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

Der Punkt ist also, dass Astar einen Knoten nicht mehr als einmal bewertet,
da es aufgrund
seiner Heuristik der Ansicht ist, dass ein einmaliger Blick auf einen Knoten ausreichend ist .

OTOH, Dijkstras Algorithmus scheut sich nicht, sich selbst zu korrigieren, falls
ein Knoten erneut auftaucht.

Dadurch sollte Astar schneller und besser für die Wegfindung geeignet sein.

In A * überprüfen Sie für jeden Knoten die ausgehenden Verbindungen auf ihre.
Für jeden neuen Knoten berechnen Sie die bisher niedrigsten Kosten (csf) in Abhängigkeit von der Gewichtung der Verbindungen zu diesem Knoten und den Kosten, die Sie zum Erreichen des vorherigen Knotens hatten.
Zusätzlich schätzen Sie die Kosten vom neuen Knoten zum Zielknoten und fügen diese der CSF hinzu. Sie haben jetzt die geschätzten Gesamtkosten (usw.). (etc = csf + geschätzte Entfernung zum Ziel) Als nächstes wählen Sie aus den neuen Knoten den mit dem niedrigsten usw. aus.
Machen Sie dasselbe wie zuvor, bis einer der neuen Knoten das Ziel ist.

Dijkstra funktioniert fast genauso. Abgesehen davon, dass die geschätzte Entfernung zum Ziel immer 0 ist und der Algorithmus zuerst stoppt, wenn das Ziel nicht nur einer der neuen Knoten ist , sondern auch der mit dem niedrigsten csf.

A * ist normalerweise schneller als dijstra, obwohl dies nicht immer der Fall ist. In Videospielen bevorzugen Sie häufig den Ansatz "nah genug für ein Spiel". Daher reicht normalerweise der optimale Pfad "nah genug" von A * aus.

Der Dijkstra-Algorithmus ist definitiv vollständig und optimal, sodass Sie immer den kürzesten Weg finden. Es dauert jedoch tendenziell länger, da es hauptsächlich zum Erkennen mehrerer Zielknoten verwendet wird.

A* searchAuf der anderen Seite geht es um heuristische Werte, die Sie definieren können, um Ihr Ziel näher zu erreichen, z. B. die Entfernung von Manhattan zum Ziel. Es kann entweder optimal oder vollständig sein, was von heuristischen Faktoren abhängt. Es ist definitiv schneller, wenn Sie einen einzelnen Zielknoten haben.