A*-Algorithmus

Grundidee und Zweck

Der A*-Algorithmus (gesprochen „A Stern“, auch A*-Suche) ist ein informierter Suchalgorithmus der Informatik. Er berechnet einen kürzesten Pfad zwischen zwei Knoten eines Graphen mit positiven Kantengewichten. Beschrieben wurde er 1968 von Peter Hart, Nils J. Nilsson und Bertram Raphael. Er erweitert den Dijkstra-Algorithmus und nutzt zusätzlich eine Heuristik, also eine Schätzung der noch fehlenden Kosten bis zum Ziel. Dadurch soll die Suche zielgerichteter und schneller werden.

Für jeden bekannten Knoten x wird der Wert f(x) berechnet:

f(x)=g(x)+h(x)

Dabei sind g(x) die bisher angefallenen Kosten vom Start bis x und h(x) die geschätzten Restkosten von x bis zum Ziel. Als Nächstes wird stets der Knoten mit dem kleinsten f-Wert untersucht. Die Heuristik darf die tatsächlichen Restkosten niemals überschätzen. Bei der Wegsuche eignet sich etwa die Luftlinie, weil eine reale Strecke nicht kürzer als die direkte Verbindung sein kann.

Ablauf der Suche

Knoten gehören während der Suche zu drei Gruppen:

• Unbekannte Knoten wurden noch nicht gefunden.
• Bekannte Knoten besitzen einen möglicherweise noch nicht optimalen Weg. Sie liegen mit ihrem f-Wert in der Open List, meist einer Prioritätswarteschlange wie einem binären Heap.
• Abschließend untersuchte Knoten besitzen den kürzesten Weg und liegen in der Closed List, die oft als Menge gespeichert wird.

Zu jedem bekannten oder abschließend untersuchten Knoten wird ein Zeiger auf den bisher besten Vorgänger gespeichert. So lässt sich der Weg vom Ziel zum Start zurückverfolgen. Anfangs enthält die Open List nur den Startknoten, die Closed List ist leer.

Der Algorithmus entfernt den Knoten mit dem kleinsten f-Wert aus der Open List. Ist er das Ziel, wird der Weg über die Vorgängerzeiger ausgegeben. Sonst wird der Knoten expandiert: Seine Nachfolger werden betrachtet und der Knoten selbst kommt in die Closed List. Ein neuer Nachfolger wird mit Vorgänger, g-Wert und f-Wert in die Open List aufgenommen. Bei einem schon bekannten Nachfolger werden diese Angaben nur geändert, wenn der neue Weg kürzer ist. Knoten aus der Closed List werden bei diesem Verfahren nicht erneut untersucht. Ist die Open List leer, existiert kein Pfad.

Ohne Closed List muss auf andere Weise verhindert werden, dass Knoten mehrfach untersucht werden. Andernfalls verschlechtert sich die Worst-Case-Laufzeit auf schlechter als quadratisch; bei fehlender Lösung kann der Algorithmus sogar endlos weiterlaufen.

Einsatz und Wegbeispiel

A* kann Probleme lösen, die als Graph darstellbar sind und für die sich Restkosten zum Ziel schätzen lassen. „Optimal“ kann je nach Kantengewichtung den kürzesten, schnellsten oder einfachsten Weg bedeuten. Typische Anwendungen sind Routenplaner, Computerspiele, das 15-Puzzle und das Damenproblem. Bei Karten wird meist der Luftlinienabstand als Heuristik verwendet; bei Spielen kann etwa die Anzahl falsch platzierter Steine geschätzt werden.

Im Beispiel wird der kürzeste Weg von Saarbrücken nach Würzburg gesucht. Zuerst werden Kaiserslautern mit f_KL=0+70+158=228 und Karlsruhe mit f_KA=0+145+140=285 gefunden. Danach wird wegen des kleineren f-Werts Kaiserslautern untersucht. Es erzeugt unter anderem Frankfurt mit f_F=70+103+96=269 und Ludwigshafen mit f_LU=70+53+108=231. Von Ludwigshafen wird Würzburg zunächst gefunden, aber nur vorläufig gespeichert. Bei der späteren Untersuchung von Frankfurt ergibt sich ein kleinerer Wert für Würzburg; dessen Vorgänger wird daher auf Frankfurt geändert. Nachdem Karlsruhe untersucht wurde, hat Würzburg den kleinsten f-Wert. Der optimale Weg lautet: Saarbrücken–Kaiserslautern–Frankfurt–Würzburg.

Das Beispiel zeigt: Ein Knoten in der Open List kann noch über einen besseren Weg erreicht werden. Für einen Knoten in der Closed List ist der kürzeste Weg dagegen bekannt.

Zulässige und monotone Heuristiken

Eine zulässige Heuristik überschätzt nie. Liegen die tatsächlichen Restkosten bei k, muss die Schätzung im Intervall [0;k] liegen. Für einen Zielknoten gilt deshalb immer h=0. Ist die Heuristik zwar zulässig, aber nicht monoton, ist bei einem bereits expandierten Knoten nicht unbedingt der kürzeste Weg bekannt. Dann darf keine Closed List verwendet werden, weil Knoten mehrfach expandiert werden können müssen.

Eine monotone oder konsistente Heuristik ist stärker: Sie ist zulässig und erfüllt für jeden Knoten k sowie jeden Nachfolger k′:

h(k)≤c(k,k′)+h(k′)

c(k,k′) sind die tatsächlichen Kosten der Kante von k nach k′. Die Bedingung entspricht einer Form der Dreiecksungleichung. Die Luftlinie zum Ziel ist in vielen Fällen, etwa bei Fahrstrecken, monoton.

Das Beispiel einer zulässigen, aber nicht monotonen Heuristik zeigt die Gefahr einer Closed List: Der optimale Pfad Start–K1–K2–Ziel kostet 40, der Umweg Start–U–K2–Ziel kostet 45. Mit Closed List wird K2 zunächst über U abgeschlossen. K1 kann K2 danach nicht mehr verbessern; ausgegeben wird fälschlich der Weg mit Kosten 45. Ohne Closed List wird K2 erneut expandiert und der optimale Weg mit Kosten 40 gefunden.

Eigenschaften, Optimalität und Aufwand

A* ist vollständig: Gibt es eine Lösung, wird sie gefunden. Mit monotoner Heuristik ist er optimal; bei nur zulässiger Heuristik bleibt er ohne Closed List optimal. Gibt es mehrere optimale Lösungen, wird abhängig von Implementierungsdetails eine davon gefunden. Außerdem gilt A* als optimal effizient: Unter Verwendung derselben Heuristik expandiert kein anderer Algorithmus weniger Knoten.

Die Optimalität folgt daraus, dass für jeden Knoten x auf einem optimalen Pfad mit Kosten K* gilt f(x)=g(x)+h(x)≤K*. Für eine suboptimale Ziellösung L2 mit Kosten K2 gilt dagegen h(L2)=0 und f(L2)=g(L2)>K*. Solange ein Knoten eines optimalen Pfads in der Open List liegt, wird daher keine suboptimale Lösung gewählt.

Die Laufzeit hängt besonders von der Genauigkeit der Heuristik und der Umsetzung von Open und Closed List ab. Eine genauere Schätzung reduziert die Zahl der untersuchten Knoten; eine nicht monotone Heuristik kann durch wiederholtes Expandieren exponentielle Laufzeit verursachen. Bei monotoner Heuristik, binärem Heap für die Open List, Array für die Closed List und höchstens d ausgehenden Kanten pro Knoten ergibt sich zunächst eine quadratische Worst-Case-Laufzeit O(|V|²). Speichert jeder Knoten seine Heap-Position, kann decreaseKey logarithmisch statt linear arbeiten; dann sinkt die Gesamtlaufzeit auf O(|V|·log|V|).

Oft ist Speicher statt Rechenzeit der begrenzende Faktor, da Open und Closed List alle bekannten Knoten halten. Beim 15-Puzzle besitzt der vollständige Graph bereits 16!=20.922.789.888.000 Knoten.

Verwandte Verfahren

Dijkstra verwendet keine Heuristik: h=0 und damit f=g. Bei monotoner Heuristik kann A* durch g_neu(x,y)=g(x,y)+h(y)-h(x) und h_neu=0 in einen äquivalenten Dijkstra-Algorithmus überführt werden. Ein Greedy-Algorithmus ignoriert dagegen die bisherigen Kosten: g=0 und f=h. Dijkstra eignet sich bei der Wegsuche besser, wenn das Ziel vorab nicht bekannt ist, etwa bei der Suche nach der nächsten Tankstelle.

Speicherbeschränkte Varianten sind IDA* (Iterative Deepening A*), RBFS (Recursive Best-First Search), MA* und SMA*. Sie sparen Speicher, erhöhen aber die Laufzeit, weil vergessene Knoten später neu erzeugt werden können. Bei monotoner Heuristik und ausreichend Speicher sind sie optimal; bei zu enger Speichergrenze kann nur eine suboptimale oder gar keine Lösung gefunden werden.

D* (dynamischer A*) verarbeitet neue Umgebungsinformationen effizient und plant nur betroffene Teile eines Weges neu, etwa wenn eine Brücke unpassierbar ist. Er ist wie A* optimal und optimal effizient. Bellman-Ford erlaubt negative Kantengewichte; Floyd und Warshall berechnet kürzeste Pfade zwischen allen Knotenpaaren.