Benutzer:Regnaron/Algorithmen-Layout
Einleitung
Der A*-Algorithmus dient in der [[[Informatik]] der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem gewichteten Graphen. 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.
Eigenschaften
Wie oben schon angedeuted ist das besondere am A*-Algorithmus dass er – im Gegensatz zu den uninformierten Suchalgorithmen – Zielgerichtet sucht. Dies wird jedoch erst durch eine Heuristik, mittels der man Annahmen über den den Graph auf dem der A*-Algorithmus angewendet werden soll erreicht. Der Algorithmus arbeitet umso Zielgerichteter, je besser die Heuristik ist. Das finden einer guten Heuristik ist somit der wichtigste Schritt wenn man 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.
Einen formalen Beweis hierfür findet man unter Optimalitätsbeweis weiter unten im Artikel.
- Einführung warum A* optimal ist.
- Konkretes Beispiel für Gute Heuristik <-> schlechte Heuristik
Motivation
- Was ist das tolle an A*?
- Was kann er?
- Vorteile gegenüber uninformierten Suchalgorithmen
Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Fusce velit. Suspendisse purus nunc, dictum vitae, volutpat non, faucibus vel, eros. Nulla mi libero, tempor eget, faucibus eu, pharetra at, nisl. Donec nonummy adipiscing justo. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Praesent eu massa at tellus convallis posuere. Cras fermentum est nec metus. Integer ac ipsum eget tortor euismod nonummy. Proin vestibulum mi quis neque. Praesent eros. Ut erat felis, eleifend at, adipiscing ac, faucibus vitae, elit. Vestibulum pretium neque ac diam. Suspendisse mollis, enim a ullamcorper elementum, urna ante bibendum nibh, et blandit elit velit at dui. Nulla cursus mi non ligula. |
Pellentesque feugiat lobortis eros. Integer ac ligula. Ut sit amet est sed pede pretium convallis. Maecenas tempus pellentesque leo. Suspendisse lectus augue, tempus a, euismod eu, luctus et, velit. Maecenas suscipit tortor. Fusce magna dolor, iaculis ac, cursus vitae, elementum nec, arcu. Sed varius diam at est. Quisque elit. Etiam velit purus, posuere eget, hendrerit nec, placerat quis, est. Integer varius, arcu eget gravida tincidunt, massa mauris imperdiet sem, vel hendrerit diam tortor et velit. Etiam dictum mollis turpis. In sit amet est ac neque pellentesque porttitor. Nulla magna. In hac habitasse platea dictumst. Morbi vel nulla at magna accumsan gravida. |
Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Fusce velit. Suspendisse purus nunc, dictum vitae, volutpat non, faucibus vel, eros. Nulla mi libero, tempor eget, faucibus eu, pharetra at, nisl. Donec nonummy adipiscing justo. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Praesent eu massa at tellus convallis posuere. Cras fermentum est nec metus. Integer ac ipsum eget tortor euismod nonummy. Proin vestibulum mi quis neque. Praesent eros. Ut erat felis, eleifend at, adipiscing ac, faucibus vitae, elit. Vestibulum pretium neque ac diam. Suspendisse mollis, enim a ullamcorper elementum, urna ante bibendum nibh, et blandit elit velit at dui. Nulla cursus mi non ligula. |
Pellentesque feugiat lobortis eros. Integer ac ligula. Ut sit amet est sed pede pretium convallis. Maecenas tempus pellentesque leo. Suspendisse lectus augue, tempus a, euismod eu, luctus et, velit. Maecenas suscipit tortor. Fusce magna dolor, iaculis ac, cursus vitae, elementum nec, arcu. Sed varius diam at est. Quisque elit. Etiam velit purus, posuere eget, hendrerit nec, placerat quis, est. Integer varius, arcu eget gravida tincidunt, massa mauris imperdiet sem, vel hendrerit diam tortor et velit. Etiam dictum mollis turpis. In sit amet est ac neque pellentesque porttitor. Nulla magna. In hac habitasse platea dictumst. Morbi vel nulla at magna accumsan gravida. |
Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Fusce velit. Suspendisse purus nunc, dictum vitae, volutpat non, faucibus vel, eros. Nulla mi libero, tempor eget, faucibus eu, pharetra at, nisl. Donec nonummy adipiscing justo. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Praesent eu massa at tellus convallis posuere. Cras fermentum est nec metus. Integer ac ipsum eget tortor euismod nonummy. Proin vestibulum mi quis neque. Praesent eros. Ut erat felis, eleifend at, adipiscing ac, faucibus vitae, elit. Vestibulum pretium neque ac diam. Suspendisse mollis, enim a ullamcorper elementum, urna ante bibendum nibh, et blandit elit velit at dui. Nulla cursus mi non ligula. |
Pellentesque feugiat lobortis eros. Integer ac ligula. Ut sit amet est sed pede pretium convallis. Maecenas tempus pellentesque leo. Suspendisse lectus augue, tempus a, euismod eu, luctus et, velit. Maecenas suscipit tortor. Fusce magna dolor, iaculis ac, cursus vitae, elementum nec, arcu. Sed varius diam at est. Quisque elit. Etiam velit purus, posuere eget, hendrerit nec, placerat quis, est. Integer varius, arcu eget gravida tincidunt, massa mauris imperdiet sem, vel hendrerit diam tortor et velit. Etiam dictum mollis turpis. In sit amet est ac neque pellentesque porttitor. Nulla magna. In hac habitasse platea dictumst. Morbi vel nulla at magna accumsan gravida. |
Algorithmus (informal)
- Informale Beschreibung des Algorithmus
Anwendungsbeispiel
- Beispiel der Anwendung von A*
Algorithmus (formal)
- Pseudocode wie der Algorithmus aussieht
Optimalitätsbeweis
- Formaler Beweis dafür dass A* optimal ist
Anwendungsgebiete
- Routenplaner
- Roboter die ihren Weg suchen
- weitere Beispiele
Literatur
- Introduction to AI
- Corman?
- Tardos?
Weblinks
- Beispiel eines A* Laufes
- A* Algorithmus in C++
- A* Algorithmus in Pascal
- Semesterarbeit über A*
Der A*-Algorithmus dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ sein.
Für nicht zusammenhängende, ungerichtete Graphen kann der Abstand zu bestimmten Knoten auch unendlich sein, wenn ein Pfad zwischen Startknoten und diesen Knoten nicht existiert. Dasselbe gilt auch für gerichtete, nicht stark zusammenhängende Graphen.
Er steht in engem Zusammenhang zum A*-Baum.
Der Algorithmus verwendet dazu eine Schätzfunktion, die für jeden Knoten v eine untere Schranke für den noch zu erwartenden Abstand (im Sinne der Pfadlänge, d.h. die Summe der Kantengewichte, welche die Kosten des Restpfades darstellt) von v zum Zielknoten e liefert. Durch die Verwendung dieser Funktion ergibt sich eine zielgerichtete Suche in Richtung auf den Endknoten. Zu beachten ist, dass es sich dabei zwar um eine Heuristik handelt (es werden zwar die "vielversprechendsten" Pfade zuerst untersucht, aber keine Lösungsmöglichkeit grundsätzlich ausgeschlossen), jedoch findet der Algorithmus immer die optimale Lösung (also den Pfad mit den geringsten Kosten=Summe der Kantengewichte) solange die Schätzfunktion nicht überschätzt, d.h. sie darf niemals die Kosten zwischen zwei Knoten höher berechnen, als sie es sind.
Von entscheidender Bedeutung ist, dass die Schätzfunktion eine möglichst hohe, untere Schranke für die noch zu erwartende Pfadlänge liefern muss. Für die Suche in einer Landkarte (z.B. bei Routenplanern) erfüllt die Luftlinie diese Bedingung. Der Algorithmus sucht dann so, wie man es als Mensch auch tun würde: Wird z.B. eine Route von München nach Hamburg gesucht, macht es wenig Sinn, zuerst in Richtung Salzburg zu suchen, sondern man wird zuerst eine Strecke prüfen, die in Richtung Norden führt. Ungeeignet gewählte Schätzfunktionen können die Laufzeit um den Faktor n (Knotenanzahl) gegenüber anderen Algorithmen (bspw. Algorithmus von Dijkstra) erhöhen.
Eigenschaften
- Der A*-Algorithmus ist vollständig, d.h. wenn ein Pfad zum Zielknoten existiert, so wird dieser auch gefunden.
- Außerdem ist er optimal, d.h. es gibt keinen kürzeren Pfad zum Zielknoten als den gefundenen.
- Zudem ist A* optimal effizient, d.h. jeder andere optimale und vollständige Algorithmus, der dieselbe Heuristik verwendet, muss mindestens so viele Knoten betrachten wie A*, um eine Lösung zu finden.
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.
Literatur
- 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.