A*-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Der A*-Algorithmus (a-star) 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 Nilsson und Bertram Raphael beschrieben. Beim A*-Algorithmus handelt es sich um eine sogenannte informierte Suche, was heißt, dass der Algorithmus auf eine Heuristik zurückgreift, um zielgerichtet zu suchen, wodurch er – im Gegensatz zu uninformierten Suchalgorithmen – zuerst jene Knoten untersucht, welche am wahrscheinlichsten zum Ziel führen.
Inhaltsverzeichnis |
[Bearbeiten] Allgemeines
Die Besonderheit des A*-Algorithmus ist, dass er im Gegensatz zu den uninformierten Suchalgorithmen zielgerichtet sucht. Er betrachtet von den vielen möglichen Knoten, die zum Ziel führen könnten, tatsächlich nur sehr wenige, und findet das Ziel daher im allgemeinen sehr schnell.
Die Abschätzung, welche Knoten am wahrscheinlichsten zum Ziel führen, liefert jedoch erst eine Heuristik, die Annahmen über den Graphen, auf dem der A*-Algorithmus angewendet werden soll, ermöglicht. Der Algorithmus arbeitet hierbei umso effizienter, je genauer die von der Heuristik für einen Knoten geschätzten Kosten bis zum Ziel den tatsächlichen Kosten von diesem Knoten zum Ziel entsprechen.
Fordert man von der Heuristik, dass sie monoton ist, also den tatsächlichen Weg zwischen zwei Knoten nie überschätzt, so kann man beweisen, dass der A*-Algorithmus tatsächlich immer einen kürzesten Weg findet. Dies bedeutet jedoch im Umkehrschluss auch, dass der Algorithmus nicht mit Sicherheit den kürzesten Weg zum Ziel findet, falls man eine sehr schlechte Heuristik verwendet. Ein formaler Beweis der Optimalität des Algorithmus findet sich im Abschnitt Optimalitätsbeweis weiter unten im Artikel.
Anmerkung: Modifiziert man den A*-Algorithmus geringfügig, so reicht es aus, eine zulässige Heuristik – welche die Kosten von einem Knoten bis zum Ziel nie überschätzt – zu verwenden, um immer einen kürzesten Pfad zu finden. Eine genauere Beschreibung der Unterschiede zwischen monotonen und zulässigen Heuristiken findet sich im Abschnitt Heuristiken weiter unten im Artikel.
[Bearbeiten] Funktionsweise
Wendet man den A*-Algorithmus auf einem Knoten u an, so wird für jeden von diesem Knoten aus erreichbaren Nachbarn durch die Heuristik eine Schätzung abgegeben, wie teuer es ist, von diesem aus zum Ziel zu kommen. Für jeden dieser Nachbarknoten v addiert der A*-Algorithmus nun die von der Heuristik geschätzten Kosten bis zum Ziel zu den Kosten, um vom Knoten u zu eben jenem Knoten v zu kommen. Die Vorgehensweise des Algorithmus lässt sich dabei durch folgende Gleichung beschreiben:
f(v) = g(v) + h(v)
Hierbei steht g(v) für die bisherigen gesamten Wegkosten vom Start zum Knoten v, h(v) für die von der Heuristik für Knoten v geschätzten Kosten bis zum Ziel, und f(v) steht demnach für die geschätzten Gesamtkosten, um vom Startknoten über v zum Ziel zu gelangen. Im nächsten Schritt wird nun der Knoten weiter untersucht, der den geringsten f-Wert besitzt.
[Bearbeiten] Algorithmus
Der A*-Algorithmus erhält vier Eingaben: Den Graph (G), auf welchem er laufen soll, den Startknoten (s), von dem aus die Suche gestartet werden soll, der Zielknoten (g), zu dem ein kürzester Pfad gefunden werden soll und die Heuristik (h), welche für jeden Knoten die Entfernung bis zum Ziel abschätzt. Als Datenstruktur braucht er außerdem eine Prioritätswarteschlange (Q), in der er die noch nicht besuchten Knoten speichert.
Im ersten Schritt wird der Graph initialisiert wobei die Entfernungen zu allen Knoten auf unendlich gesetzt werden, und die Entfernung zum Startknoten auf Null gesetzt wird. Danach werden alle Knoten des Graphen in die Prioritätswarteschlange eingefügt, und eine Schleife gestartet, welche solange läuft, bis entweder ein kürzester Pfad zum Ziel gefunden wurde oder jeder Knoten bereits einmal betrachtet wurde. Tritt der zweite Fall ein, so kann man daraus schließen, dass kein Pfad zwischen dem Start- und Zielknoten existiert.
Innerhalb der Schleife wird zuerst der erste Knoten der Prioritätswarteschlange entfernt, welcher – da es sich um eine Prioritätswarteschlange handelt – auch genau der Knoten mit dem niedrigsten f-Wert ist. Dieser Knoten wird nun in die Liste der besuchten Knoten eingetragen, und es wird überprüft ob man den Algorithmus eventuell schon abbrechen kann. Der Algorithmus kann hier aus zweierlei Gründen abgebrochen werden: Einerseits kann es sein, dass der eben besuchte Knoten schon einmal besucht wurde, was aufgrund der monotonen Heuristik jedoch eigentlich nicht hätte passieren dürfen. Expandiert der A* Algorithmus einen Knoten trotzdem zum zweiten mal, so kann es keinen Weg vom Start zum Ziel geben, da dieser Weg sonst vorher gefunden worden wäre. Eine genauere Begründung findet man unter Optimalitätsbeweis weiter unten im Artikel.
Terminiert der Algorithmus, weil er das Ziel gefunden hat, so wird die Hilfsfunktion reconstruct_shortest_path aufgerufen, welche ihrerseits vom Zielknoten aus rückwärts den Pfad zum Startknoten berechnet. Hierzu bekommt die Funktion den Startknoten, den Zielknoten und den Graph übergeben, und folgt nun Schritt für Schritt vom Zielknoten startend den Vorgängerzeigern. Diese Zeiger wurden, während der Algorithmus Knoten expandiert hat, in den Graph geschrieben, sodass die Funktion reconstruct_shortest_path für einen Knoten v nur noch direkt aus dem Graph ablesen muss von welchem Knoten u aus v besucht wurde. Nachdem nun der Vorgänger bestimmt wurde, wird dieser in einem Stack gespeichert. reconstruct_shortest_path berechnet solange rekursiv den Vorgänger dieses Vorgängers, bis die Berechnung beim Startzustand angekommen ist. Sobald dies der Fall ist, kann der Stack – welcher nun den kürzesten Pfad vom Start zum Ziel in der richtigen Reihenfolge enthält – direkt zurückgegeben werden.
Sollte im A*-Algorithmus das Ziel jedoch noch nicht gefunden worden sein, so werden nun alle vom aktuellen Knoten u aus direkt erreichbaren Knoten bestimmt, und die Kanten zu diesen Knoten relaxiert. Bei diesem Schritt wird für jeden der entdeckten Knoten v geprüft ob der gerade entdeckte Pfad besser ist als der bereits bekannte. Falls dies der Fall ist, wird sowohl gespeichert von welchem Knoten aus v gerade erkundet wurde (Vorgängerzeiger), als auch sein f-Wert nach der Formel f(v) = g(u) + w(u,v) + h(v) angepasst. Den Wert für g(u) kann man hierbei genau wie das Gewicht der Kante zwischen u und v direkt aus dem Graph ablesen. Die Berechnung von h(v) ist einfach, da sie dem A*-Algorithmus direkt mitgeliefert wird.
Anmerkung: Neben der hier vorgestellten Methode den A*-Algorithmus zu Implementieren gibt es häufig auch noch Implementierungen welche eine sogenannte Closed List von bereits besuchten Knoten mitführen welche sie in jedem Schritt überprüfen. Dies ist nötig falls eine Heuristik verwendet werden soll welche zwar zulässig aber nicht monoton ist. Da diese Implementierung jedoch davon ausgeht, dass eine monotone Heuristik verwendet wird, ist der erste genutzte Pfad der zu einem beliebigen Knoten welcher expandiert wird führt auf jeden Fall auch der kürzeste Pfad zu diesem Knoten. Somit ist es nicht nötig die Pfadkosten entdeckter Knoten eventuell später ein zweites mal mit den Pfadkosten, welche die Knoten bei ihrer ersten Entdeckung hatten, zu vergleichen, da die Pfadkosten bei der ersten Entdeckung garantiert niedriger waren. Die genauen Unterschiede zwischen einer monotonen Heuristik und einer zulässigen Heuristik findet man weiter unten unter Heuristiken im Artikel.
/*
* Rekonstruktion des kürzesten Pfades
* -----------------------------------
* p: berechneter kürzester Pfad
* n: Zielknoten
*/
reconstructShortestPath (n)
{
p := new stack; // leer initialisieren
// Prüfe ob schon beim Startknoten angekommen
while (π(n) != NIL))
{
// Füge Knoten dem Pfad hinzu
push(n, p);
// Mache dasselbe für den Vorgängerknoten
n := π(n);
}
// Liefere den gefundenen Pfad zurück
return p;
}
/*
* Initialisieren des Graphen
* --------------------------
* G: Zu untersuchender Graph
* s: Startknoten
*/
initialize(G, s)
{
// Setze Entfernung zu allen Knoten auf Unendlich
forall v do
d[v] := ∞
// Setze Entfernung zum Startknoten auf Null
d[s] := 0;
}
/*
* Relaxieren einer Kante
* ----------------------
* u: Knoten der gerade expandiert wurde
* v: Aktuell betrachteter Nachfolger von u
* w: Gewichtsfunktion zum Berechnen der Kosten für eine Kante
* f: Kombination der Abstandsfunktion d mit der Heuristik h (f[v] = d[v] + h[v])
*/
relax(u,v,w,h)
{
// Prüfe ob der Weg über u zu v kürzer ist als der aktuelle
if f[v] > d[u] + w(u,v) + h[v] {
// Neuer weg kürzer als bisher gefundener Weg
// Aktualisiere geschätzte restliche Weglänge
f[v] := d[u] + w(u,v) + h[v];
// Aktualisiere Vorgänger in kürzestem Pfad
π[v] := u;
}
else
; // Ändere nichts, da bereits besserer Pfad bekannt
}
/* * Der eigentliche A*-Algorithmus * ------------------------------ * G: Zu untersuchender Graph * s: Startknoten * g: Der Zielknoten * w: Gewichtsfunktion zum Berechnen der Kosten für eine Kante * f: Kombination der Abstandsfunktion d mit der Heuristik h (f[v] = d[v] + h[v]) * Q: Prioritätswarteschlange der Knoten, deren f-Wert bereits bekannt ist */ A-Star (s, g, w, h, G) { 01 initialize(G, s); 02 Q := V[G]; // Füge alle Knoten aus dem Graph in die Warteschlage ein 03 while not isEmpty(Q) { 04 // Betrachte Knoten mit geringsten Abstand zum Startknoten 05 u := pop(Q); 06 if (u == g) then 07 return reconstructShortestPath(g); 08 else { 09 // Betrachte alle vom aktuellen Knoten u aus erreichbaren Knoten (Nachfolger) 10 forall v := sucessors(u) do { 11 // relaxiere die Kante zwischen u und seinem Nachfolger 12 relax(u, v, w, h); 13 } 14 } 15 } 15 // Es konnte kein Pfad gefunden werden 16 return fail; 17 }
[Bearbeiten] Beispiel
 Ein Beispiel für die Anwendung des A*-Algorithmus ist die Suche nach einem kürzesten Pfad auf einer Landkarte. (Im Beispiel will man in Deutschland einen kürzesten Pfad von Frankfurt nach München finden.) Zuerst muss man eine für das Problem geeignete Heuristik finden, welche zwar möglichst genau an die tatsächlichen Kosten zwischen zwei Knoten herankommt, aber immer unter den tatsächlichen Kosten bleibt. Da in diesem Beispiel der kürzeste Weg zwischen zwei Städten berechnet werden soll, bietet sich die Luftlinie zwischen den beiden Städten als Schätzfunktion an. Jeder Weg zwischen zwei Städten wird immer mindestens genauso lang sein wie die Luftlinie zwischen den beiden Städten und im Allgemeinen werden die Straßen zwischen zwei Städten relativ direkt gebaut sein, so dass der tatsächlich zurückzulegende Weg nicht sehr viel länger sein sollte als die Luftlinie. Schreibt man nun also die geschätzten Kosten für die Entfernungen aller Städte nach München auf, so ergeben sich die folgenden Werte, welche im Beispiel die Kosten für die Funktion h(v) sein werden. Augsburg <--> München: 43 km Erfurt <--> München: 342 km Frankfurt <--> München: 353 km Karlsruhe <--> München: 260 km Kassel <--> München: 446 km Mannheim <--> München: 311 km München <--> München: 0 km Nürnberg <--> München: 151 km Stuttgart <--> München: 199 km Würzburg <--> München: 229 km Weiterhin braucht man noch die Kosten sämtlicher Pfade zwischen zwei Städten, um sukzessive für eine Stadt u berechnen zu können wie teuer es vom Start aus war, zu dieser Stadt zu kommen. Diese Werte werden später für die Funktion g(u) benötigt und lassen sich am besten aus der oben gegebenen Landkarte für dieses Beispiel ableiten. Anmerkung: Im folgenden Beispiel ist die Zahl in Klammern hinter dem Namen der Stadt bereits der fertig berechnete Wert f(v) für die entsprechende Stadt v, welcher sich aus Wegstrecke von Frankfurt bis zur Stadt v und den geschätzten Kosten von dieser Stadt bis nach München zusammensetzt.
[Bearbeiten] ZeitkomplexitätDie Zeitkomplexität des A*-Algorithmus hängt sehr stark von der Datenstruktur ab, welche man verwendet um die noch nicht besuchten Knoten Q zu speichern. Verwendet man hier einen Fibonacci-Heap, so hat der Algorithmus insgesamt eine Laufzeit von Diese Laufzeit ergibt sich wie folgt: In der zweiten Zeile wird die Prioritätswarteschlange mit allen Knoten aus dem Graph gefüllt. Um Insgesamt ergibt sich somit eine Komplexität von [Bearbeiten] HeuristikenMan unterscheidet zwei Arten von Heuristiken für den A*-Algorithmus: Zulässige und monotone Heuristiken. Zulässige Heuristiken dürfen zwar nie die Kosten bis zum Ziel, aber sehr wohl die Kosten von einem Knoten zum nächsten, überschätzen. Monotone Heuristiken dürfen weder die einen noch die anderen Kosten überschätzen; Monotonie ist also eine stärkere Eigenschaft als die der Zulässigkeit. Es ist zwar möglich, Heuristiken zu konstruieren, die zulässig aber nicht monoton sind, jedoch kommen diese Heuristiken in der Praxis sehr selten vor. Die Heuristik zur Abschätzung der Entfernung zweier Städte – die Luftlinie – ist zum Beispiel monoton: Man kann keinen Weg von der einen Stadt zur anderen finden, der kürzer wäre als die Luftlinie der betrachteten Städte. Die wichtigste Konsequenz dieser Unterscheidung beider Heuristiken tritt bei der Implementierung des A*-Algorithmus zu Tage: Sollte man nur eine zulässige Heuristik verwenden, so kann es passieren, dass die Entfernung zwischen zwei Knoten u und v überschätzt wird, und der Algorithmus somit den Knoten v auf einem Umweg über den Knoten w erreicht. Dies hat nun aber zur Folge, dass die berechnete Entfernung zwischen u und v nicht optimal ist, da der Weg über w nach Annahme ein Umweg war. Lässt man den Algorithmus noch einige Zeit laufen, so wird er jedoch auch die direkte Verbindung zwischen u und v finden, wodurch nun zwei Pfade gefunden wurden um von u nach v zu kommen. Da die gewählte Heuristik aber nur zulässig und nicht monoton war, kann nicht mehr garantiert werden, dass der erste gefundene Pfad zum Knoten v tatsächlich der kürzeste war. Somit muss man nun die Kosten für die beiden Pfade um von u nach v zu kommen vergleichen, um am Ende den Pfad zu wählen welcher kürzer war. Wählt man jedoch eine monotone Heuristik, so ist dieser Schritt unnötig, da der erste entdeckte Pfad zu einem Knoten v auf jeden Fall auch der kürzestmögliche Pfad ist. Die gewählte Heuristik hat ebenfalls große Auswirkungen auf die Laufzeit des A*-Algorithmus. Auf der einen Seite gibt es die perfekte Heuristik, welche in jedem Schritt die tatsächlichen Kosten für einen Knoten bis zum Ziel als Schätzwert abgibt, wodurch der A*-Algorithmus nur die Knoten erkunden wird, welche auch tatsächlich auf dem kürzesten Pfad liegen. Eine solch genaue Heuristik ist aber sinnlos, und in der Berechnung extrem teuer, da man für sie erst einmal für jeden Knoten den kürzesten Pfad bis zum Ziel finden muss, was genau der ursprünglich zu lösenden Problemstellung entspricht. Auf der anderen Seite gibt es extrem schlechte aber dafür sehr einfach zu berechnende Heuristiken. So kann man die Entfernung zwischen zwei Knoten mit Kosten von 0 schätzen, wodurch effektiv gar keine Heuristik mehr verwendet wird, und der A*-Algorithmus alle Knoten blind untersuchen muss, bis er irgendwann auf diese Weise das Ziel findet. Diese Version des Algorithmus ist besser als der Algorithmus von Dijkstra bekannt. Eine gute Heuristik stellt somit einen Kompromiss zwischen dem Berechnungsaufwand für die Heuristik und ihrer Genauigkeit dar. [Bearbeiten] OptimalitätsbeweisWie bereits erwähnt ist eine gute Heuristik eine der wichtigsten Voraussetzungen damit der A*-Algorithmus effizient arbeiten kann. Setzt man weiterhin voraus, dass die verwendete Heuristik monoton ist – also sowohl die Kosten bis zum Ziel, als auch die Kosten zwischen zwei beliebigen Knoten nie überschätzt – und dass der Graph keine negativen Kantengewichte besitzt, so kann man beweisen dass der A*-Algorithmus immer einen kürzesten Pfad vom Start zum Ziel findet. Betrachtet man die Vorgehensweise des Algorithmus, so sieht man, dass immer erst jene Knoten u betrachtet werden welche die niedrigsten f-Kosten haben. Da die Heuristik, welche zur Berechnung der f-Kosten herangezogen wird, aber nach Voraussetzung die tatsächlichen Kosten nie überschätzt, und die Kosten, um zu dem aktuell zu schätzenden Knoten u zu kommen, bekannt sind (da der Algorithmus schon einen Weg vom Startknoten zu u gefunden hat), ist auch der endgültige f-Wert für u eine optimistische Schätzung, welche garantiert nicht über den tatsächlichen Kosten liegen wird. Gibt es nun einen Knoten a mit f(a) = 450, so wird dieser Knoten erst weiter erkundet wenn alle anderen Knoten x erkundet wurden für die gilt f(x) < 450. Somit kann der Algorithmus keine Knoten auslassen welche schneller zum Ziel führen könnten. Würde man jedoch negative Kantengewichte zulassen, so könnten hinter dem Knoten mit Kosten von 450 durchaus noch weitere Knoten existieren welche – durch negative Kantengewichte – f-Kosten von weniger als 450 haben. Schreibt man diese Überlegungen nun formal auf, so ergibt sich der formale Beweis der Optimalität des A*-Algorithmus: Zu zeigen: Der A*-Algorithmus findet immer einen kürzesten Pfad Annahme: Der A*-Algorithmus findet eine suboptimale Lösung G2, wobei die optimale Lösung G1 Kosten von C1 hat. Da für alle Zielknoten gilt dass die geschätzte Entfernung vom Zielknoten bis zum Zielknoten 0 ist, gilt insbesondere: h(G2) = 0 Da G2 nach Annahme eine suboptimale Lösung ist gilt nun aber folgende Gleichung: f(G2) = g(G2) + h(G2) = g(G2) > C1 Betrachtet man nun einen beliebigen Knoten n auf dem kürzesten Pfad zum optimalen Ziel G1 und die Tatsache dass die Heuristik die tatsächlichen Kosten niemals überschätzt, gilt: f(n) = g(n) + h(n) ≤ C1 Fasst man nun die beiden Gleichungen zusammen, so erhält man: f(n) ≤ C1 < f(G2) Dies bedeutet aber nun dass der A*-Algorithmus den Knoten G2 niemals erkundet bevor er die optimale Lösung (G1) findet. Somit findet der Algorithmus zuerst die Lösung G1, und berechnet damit tatsächlich einen kürzesten Pfad. [Bearbeiten] AnwendungsgebieteAnwendung findet der A*-Algorithmus bei der Berechnung eines kürzesten Pfades zwischen zwei Punkten, wie zum Beispiel bei der Wegberechnung eines Routenplaners in einem Auto oder via Internet. Auch in Computerspielen wird der Algorithmus häufig verwendet, zum Beispiel, wenn der Spieler einer Einheit den Befehl gibt zu einem bestimmten Punkt zu gehen, und somit ein Weg für diese Einheit berechnet werden muss. Dieses Beispiel kann man auch auf Roboter oder Software-Agenten, welche selbstständig einen Weg in einer vorgegebenen Welt finden sollen, verallgemeinern. [Bearbeiten] Andere Verfahren zur Berechnung kürzester PfadeHat man keine Heuristik, um die Entfernung der Knoten abzuschätzen, kann man statt des A*-Algorithmus den Algorithmus von Dijkstra verwenden. Um alle kürzesten Pfade von einem Knoten zu allen anderen Knoten in einem Graph mit negativen Kantengewichten zu berechnen, kann der Bellman-Ford-Algorithmus verwendet werden. Sucht man nicht nur die kürzesten Pfade eines Knotens zu allen anderen Knoten im Graph, sondern die kürzesten Pfade zwischen allen Knotenpaaren, so kann man den Algorithmus von Floyd und Warshall verwenden. [Bearbeiten] Literatur
[Bearbeiten] Weblinks
|
viele Knoten in einer durch einen Fibonacci Heap dargestellten Prioritätswarteschlange zu speichern benötigt man Zeit 
. In der dritten Zeile wird eine Schleife gestartet, welche im schlimmsten Fall 
kostet. Die zehnte Zeile kostet Schlussendlich noch einmal Laufzeit 
, da jeder Knoten nur einmal betrachtet wird, und somit auch jede Kante nur einmal betrachtet werden kann, weswegen relax insgesamt maximal 
