A*-Algorithmus
Der A*-Algorithmus 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 Nilson 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.
Allgemeines
Das Besondere am A*-Algorithmus ist, dass er – im Gegensatz zu den uninformierten Suchalgorithmen – zielgerichtet sucht, wodurch von den vielen möglichen Knoten, welche man – um vom Startknoten zum Endknoten zu kommen – betrachten kann, nur sehr wenige tatsächlich betrachtet werden, weswegen der Algorithmus das Ziel im Allgemeinen sehr schnell findet.
Die Abschätzung welche Knoten am wahrscheinlichsten zum Ziel führen kann jedoch erst durch eine Heuristik, mittels derer man Annahmen über den Graphen, auf dem der A*-Algorithmus angewendet werden soll, erreicht werden. Der Algorithmus arbeitet hierbei umso zielgerichteter, 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.
Stellt man die Anforderung an die Heuristik, dass diese 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, falls man eine sehr schlechte Heuristik verwendet, nicht unbedingt den kürzesten Weg zum Ziel finden muss. Einen Formalen Beweis zur Optimalität des Algorithmus findet man unter Optimalitätsbeweis weiter unten im Artikel.
Anmerkung: Modifiziert man den A*-Algorithmus etwas, so reicht es auch 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 Betrachtung der Unterschiede zwischen monotonen und optimistischen Heuristiken findet man unter Heuristiken weiter unten im Artikel.
Funktionsweise
Wendet man den A*-Algorithmus auf einem Knoten u an, so werden zuerst alle von diesem Knoten aus erreichbaren Nachbarn berechnet. Danach wird durch die Heuristik für jeden dieser Nachbarn eine Schätzung abgegeben wie teuer es ist von ihm 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 h(v) für die von der Heuristik für Knoten v geschätzten Kosten bis zum Ziel, g(v) für die bisherigen gesamten Wegkosten um vom Knoten bei dem man den A*-Algorithmus gestartet hat zum Knoten v zu kommen, und f(v) steht für die wahrscheinlich zu erwartenden Kosten wenn man vom Startknoten aus über seine aktuelle Position (u) zu dem entsprechenden Nachbarn (v) weitergeht um von dort aus irgendwie weiter zum Ziel zu gelangen. Im nächsten Schritt wird nun der Knoten weiter untersucht, welcher den geringsten f-Wert besitzt. BeispielEin 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 eine 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, sodass 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 folgen 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.
AlgorithmusDer A*-Algorithmus braucht um einen kürzesten Weg zu finden und zurückzugeben fünf Eingaben: Den Graph (graph) auf welchem er laufen soll, den Startknoten (start) von dem aus die Suche gestartet werden soll, der Zielknoten (goal) zu dem ein kürzester Pfad gefunden werden soll, eine Prioritätswarteschlange (S) welche alle Knoten speichert die der Algorithmus bereits kennt (und deren f-Werte daher bereits bekannt sind) aber noch nicht besucht hat, und die Heuristik h welche für jeden Knoten die Entfernung bis zum Ziel abschätzt. Im ersten Schritt wird nun der Startknoten in die Prioritätswarteschlange eingefügt, und danach eine Schleife gestartet welche solange läuft bis entweder ein kürzester Pfad zum Ziel gefunden wurde, oder keine weiteren Knoten mehr zur Expansion zur Verfügung stehen, und somit 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 weil man das Ziel bereits gefunden hat. Ist dies der Fall, 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 wurde 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, und reconstruct_shortest_path berechnet rekursiv den Vorgänger dieses Vorgängers, solange 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 mittels der Funktion expand alle vom aktuellen Knoten aus direkt erreichbaren Knoten bestimmt. Bei diesem Schritt wird auch für jeden der neu Entdeckten Knoten gespeichert von welchem Knoten aus er gefunden wurde. Somit kann man, wenn der Knoten selbst später einmal expandiert, wird diese Information über den Vorgänger direkt in den Graph schreiben. Da diese Implementierung des A*-Algorithmus auf einer monotonen Heuristik aufbaut ist der erste zu jedem Knoten gewählte Pfad optimal, womit diese Methode, den Vorgänger endgültig festzulegen sobald der Knoten expandiert wird, sicher ist. Nun werden für alle neu Entdeckten Knoten noch die f-Kosten berechnet, wobei diese Berechnung nach der Anfangs bereis genannten Formel f(n) = g(n) + h(n) für einen Knoten n erfolgt. Der Wert für g(n) kann hierbei direkt aus dem Graph abgelesen werden, und untspricht dem Gewicht der Kante zwischen dem aktuellen und dem gerade gefunden Knoten, und die Funktion h(n) wird dem A*-Algorithmus mitgeliefert. Schlussendlich werden alle neu Entdeckten Knoten in die Prioritätswarteschlange einsortiert, die Schleife beginnt von vorne, und es wird wieder der Knoten mit den geringsten f-Kosten aus der Prioritätswarteschlange betrachtet. 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 führt auf jeden Fall auch der kürzeste Pfad zu diesem Knoten. Somit ist es nicht nötig die Pfadkosten eventuell später ein zweites mal entdeckter Knoten 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. /* * Algorithmus zur Rekonstruktion des kürzesten Pfades * --------------------------------------------------- * P: berechneter kürzester Pfad * start: Startknoten * node: Zielknoten */ reconstruct_shortest_path (start, node, graph) { if (node != start) { push(node, P); /* * Der eigentliche A*-Algorithmus * ------------------------------ * graph: Zu untersuchender Graph * start: Startknoten * goal: Der Zielknoten * h: Heuristikfunktion zum Schätzen des Abstandes eines Knotens bis zum Ziel * S: Prioritätswarteschlange der Knoten, deren f-Wert bereits bekannt ist */ A-Star (graph, start, goal, h, S) { insert (start,S); while not isEmpty(S) { current_node := pop(S); insert (current_node, N); if (current_node == goal) then return reconstruct_shortest_path(start,goal, graph); else { // Finde alle vom aktuellen Knoten aus erreichbaren Knoten successors := expand(current_node, graph); HeuristikenBei Heuristiken für den A*-Algorithmus unterscheidet man zwischen zwei Sorten: Einmal die zulässigen Heuristiken, welche zwar die Kosten bis zum Ziel nie überschätzen, aber die Kosten um von einem Knoten zum nächsten zu kommen durchaus überschätzen dürfen, und die monotonen Heuristiken auf der anderen Seite, welche nicht nur die Entfernung bis zum Ziel nie überschätzen, sondern auch die Kosten zwischen zwei Knoten immer unterschätzen. Wenn eine Heuristik monoton ist, so ist dies also eine stärkere Aussage ,als wenn sie nur zulässig wäre. Es ist zwar möglich Heuristiken zu konstruieren welche zwar monoton aber nicht zulässig sind, jedoch sind diese Heuristiken in der Regel sehr selten. Die Heuristik um die Entfernung zwischen zwei Städten zu schätzen – die Luftlinie zwischen diesen beiden Städten – ist zum Beispiel monoton. So kann man keinen Weg finden um von einer Stadt in eine andere zu kommen, der kürzer wäre als die direkte Luftlinie zwischen diesen beiden Städten. Die wichtigste Konsequenz dieser Unterscheidung bei der 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 vtatsä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 von 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 in der Berechnung extrem teuer, da man dazu erst einmal für jeden Knoten den kürzesten Pfad bis zum Ziel finden muss. 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 durch Zufall 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. 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 verwedete 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 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 , und berechnet damit tatsächlich einen kürzesten Pfad. AnwendungsgebieteDer A*-Algorithmus wird beim Finden von kürzesten Wegen angewendet. Dabei kann er sowohl bei normalen Routenplanern im Auto eingesetzt werden, als auch bei Robotern oder Software-Agenten welche selbstständig einen Weg in einer vorgegebenen Welt finden sollen. Siehe auchLiteratur
Weblinks |