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

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

Konkreter ausgedrückt: Wenn Sie die Algorithmen mit einer Prioritätswarteschlange implementieren, dann ist die Priorität des besuchten Knotens eine Funktion der Kosten (Kosten des vorherigen Knotens + Kosten für den Weg zum Ziel) und der heuristischen Schätzung des Weges zum Ziel. Bei Dijkstra hingegen wird die Priorität nur von den tatsächlichen Kosten zu den Knotenpunkten beeinflusst. In beiden Fällen ist das Erreichen des Ziels das Haltekriterium.

Answer 2

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

Daher scheint es, dass Dijkstra weniger effizient ist, wenn man nur die minimale Entfernung von einem Knoten zu einem anderen benötigt.

Answer 3

Wenn Sie sich die psuedocode für Astar :

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

Betrachtet man hingegen die gleichen Zahlen für Dijkstra :

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 auswerten wird,
da sie der Ansicht ist, dass die einmalige Betrachtung eines Knotens ausreicht, da
auf seine Heuristik.

OTOH, Dijkstra's Algorithmus ist nicht scheu, sich selbst zu korrigieren, falls
taucht wieder ein Knoten auf.

Welche sollte machen Astar schneller und besser geeignet für die Pfadsuche.

Answer 4

Die Algorithmen von BFS und Dijkstra sind einander sehr ähnlich; sie sind beide ein Sonderfall des A*-Algorithmus.

Der A*-Algorithmus ist nicht nur allgemeiner; er verbessert die Leistung des Dijkstra-Algorithmus in einigen Situationen, was aber nicht immer der Fall ist; im allgemeinen Fall ist der Dijkstra-Algorithmus asymptotisch genauso schnell wie A*.

Der Dijkstra-Algorithmus hat 3 Argumente. Wenn Sie jemals ein Netzwerkverzögerungszeitproblem gelöst haben:

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:

Die Methode A* hat 2 zusätzliche Argumente:

 function aStar(graph, start, isGoal, distance, heuristic)
        queue  new PriorityQueue()
        queue.insert(start, 0)

        # hash table to keep track of the distance of each vertex from vertex "start", 
        #that is, the sum of the weight of edges that needs to be traversed to get from vertex start to each other vertex. 
        # Initializes these distances to infinity for all vertices but vertex start .
        distances[v]  inf ( v  graph | v <> start)

       # hash table for the f-score of a vertex, 
       # capturing the estimated cost to be sustained to reach the goal from start in a path passing through a certain vertex. Initializes these values to infinity for all vertices but vertex "start".
        fScore[v]  inf ( v  graph | v <> start)

        # Finally, creates another hash table to keep track, for each vertex u, of the vertex through which u was reached.
        parents[v]  null ( v  graph)

A* benötigt zwei zusätzliche Argumente, a distance function et un heuristic . Beide tragen zur Berechnung des sogenannten f-score bei. Dieser Wert ist eine Mischung aus den Kosten für das Erreichen des aktuellen Knotens u von der Quelle aus und den erwarteten Kosten, die erforderlich sind, um das Ziel von u aus zu erreichen.

Durch die Kontrolle dieser beiden Argumente können wir entweder BFS oder Dijkstra's Algorithmus (oder keines von beiden) erhalten. Für beide gilt, dass die heuristic muss eine Funktion sein, die identisch gleich 0 ist, etwa so

   lambda(v)  0 

Beide Algorithmen lassen nämlich jegliche Vorstellung von oder Informationen über die Entfernung der Eckpunkte zum Ziel völlig außer Acht.

Bei den Entfernungsmetriken stellt sich die Situation anders dar:

• Dijkstras Algorithmus verwendet das Gewicht der Kante als Entfernungsfunktion, daher müssen wir etwas übergeben wie

    distance = lambda(e)  e.weight 

• BFS berücksichtigt nur die Anzahl der durchlaufenen Kanten, was gleichbedeutend damit ist, dass alle Kanten das gleiche Gewicht haben, nämlich gleich 1! Und so können wir

    distance = lambda(e)  1 

A* gewinnt nur in einigen Kontexten einen Vorteil, in denen wir zusätzliche Informationen haben, die wir irgendwie nutzen können. Wir können A* nutzen, um die Suche schneller zum Ziel zu führen, wenn wir Informationen über die Entfernung von allen oder einigen Eckpunkten zum Ziel haben.

Beachten Sie, dass in diesem speziellen Fall der Schlüsselfaktor darin besteht, dass die Scheitelpunkte zusätzliche Informationen mit sich führen (ihre Position, die feststeht), die bei der Schätzung ihrer Entfernung zum endgültigen Ziel helfen können. Dies trifft nicht immer zu und ist bei allgemeinen Graphen in der Regel nicht der Fall. Anders ausgedrückt, die zusätzlichen Informationen stammen hier nicht aus dem Graphen, sondern aus dem Fachwissen.

The key, here and always, is the quality of the extra information 
captured by the Heuristic function: the more reliable and closer 
to real distance the estimate, the better A* performs.

Answer 5

Der Dijkstra-Algorithmus findet definitiv den kürzesten Weg. A* hingegen ist abhängig von der Heuristik. Aus diesem Grund ist A* schneller als Dijkstras Algorithmus und liefert gute Ergebnisse, wenn man eine gute Heuristik hat.