Dijkstra und A* kürzester Weg

Die in diesem Blog verfassten Artikel wurden mit dem Ziel erstellt, zu unterrichten. Außerdem können die Informationen im Artikel falsch sein, also seien Sie bitte vorsichtig.

Wenn die Bewegungskosten für jedes Feld unterschiedlich sind, kann einfaches BFS allein nicht die günstigste Route garantieren. Derzeit werden Kürzeste-Pfad-Algorithmen wie Dijkstra und A* verwendet.

Dijkstra

Der Scheitelpunkt mit den niedrigsten kumulierten Kosten vom Startpunkt bis zur Gegenwart wird zuerst erweitert.

Neue Kosten = aktuelle Kosten + nächste Amtsleitungskosten

Wenn die neuen Kosten geringer sind als der alte Datensatz
Entfernung und vorherige Scheitelpunkte aktualisieren.

Im Allgemeinen bei Verwendung der PrioritätswarteschlangeO((V + E) log V)Insofern ist es umsetzbar. Der Standard-Dijkstra sollte nicht verwendet werden, da das Vorhandensein negativer Kanten den bereits festgelegten kürzesten Abstand verringern kann.

A*

A* sind die tatsächlichen Kosten ab dem Startpunktgund die geschätzten Kosten, um das Ziel zu erreichen.hHinzufügen, um Prioritäten festzulegen.

f(n) = g(n) + h(n)

In Gittern kann die Manhattan-Distanz oder die euklidische Distanz als Heuristik verwendet werden. Für hexagonale Gitter muss eine für hexagonale Koordinaten geeignete Abstandsfunktion verwendet werden.

Der kürzeste Weg kann garantiert werden, wenn die geschätzten Kosten die tatsächlich niedrigsten verbleibenden Kosten nicht überschätzen. Wenn Heuristic 0 ist, verhält sich A* wie Dijkstra.

Welches soll ich verwenden?

Erfordert mehrere Zielkosten von einem Ausgangspunkt: Dijkstra
Navigieren Sie schnell zu einem Ziel: A*
Alle Trunk-Kosten sind gleich: BFS

Die Leistung der Pfadsuche wird nicht allein durch den Namen des Algorithmus bestimmt. Außerdem müssen die Kosten für die Erzeugung von Nachbarn, die Darstellung von Hindernissen, die Prioritätswarteschlange und die Qualität der Heuristik überprüft werden.