Benutzer:Regnaron/Algorithmen-Layout
Einleitung
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.
Allgemeines
Wie oben schon angedeuted ist das besondere am A*-Algorithmus 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, was auch der Grund dafür ist dass der Algorithmus das Ziel sehr schnell findet. Diese Abschätzung kann jedoch erst durch eine Heuristik, mittels derer man Annahmen über den den Graph auf dem der A*-Algorithmus angewendet werden soll erreicht werden. Der Algorithmus arbeitet hierbei umso Zielgerichteter, je besser die Heuristik ist. Hierzu ist es nötig dass die durch die Heuristik geschätzten Kosten zum Ziel sehr nahe an den tatsächlichen Kosten zum Ziel sind. Das finden einer guten Heuristik ist somit der wichtigste Schritt wenn man effizient einen kürzesten Pfad mithilfe des A*-Algorithmus finden will. Stellt man die Anforderung an die Heuristik dass diese optimistisch ist, also den tatsächlichen Weg zum Ziel nie überschätzt, so kann man beweisen dass der A*-Algorithmus tatsächlich immer einen kürzesten Weg findet. Dies bedeuted jedoch im Umkehrschluss auch dass der Algorithmus, falls man ihm eine sehr schlechte Heuristik gibt, 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.
Funktionsweise
Wendet man den A*-Algorithmus auf einem Knoten an, so werden zuerst alle von diesem Knoten aus erreichbaren Nachbarn berechnet, und dann durch die Heuristik für jeden dieser Nachbarn eine Schätzung abgegeben wie weit es von dem entsprechenden Knoten noch zum Ziel ist. Für jeden dieser Knoten addiert der A*-Algorithmus die geschätzten Kosten bis zum Ziel mit den Kosten um vom aktuellen Knoten zu eben jenem Knoten zu kommen. Die vorgehensweise des Algorithmus lässt sich dabei durch folgende Gleichung beschreiben: f(v) = g(u) + h(v) Hierbei steht h(v) für die von der Heuristik für Knoten v geschätzten Kosten bis zum Ziel, g(u) für die bisherigen Wegkosten um zum Knoten u zu kommen, und f(v) steht für die Wahrscheinlich zu erwartenden Kosten wenn man von seiner aktuellen Position aus über Knoten v ans Ziel zu kommenen will. Hierbei wird im nächsten Schritt 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 Rumänien einen kürzesten Pfad von Arad nach Bukarest 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 um von dem einen Knoten zum anderen zu kommen 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 Bukarest auf, so ergeben sich die folgenden Werte, welche im Beispiel die Kosten für die Funktion h(v) sein werden.
Arad <--> Bukarest: 366km Bukarest <--> Bukarest: 0km Craiova <--> Bukarest: 160km Fagaras <--> Bukarest: 176km Oradea <--> Bukarest: 380km Pitesti <--> Bukarest: 100km Rimnicu <--> Bukarest: 193km Sibiu <--> Bukarest: 253km Timisora <--> Bukarest: 329km Zerind <--> Bukarest: 374km
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 Arad bis zu dieser Stadt und den geschätzten Kosten von dieser Stadt bis nach Bukarest zusammensetzt.
Nachdem man eine passende Schätzfunktion gefunden hat, und die Kosten aller Pfade Im ersten Schritt werden nun alle von Arad aus erreichbaren Städte betrachtet und für jede der Städte wird geschätzt wie weit es von der entsprechenden Stadt bis nach Bukarest ist. Auf diese geschätzte Weglänge wird die Weglänge um von Arad in die entsprechende Stadt zu kommen addiert. Somit ist es in der momentanen Situation am vielversprechensten von Arad nach Sibiu zu gehen, da der Weg von Arad über Sibiu nach Bukarest mit 393km noch der kürzeste zu sein scheint. |
Im zweiten Schritt wurden nun neben allen von Arad aus erreichbaren Städte auch noch alle von Sibiu aus erreichbaren Städte bezüglich ihrer wahrscheinlich Wegkosten bis nach Bukarest betrachtet. Bisher scheint die Wahl des Algorithmus Sibiu als erstes zu erkunden noch richtig, da der kürzeste Weg von Arad nach Bukarest scheinbar durch die Städte Sibiu und Rimnicu führt. Würde man einen anderen Weg wählen könnte dieser Weg länger als nötig sein, da es momentan möglicherweise eine Weg von Arad über Sibiu und Rimnicu irgendwie nach Bukarest gibt, der nur 413km lang sein könnte. |
Im dritten Schritt wurden nun alle von Rimnicu aus erreichbaren Städte betrachtet. Jedoch egal welche Stadt man wählt: Die Wahrscheinlichen Kosten von einer der von Rimnicu aus erreichbaren Städte nach Bukarest sind höher als wenn man zuerst Fagaras untersuchen würde. Würde man den Weg durch Rimnicu weiterverfolgen, so beträgt die Länge des Weges von Arad via Sibiu über Rimnicu nach Pitesti mindestens 417km. Untersucht man jedoch den Weg von Arad über Sibiu nach Fagaras, so ist die Entfernung bis nach Bukarest nur mindestens 415km. Es könnte also sein dass man hier einen kürzeren Pfad bis nach Bukarest findet, weswegen zuerst diese Möglichkeit überprüft wird. |
Nachdem im vierten Schritt nun alle von Fagaras aus erreichbaren Städte betrachtet wurden ist zwar schon eine Route nach Bukarest gefunden welche nur 450km hat, aber wenn man die früher schon einmal betrachtete Route durch Rimnicu noch einmal betrachtet, so kann es immer noch sein, dass wenn man von Rimnicu nach Pitesti geht von dort aus einen Weg findet welcher insgesamt nur 417km lang ist. Somit wird nicht direkt die 450km lange Route nach Bukarest genommen, sondern solange weitergesucht wie es bessere Routen gibt. Die Route über Fagaras nach Bukarest wird somit erst betrachtet wenn alle anderen Routen im besten Fall mindestens 450km lang sein sollten. Als nächstes wird also Pitesti genauer betrachtet, da dies aktuell die Vielversprechenste Route ist. |
Wird nun im fünften Schritt Pitesti erkundet, so findet man unter all den möglichen Städten in die man von Pitesti aus gehen kann auch die Stadt Bukarest. Der Weg von Arad via Sibiu, Rimnicu und Pitesti und schließlich nach Bukarest ist nun nur noch 418km lang. Somit ist dieser Weg insbesondere kürzer als der im vierten Schritt bereits gefundene Weg von 450km. Da die Stadt Bukarest nun die niedrigsten Entfernungskosten hat wird sie im nächsten Schritt erkundet, wodurch der Algorithmus terminiert und die Route Arad, Sibiu, Rimnicu, Pitesti, Bukarest erfolgreich als einen kürzesten Pfad von Arad nach Bukarest gefunden hat. Neben der Tatsache dass tatsächlich der kürzeste Pfad gefunden wurde, wurden ebenfalls nur sehr wenige Städte überhaupt betrachtet. Dank der guten Heuristik brauchte der Algorithmus viele mögliche Wege um von Arad nach Bukarest zu kommen gar nicht erst betrachten. Außerdem ist der Algorithmus sehr Zielstrebig vorgegangen: Von den sechs Städten die ausgewählt wurden lagen 5 tatsächlich auf dem kürzesten Weg, und nur eine Stadt außerhalb dieses kürzesten Weges (Fagaras) wurde erkundet. |
Algorithmus
Eingabe: Ein Graph, ein Startknoten s und ein Endknoten e.
Es wird eine Liste A von "aktuellen Knoten" verwaltet. Zu jedem Knoten wird sein Abstand vom Startknoten s auf dem kürzesten bisher gefundenen Pfad gespeichert. Soll außer der Länge des kürzesten Pfades auch der Pfad selbst gefunden werden, wird bei jedem Knoten in Schritt 4. auch sein Vorgänger gespeichert. Das Ergebnis kann dann in umgekehrter Reihenfolge (von e nach s) ermittelt werden.
- Nimm den Startknoten s in A auf
- Für jeden Knoten aus A: Berechne die Summe aus seinem Abstand von s und seiner Schätzfunktion und ermittle den Knoten mit der geringsten Summe
- Wenn dann wurde der kürzeste Weg gefunden
- Ansonsten nimm die Nachfolger von in A auf ( wird "aufgelöst") und gehe zu 2. Ist einer der Nachfolger bereits in A enthalten, nehme die Variante mit dem geringeren Abstand von s.
Zu beachten ist, dass die Suche nicht schon endet, wenn der Zielknoten e gefunden wird, sondern erst, wenn dieser als Kandidat für die "Auflösung" identifiziert wird.
Optimalitätsbeweis
- Einführung warum A* optimal ist.
- Formaler Beweis dafür dass A* optimal ist
Anwendungsgebiete
Der A*-Star Algorithmus wird insbesondere 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 auch
Literatur
- Stuart Russell, Peter Norvig: Artificial Intelligence: A Modern Approach, 2. Auflage, 2002, Prentice Hall.
- P. E. Hart, N. J. Nilsson, B. Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics SSC4 (2), pp. 100-107, 1968.
- P. E. Hart, N. J. Nilsson, B. Raphael: Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", SIGART Newsletter, 37, pp. 28-29, 1972.