Der A-Stern-Algorithmus (A & ast;) ist ein Algorithmus, der verwendet wird, um das Problem des kürzesten Pfades in einem Graphen zu lösen. Dies bedeutet, dass bei einer Anzahl von Knoten und den Kanten zwischen ihnen sowie der “Länge” der Kanten (als “Gewicht” bezeichnet) und einer Heuristik (dazu später mehr) die A & ast; Der Algorithmus findet den kürzesten Weg vom angegebenen Startknoten zu allen anderen Knoten.

Beschreibung des Algorithmus

Das Grundprinzip des A-Stern-Algorithmus (A & ast;) besteht darin, den Knoten mit der aktuell kleinsten Priorität (der kürzesten Entfernung vom Start plus der Heuristik zum Ziel) iterativ zu betrachten und alle noch nicht besuchten Nachbarn zu aktualisieren, wenn der Pfad dazu über ist der aktuelle Knoten kürzer. Dies ist dem Dijkstra-Algorithmus sehr ähnlich, mit dem Unterschied, dass der Knoten mit der niedrigsten Priorität als nächstes besucht wird und nicht der Knoten mit der kürzesten Entfernung. Im Wesentlichen verwendet Dijkstra die Entfernung als Priorität, während A & ast; verwendet den Abstand plus der Heuristik.

Warum ist das Hinzufügen der Heuristik sinnvoll? Ohne sie hat der Algorithmus keine Ahnung, ob er in die richtige Richtung geht. Bei der manuellen Suche nach dem kürzesten Pfad in diesem Beispiel haben Sie wahrscheinlich Pfade nach rechts gegenüber Pfaden nach oben oder unten priorisiert. Dies liegt daran, dass sich der Zielknoten rechts vom Startknoten befindet, sodass das Gehen nach rechts zumindest im Allgemeinen die richtige Richtung ist. Die Heuristik gibt dem Algorithmus diese räumlichen Informationen.

Wenn also ein Knoten die derzeit kürzeste Entfernung hat, aber im Allgemeinen in die falsche Richtung geht, während Dijkstra diesen Knoten als nächstes besucht hätte, wird A Star dies nicht tun. Damit dies funktioniert, muss die Heuristik zulässig sein, was bedeutet, dass sie die tatsächlichen Kosten (d. H. Die Entfernung) niemals überschätzen darf - was beispielsweise für die geradlinige Entfernung in Straßennetzen der Fall ist. Intuitiv übersieht der Algorithmus auf diese Weise niemals einen kürzeren Pfad, da die Priorität immer niedriger als die tatsächliche Entfernung ist (Wenn der aktuell kürzeste Pfad A ist, wird Pfad B untersucht, wenn er auf irgendeine Weise kürzer sein könnte.) Eine einfache Heuristik, die diese Eigenschaft erfüllt, ist die geradlinige Entfernung (z. B. in einem Straßennetz).

Im Einzelnen führt dies zu den folgenden Schritten:

1. Initialisieren Sie den Abstand zum Startknoten als 0 und den Abstand zu allen anderen Knoten als unendlich
2. Initialisieren Sie die Priorität zum Startknoten als geradlinigen Abstand zum Ziel und die Prioritäten aller anderen Knoten als unendlich
3. Setzen Sie alle Knoten auf “nicht besucht”.
4. Während wir nicht alle Knoten besucht und den Zielknoten nicht gefunden haben:     1. Suchen Sie den Knoten mit der aktuell niedrigsten Priorität (beim ersten Durchgang ist dies der Quellknoten selbst).     1. Wenn es sich um den Zielknoten handelt, geben Sie dessen Entfernung zurück     1. Überprüfen Sie für alle Knoten daneben, die wir noch nicht besucht haben, ob die derzeit kleinste Entfernung zu diesem Nachbarn größer ist, als wenn wir über den aktuellen Knoten gehen würden     1. Wenn dies der Fall ist, aktualisieren Sie die kleinste Entfernung dieses Nachbarn auf die Entfernung von der Quelle zum aktuellen Knoten plus die Entfernung vom aktuellen Knoten zu diesem Nachbarn und aktualisieren Sie die Priorität auf die Entfernung plus die geradlinige Entfernung zu der Zielknoten

Beispiel des Algorithmus

Betrachten Sie das folgende Diagramm:

Die Schritte, die der Algorithmus in diesem Diagramm ausführt, wenn Knoten 0 als Startpunkt und Knoten 5 als Ziel in der angegebenen Reihenfolge angegeben werden, sind:

1. Besuch des Knotens 0 mit der derzeit niedrigsten Priorität von 8,0
2. Aktualisieren der Entfernung von Knoten 1 bis 3 und der Priorität auf 9.32455532033676
3. Aktualisieren der Entfernung von Knoten 2 bis 4 und der Priorität auf 10.32455532033676
4. Besuch von Knoten 1 mit der derzeit niedrigsten Priorität von 9.32455532033676
5. Aktualisieren der Entfernung von Knoten 3 auf 9 und der Priorität auf 11.82842712474619
6. Aktualisieren der Entfernung von Knoten 4 auf 13 und der Priorität auf 15.82842712474619
7. Besuch von Knoten 2 mit der derzeit niedrigsten Priorität von 10.32455532033676
8. Besuch von Knoten 3 mit der derzeit niedrigsten Priorität von 11.82842712474619
9. Aktualisieren der Entfernung von Knoten 5 auf 12 und der Priorität auf 12.0
10. Zielknoten gefunden!

Endgültig niedrigster Abstand von Knoten 0 zu Knoten 5: 12

Laufzeit des Algorithmus

Die Laufzeitkomplexität von A Star hängt davon ab, wie es implementiert wird. Wenn ein Min-Heap verwendet wird, um den nächsten zu besuchenden Knoten zu bestimmen, und die Adjazenz unter Verwendung von Adjazenzlisten implementiert wird, ist die Laufzeit O(| E | + | V | log | V|) (|V| = Nummer Anzahl der Knoten, |E| = Anzahl der Kanten). Wenn wir einfach alle Entfernungen durchsuchen, um den Knoten mit der niedrigsten Entfernung in jedem Schritt zu finden, und mithilfe einer Matrix nachsehen, ob zwei Knoten benachbart sind, steigt die Laufzeitkomplexität auf O(| V | ^ 2).

Beachten Sie, dass dies dasselbe ist wie bei Dijkstra. In der Praxis können jedoch bei Auswahl einer guten Heuristik viele der Pfade eliminiert werden, bevor sie untersucht werden, was zu einer signifikanten Zeitverbesserung führt.

Weitere Informationen darüber, wie die Heuristik die Komplexität beeinflusst, finden Sie im Wikipedia-Artikel.

Speicherkomplexität des Algorithmus

Die Speicherplatzkomplexität von A Star hängt davon ab, wie es ebenfalls implementiert ist, und entspricht der Laufzeitkomplexität sowie dem für die Heuristik erforderlichen Speicherplatz.