A*-Algorithmus
| Dieser Artikel bedarf einer Überarbeitung. Eine Begründung befindet sich in der Regel auf der Diskussionsseite. Wenn du Lust hast, verbessere den Artikel und entferne anschließend diesen Baustein. |
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) 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 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.
| Inhaltsverzeichnis |
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 vmin mit der geringsten Summe
- Wenn vmin = e dann wurde der kürzeste Weg gefunden
- Ansonsten nimm die Nachfolger von vmin in A auf (vmin 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.