Der A*-Algorithmus („A Stern“ oder englisch „a star“, auch A*-Suche) gehört zur Klasse der informierten Suchalgorithmen. Er dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Er wurde das erste Mal 1968 von Peter Hart, Nils J. Nilsson und Bertram Raphael beschrieben. Der Algorithmus gilt als Verallgemeinerung und Erweiterung des Dijkstra-Algorithmus, in vielen Fällen kann aber umgekehrt A* auch auf Dijkstra reduziert werden.
Im Gegensatz zu uninformierten Suchalgorithmen verwendet der A*-Algorithmus eine Schätzfunktion (Heuristik), um zielgerichtet zu suchen und damit die Laufzeit zu verringern. Der Algorithmus ist vollständig und optimal. Das heißt, dass immer eine optimale Lösung gefunden wird, falls eine existiert.
Idee des Algorithmus Der A*-Algorithmus untersucht immer die Knoten zuerst, die wahrscheinlich schnell zum Ziel führen. Um den vielversprechendsten Knoten zu ermitteln, wird allen bekannten Knoten jeweils durch eine Metrik ein Wert zugeordnet, der eine Abschätzung angibt, wie lang der Pfad vom Start zum Ziel unter Verwendung des betrachteten Knotens im günstigsten Fall ist. Der Knoten mit dem niedrigsten -Wert wird als nächster untersucht.
Für einen Knoten bezeichnet die bisherigen Kosten vom Startknoten aus, um zu erreichen. bezeichnet die geschätzten Kosten von bis zum Zielknoten. Die verwendete Heuristik darf die Kosten nie überschätzen. Für das Beispiel der Wegsuche ist die Luftlinie eine geeignete Schätzung: Die tatsächliche Strecke ist nie kürzer als die direkte Verbindung.
Funktionsweise mini|Illustration der Wegfindung um ein Hindernis mittels A*-Suche. Bekannte Knoten sind hellblau umrandet, abschließend untersuchte Knoten sind ausgefüllt. Die Farbe letzterer markiert dabei die Entfernung zum Ziel; je grüner, desto weniger weit ist dieser vom Ziel entfernt. Zu beobachten ist, dass der A* zuerst in einer geraden Linie in Richtung Ziel strebt, bis er auf das Hindernis stößt. Erreicht er den Zielknoten, erkundet er zuerst noch alternative Knoten in der Open List, bevor er terminiert. Die Knoten werden während der Suche in drei verschiedene Klassen eingeteilt: unbekannte Knoten: Diese Knoten wurden während der Suche noch nicht gefunden. Zu ihnen ist noch kein Weg bekannt. Jeder Knoten (außer dem Startknoten) ist zu Beginn des Algorithmus unbekannt. bekannte Knoten: Zu diesen Knoten ist ein (möglicherweise suboptimaler) Weg bekannt. Alle bekannten Knoten werden zusammen mit ihrem -Wert in der sogenannten Open List gespeichert. Aus dieser Liste wird immer der vielversprechendste Knoten ausgewählt und untersucht. Die Implementierung der Open List hat großen Einfluss auf die Laufzeit und wird oft als einfache Prioritätswarteschlange (z. B. binärer Heap) realisiert. Zu Beginn ist nur der Startknoten bekannt. abschließend untersuchte Knoten: Zu diesen Knoten ist der kürzeste Weg bekannt. Die abschließend untersuchten Knoten werden in der sogenannten Closed List gespeichert, damit sie nicht mehrfach untersucht werden. Um effizient entscheiden zu können, ob sich ein Element auf der Closed List befindet, wird diese oft als Menge implementiert. Die Closed List ist zu Beginn leer.
Jeder bekannte oder abschließend besuchte Knoten enthält einen Zeiger auf seinen (bisher besten) Vorgängerknoten. Mit Hilfe dieser Zeiger kann der Pfad bis zum Startknoten rückverfolgt werden.
Wird ein Knoten abschließend untersucht (auch expandiert oder relaxiert), so werden seine Nachfolgeknoten in die Open List eingefügt und in die Closed List aufgenommen. Für neu eingefügte Nachfolgeknoten werden die Vorgängerzeiger auf gesetzt. Ist ein Nachfolgeknoten bereits auf der Closed List, so wird er nicht erneut in die Open List eingefügt und auch sein Vorgängerzeiger nicht geändert. Ist ein Nachfolgeknoten bereits auf der Open List, so wird der Knoten nur aktualisiert (-Wert und Vorgängerzeiger), wenn der neue Weg dorthin kürzer ist als der bisherige.
Falls der Zielknoten abschließend untersucht wird, terminiert der Algorithmus. Der gefundene Weg wird mit Hilfe der Vorgängerzeiger rekonstruiert und ausgegeben. Falls die Open List leer ist, gibt es keine Knoten mehr, die untersucht werden könnten. In diesem Fall terminiert der Algorithmus, da es keine Lösung gibt.
Bedingt durch die Vorgängerzeiger wird der gefundene Weg vom Ziel ausgehend rückwärts bis zum Start ausgegeben. Um den Weg in der richtigen Reihenfolge zu erhalten, kann z. B. vor der Wegsuche Start und Ziel vertauscht werden. Somit wird vom eigentlichen Ziel zum Start gesucht und die Wegausgabe beginnt beim ursprünglichen Startknoten.
Anmerkung: Die Closed List kann auch indirekt implementiert werden. Dazu speichern auch die abschließend untersuchten Knoten ihren -Wert. Wird nun ein abschließend untersuchter Knoten erneut gefunden, ist sein alter -Wert geringer als der neue, da der kürzeste Weg zu diesem Knoten bereits gefunden wurde. Der Knoten wird also nicht erneut in die Open List eingefügt. Wird keine Closed List benutzt, muss anderweitig sichergestellt werden, dass Knoten nicht mehrfach untersucht werden. Ansonsten wird die worst-case Laufzeit schlechter als quadratisch. Außerdem terminiert der Algorithmus nicht mehr, wenn es keine Lösung gibt. Die Knoten werden dann unendlich oft untersucht, da die Open List nie leer wird.
declare openlist as PriorityQueue with Nodes // Prioritätenwarteschlange declare closedlist as Set with Nodes
program a-star // Initialisierung der Open List, die Closed List ist noch leer // (die Priorität bzw. der f-Wert des Startknotens ist unerheblich) openlist.enqueue(startknoten, 0) // diese Schleife wird durchlaufen bis entweder // - die optimale Lösung gefunden wurde oder // - feststeht, dass keine Lösung existiert repeat // Knoten mit dem geringsten f-Wert aus der Open List entfernen currentNode := openlist.removeMin() // Wurde das Ziel gefunden? if currentNode == zielknoten then return PathFound // Der aktuelle Knoten soll durch nachfolgende Funktionen // nicht weiter untersucht werden, damit keine Zyklen entstehen closedlist.add(currentNode) // Wenn das Ziel noch nicht gefunden wurde: Nachfolgeknoten // des aktuellen Knotens auf die Open List setzen expandNode(currentNode) until openlist.isEmpty() // die Open List ist leer, es existiert kein Pfad zum Ziel return NoPathFound end
// überprüft alle Nachfolgeknoten und fügt sie der Open List hinzu, wenn entweder // - der Nachfolgeknoten zum ersten Mal gefunden wird, oder // - ein besserer Weg zu diesem Knoten gefunden wird function expandNode(currentNode) foreach successor of currentNode // wenn der Nachfolgeknoten bereits auf der Closed List ist – tue nichts if closedlist.contains(successor) then continue // g-Wert für den neuen Weg berechnen: g-Wert des Vorgängers plus // die Kosten der gerade benutzten Kante tentative_g = g(currentNode) + c(currentNode, successor) // wenn der Nachfolgeknoten bereits auf der Open List ist, // aber der neue Weg nicht besser ist als der alte – tue nichts if openlist.contains(successor) and tentative_g >= g(successor) then continue // Vorgängerzeiger setzen und g Wert merken oder anpassen successor.predecessor := currentNode g(successor) = tentative_g // f-Wert des Knotens in der Open List aktualisieren // bzw. Knoten mit f-Wert in die Open List einfügen f := tentative_g + h(successor) if openlist.contains(successor) then openlist.decreaseKey(successor, f) else openlist.enqueue(successor, f) end end
Anwendungsgebiete
Der A*-Algorithmus findet allgemein einen optimalen Pfad zwischen zwei Knoten in einem Graphen. Optimal kann dabei am kürzesten, am schnellsten oder auch am einfachsten bedeuten, je nach Art der Gewichtungsfunktion, die den Kanten ihre Länge zuordnet. Theoretisch kann der Algorithmus alle Probleme lösen, die durch einen Graphen dargestellt werden können und bei denen eine Schätzung über die Restkosten bis zum Ziel gemacht werden kann. Zu den Beschränkungen von A* siehe den Abschnitt Nachteile.
A* wird oft zur Wegsuche bei Routenplanern oder in Computerspielen benutzt. Als Heuristik wird dabei meist der Luftlinienabstand zum Ziel verwendet, da er auf Grund der Dreiecksungleichung stets optimistisch schätzt. Weitere Anwendungsgebiete sind Spiele wie das 15-Puzzle oder das Damenproblem, bei dem ein vorgegebener Zielzustand erreicht werden soll. Als Heuristik kann dabei die Anzahl der falsch platzierten Steine verwendet werden.
Beispiel 302px|mini|links|Landkarte als Graph (Angaben in Kilometern)
Im Beispiel soll der kürzeste Weg von Saarbrücken nach Würzburg gefunden werden. Das Diagramm zeigt eine kleine Auswahl an Städten und Wegen. Die Kantenbeschriftung entspricht den Kosten (hier: Entfernung in Kilometern), um von einer Stadt zur nächsten zu kommen. Jeder Knoten enthält die geschätzte Entfernung zum Zielknoten (Wert der -Funktion). Als Heuristik wird hier die Luftlinie verwendet.
Auf den Schritt-für-Schritt Bildern zeigt die Farbe eines Knotens seinen Status an: weiß: noch nicht gefunden grau: gefunden, befindet sich auf der Open List schwarz: untersucht, befindet sich auf der Closed List Sobald ein Knoten erreicht wurde, zeigt eine Kante auf den Vorgängerknoten. Für alle Knoten auf der Open List ist der -Wert angegeben.
302px|mini|links|Schritt 1: Der Startknoten Saarbrücken wurde erkundet.
Schritt 1: Es werden alle Nachfolgeknoten vom Startknoten Saarbrücken betrachtet: Kaiserslautern wird mit in die Open List eingefügt. (Die Kosten, um von Saarbrücken nach Saarbrücken zu kommen sind 0, die Kosten der Kante Saarbrücken–Kaiserslautern betragen 70, und die geschätzten Restkosten Kaiserslautern–Würzburg liegen bei 158. Dabei bezeichnet die Kosten der Kante zwischen den Knoten und .) Karlsruhe wird mit in die Open List eingefügt. Saarbrücken wird in beiden Knoten als Vorgängerknoten eingetragen. Der Knoten Saarbrücken ist nun abschließend betrachtet und wird auf die Closed List gesetzt. (Intuitiv: Es ist sinnlos, erst eine Weile umherzufahren, dabei wieder am Start anzukommen, dann irgendwann anzukommen und zu behaupten, das wäre der optimale Weg.)
302px|mini|links|Schritt 2: Kaiserslautern wurde erkundet.
Schritt 2: Die Open List enthält nun zwei Punkte. Da Kaiserslautern den geringeren -Wert hat, wird nun Kaiserslautern als Nächstes untersucht und seine Nachfolgeknoten betrachtet. (Der Weg über Kaiserslautern ist mindestens 228 km lang, der über Karlsruhe mindestens 285 km. Daher ist es am geschicktesten, zuerst Kaiserslautern genauer zu überprüfen.) Saarbrücken ist bereits auf der Closed List und wird nicht weiter betrachtet. Frankfurt wird mit in die Open List eingefügt. Die Kosten bis Frankfurt berechnen sich aus den Kosten bis Kaiserslautern plus die Kosten der zuletzt genutzten Kante (Kaiserslautern–Frankfurt). Kaiserslautern wird als Vorgängerknoten gespeichert. Ludwigshafen wird mit in die Open List eingefügt. Kaiserslautern wird als Vorgängerknoten gespeichert. Kaiserslautern wird auf die Closed List gesetzt.
302px|mini|links|Schritt 3: Ludwigshafen wurde erkundet.
Schritt 3: Der Knoten mit dem geringsten -Wert ist Ludwigshafen. (Die tatsächlichen Kosten von Ludwigshafen nach Würzburg (183 km) weichen deutlich von der Schätzung (108 km) ab, da in diesem Beispiel nur Autobahnen verwendet werden sollen.) Kaiserslautern ist bereits auf der Closed List und wird nicht weiter betrachtet. Der Zielknoten Würzburg wird gefunden, aber noch nicht als Lösung ausgegeben, sondern zunächst in die Open List eingefügt. Ludwigshafen wird als Vorgängerknoten gespeichert. Ludwigshafen wird auf die Closed List gesetzt.