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

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 den Gewichten der Verbindungen zu diesem Knoten und den Kosten, die Sie hatten, um den vorherigen Knoten zu erreichen.
Zusätzlich schätzen Sie die Kosten vom neuen Knoten zum Zielknoten und fügen diese zum csf hinzu. Sie haben nun die geschätzten Gesamtkosten (etc). (etc = csf + geschätzte Entfernung zum Ziel) Als Nächstes wählen Sie unter den neuen Knoten denjenigen mit den niedrigsten etc.
Gehen Sie genauso vor wie zuvor, bis eine der neue Knotenpunkte wird das Ziel sein.

Dijkstra funktioniert fast genauso. Nur dass der geschätzte Abstand zum Ziel immer 0 ist und der Algorithmus erst anhält, wenn das Ziel nicht nur eine der neue Knotenpunkte sondern auch derjenige mit dem niedrigsten csf.

A* ist in der Regel schneller als Dijstra, was aber nicht immer der Fall ist. In Videospielen bevorzugt man oft den Ansatz "nah genug für ein Spiel". Daher ist der "nahe genug" optimale Pfad von A* normalerweise ausreichend.

Answer 2

Dijkstras Algorithmus ist definitiv vollständig und optimal, so dass Sie immer den kürzesten Weg finden werden. Allerdings dauert er in der Regel länger, da er hauptsächlich zur Ermittlung mehrerer Zielknoten verwendet wird.

A* search auf der anderen Seite geht es um heuristische Werte, die Sie definieren können, um Ihr Ziel näher zu erreichen, wie z.B. die Manhattan-Distanz 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.