A*-Algorithmus

Eine Heuristik ist zulässig, wenn die Kosten nie überschätzt werden. Das heißt, die geschätzten Kosten müssen stets im Intervall ${\displaystyle [0;k]}$ liegen, wenn ${\displaystyle k}$ die tatsächlichen Kosten bezeichnet. Ist die verwendete Heuristik nur zulässig, aber nicht monoton, dann ist zu einem expandierten Knoten nicht notwendigerweise der kürzeste Weg bekannt. Daher muss es möglich sein, einen Knoten mehrfach zu expandieren. Es darf also keine Closed List benutzt werden.

Im Diagramm rechts ist ein Beispielgraph und eine zulässige (aber nicht monotone) Heuristik dargestellt. Der beste Weg vom Start zum Ziel hat Kosten 40 und führt über die Knoten K1 und K2. Der Weg über den Umwegknoten U hat Kosten 45. Beim Startknoten schätzt die Heuristik Kosten von 40 und beim Knoten K1 Kosten von 30, was jeweils den tatsächlichen Kosten entspricht. Bei den Knoten K2, U und Ziel werden Kosten von 0 geschätzt. Da eine Heuristik nicht überschätzen darf, werden für einen Zielknoten immer Kosten von 0 geschätzt.

Beispiel mit Closed List

• Im ersten Schritt wird der Startknoten expandiert. Die beiden Nachfolgeknoten K1 und U werden gefunden und mit den Werten ${\displaystyle f_{K1}=10+30=40}$ und ${\displaystyle f_{U}=25+0=25}$ in die Open List eingetragen.
• Im zweiten Schritt wird der Knoten U expandiert, da sein ${\displaystyle f}$-Wert am niedrigsten ist. Der Nachfolgeknoten K2 wird gefunden und mit dem Wert ${\displaystyle f_{K2}=35+0=35}$ in die Open List eingetragen.
• Im dritten Schritt besteht die Open List aus den Knoten K2 mit ${\displaystyle f_{K2}=35}$ und dem Knoten K1 mit ${\displaystyle f_{K1}=40}$. Also wird der Knoten K2 expandiert. Die beiden Nachfolgeknoten K1 und Ziel werden gefunden. Der neue Wert ${\displaystyle f_{K1}'=55+30=85}$ ist größer als der alte Wert. Daher wird der ${\displaystyle f}$-Wert für den Knoten K1 in der Open List nicht aktualisiert. Der Zielknoten wird mit ${\displaystyle f_{Ziel}=45+0=45}$ in die Open List eingefügt.
• Im vierten Schritt befinden sich die Knoten K1 mit ${\displaystyle f_{K1}=40}$ und Ziel mit ${\displaystyle f_{Ziel}=45}$ in der Open List. Die Expansion von K1 erzeugt keine Nachfolgeknoten, da sich sowohl Start als auch K2 bereits auf der Closed List befinden. Die Verwendung der Closed List verhindert hier, dass die optimale Lösung gefunden wird.
• Im fünften Schritt wird der einzige Knoten auf der Open List expandiert: der Zielknoten. Die gefundene Lösung ist also Start–U–K2–Ziel und mit Kosten 45 nicht optimal.

Beispiel ohne Closed List

• Im ersten Schritt wird der Startknoten expandiert. Die beiden Nachfolgeknoten K1 und U werden gefunden und mit den Werten ${\displaystyle f_{K1}=10+30=40}$ und ${\displaystyle f_{U}=25+0=25}$ in die Open List eingetragen.
• Im zweiten Schritt wird der Knoten U mit ${\displaystyle f_{U}=25}$ expandiert. Die Nachfolgeknoten K2 und Start werden gefunden und mit den Werten ${\displaystyle f_{K2}=35+0=35}$ und ${\displaystyle f_{Start}=50+40=90}$ in die Open List eingetragen.
• Im dritten Schritt wird der Knoten K2 expandiert. Die Nachfolgeknoten K1 (${\displaystyle f_{K1}=55+30=85}$), U (${\displaystyle f_{U}=45+0=45}$) und Ziel (${\displaystyle f_{Ziel}=45+0=45}$) werden gefunden.
• Im vierten Schritt werden die Nachfolgeknoten von K1 (${\displaystyle f_{K1}=40}$) in die Open List eingefügt: Start mit ${\displaystyle f_{Start}=20+40=60}$ und K2 mit ${\displaystyle f_{K2}=30+0=30}$.
• Im fünften Schritt wird K2 zum zweiten Mal expandiert, jetzt mit ${\displaystyle f_{K2}=30}$. Die Knoten K1 (${\displaystyle f_{K1}=50+30=80}$), U (${\displaystyle f_{U}=40+0=40}$) und Ziel (${\displaystyle f_{Ziel}=40+0=40}$) werden gefunden.
• Im sechsten Schritt befinden sich 8 Knoten auf der Open List (${\displaystyle f_{Ziel}=40}$, ${\displaystyle f_{U}=40}$, ${\displaystyle f_{U}=45}$, ${\displaystyle f_{Ziel}=45}$, ${\displaystyle f_{Start}=60}$, ${\displaystyle f_{K1}=80}$, ${\displaystyle f_{K1}=85}$, ${\displaystyle f_{Start}=90}$). Die beiden Knoten U und Ziel haben jeweils mit 40 den niedrigsten ${\displaystyle f}$-Wert. Welcher Knoten expandiert wird hängt vom Zufall (genauer: Implementierungsdetails) ab. Auf die gefundene Lösung hat dies jedoch keinen Einfluss. Sobald der Zielknoten expandiert wird (entweder in diesem oder im nächsten Schritt), ist mit dem Pfad Start–K1–K2–Ziel die optimale Lösung gefunden.

Damit eine Heuristik monoton (oder konsistent) ist, muss sie zwei Bedingungen erfüllen:

• Die Kosten dürfen nie überschätzt werden (Bedingung für eine zulässige Heuristik).
• Für jeden Knoten ${\displaystyle k}$ und jeden Nachfolgeknoten ${\displaystyle k'}$ von ${\displaystyle k}$ muss gelten ${\displaystyle h(k)\leq c(k,k')+h(k')}$. Hierbei bezeichnet ${\displaystyle c(k,k')}$ die tatsächlichen Kosten, um von ${\displaystyle k}$ nach ${\displaystyle k'}$ zu kommen.

Die zweite Bedingung ist eine Form der Dreiecksungleichung: Die geschätzten Kosten von einem Knoten ${\displaystyle k}$ dürfen nicht größer sein als die tatsächlichen Kosten zu einem Nachfolgeknoten ${\displaystyle k'}$ plus die geschätzten Kosten dieses Knotens.

Die zulässige Heuristik aus dem Beispiel verletzt diese Bedingung: Die Kosten von Knoten K1 werden mit 30 geschätzt. Bewegt man sich nun 20 in Richtung des Ziels zu Knoten K2 werden plötzlich keine Kosten mehr geschätzt. Hier gilt ${\displaystyle 30\not \leq 20+0}$.

In vielen Fällen ist z. B. der euklidische Abstand (die Luftlinie) zum Ziel eine monotone Heuristik, beispielsweise für die Fahrtstrecke mit einem Auto.

Wenn eine Heuristik monoton ist, so kann sie in die Kostenfunktion integriert werden, und die A*-Suche wird zu einem Dijkstra-Algorithmus.

Der A*-Algorithmus ist optimal, falls eine monotone Heuristik verwendet wird. Wenn keine Closed List verwendet wird, bleibt die Optimalität auch bei einer zulässigen Heuristik erhalten. Im Folgenden wird die Optimalität unter Verwendung einer monotonen Heuristik bewiesen.

Behauptung: Der A*-Algorithmus findet immer eine optimale Lösung.

Beweis: Sei ${\displaystyle L_{1}}$ eine optimale Lösung mit Kosten ${\displaystyle K^{*}}$ und ${\displaystyle L_{2}}$ eine suboptimale Lösung. Da die Heuristik die Kosten bis zum Ziel nie überschätzt, gilt für jeden Zielknoten und insbesondere für ${\displaystyle L_{2}}$:

${\displaystyle h(L_{2})\!\,=0}$

Da ${\displaystyle L_{2}}$ eine suboptimale Lösung ist, gilt für die Kosten ${\displaystyle K_{2}}$:

${\displaystyle K_{2}\!\,=f(L_{2})=g(L_{2})+h(L_{2})=g(L_{2})>K^{*}}$

Die Heuristik schätzt die tatsächlichen Kosten oder unterschätzt sie. Also gilt für einen beliebigen Knoten ${\displaystyle x}$ auf dem kürzesten Pfad zur optimalen Lösung ${\displaystyle L_{1}}$:

${\displaystyle f(x)=g(x)+h(x)\leq K^{*}}$

Damit gilt:

${\displaystyle f(x)\leq K^{*}<f(L_{2})}$

Dies bedeutet, dass der A*-Algorithmus die suboptimale Lösung ${\displaystyle L_{2}}$ nicht wählt, solange sich Knoten eines optimalen Pfades in der Open List befinden (da bei jedem Schritt der Knoten mit minimalem ${\displaystyle f}$-Wert erweitert wird). Eine suboptimale Lösung würde also erst gewählt werden, nachdem die Knoten jeder optimalen Lösung besucht worden wären. Dazu kommt es nicht, da der A*-Algorithmus stets die erste gefundene Lösung ausgibt und dann terminiert.

Die hier beschriebene Zeitkomplexität (oder asymptotische Laufzeit) hat nur geringe Bedeutung, da die Stärke des A*-Algorithmus im zielgerichteten Suchen liegt und im Vergleich zur Gesamtanzahl der Knoten meist nur ein kleiner Teil davon untersucht wird. Bei Labyrinthen ist dies jedoch oft nicht möglich und die tatsächliche Laufzeit nähert sich der angegebenen worst-case Laufzeit an. Die Zeitkomplexität wird hier nur unter Verwendung von vereinfachenden Annahmen abgeschätzt. Sie hängt sehr stark von zwei Faktoren ab:

• Genauigkeit der verwendeten Heuristik: Ist die Heuristik nicht monoton, wird die Laufzeit exponentiell, da Knoten mehrfach expandiert werden. Je genauer die Kostenabschätzung ist, desto weniger Knoten werden untersucht.
• Implementierung der Open und Closed List: Die kostenintensiven Operationen im A*-Algorithmus sind die Methoden, um Elemente in die Listen einzufügen und zu entfernen, sowie Elemente in der Open List zu ändern. Diese müssen von den verwendeten Datenstrukturen effizient unterstützt werden, um eine kurze Laufzeit zu ermöglichen.

Im Folgenden wird die Menge der Knoten des zu Grunde liegenden Graphen mit ${\displaystyle V}$ bezeichnet. Es wird angenommen, dass alle Knoten und Kanten im Voraus bekannt sind. (Dies ist bei einer Wegsuche meist der Fall.) Die verwendete Heuristik ist monoton. Die Open List wird als binärer Heap implementiert, die Closed List als Array. (Jeder Knoten besitzt ein Flag, ob er auf der Liste ist oder nicht.) Der A*-Algorithmus hat damit eine quadratische worst-case Laufzeit:

${\displaystyle {\mathcal {O}}(\vert V\vert ^{2})}$

Diese Laufzeit ergibt sich wie folgt: Die Hauptschleife des Algorithmus wird für jeden Knoten maximal einmal ausgeführt. Die Funktionen openlist.removeMin, expandNode und closedlist.add werden also maximal ${\displaystyle \vert V\vert }$-mal aufgerufen. openlist.removeMin enthält maximal ${\displaystyle \vert V\vert }$ Knoten und benötigt bei einem binären Heap logarithmische Laufzeit. closedlist.add benötigt bei einem Array nur konstante Laufzeit. Dadurch ergibt sich eine vorläufige Laufzeit von:

${\displaystyle {\mathcal {O}}{\big (}\vert V\vert \cdot (\log \vert V\vert +{\mathcal {O}}_{\textit {expandNode}}){\big )}}$

Die Laufzeit von expandNode setzt sich zusammen aus: closedlist.contains hat konstante Laufzeit. openlist.contains hat ebenfalls konstante Laufzeit, wenn man zu jedem Knoten auch ein Open List Flag speichert. Der Aufruf von openlist.find kann entfallen, wenn jeder Knoten auch seinen ${\displaystyle f}$-Wert speichert. Es wird entweder openlist.decreaseKey (benötigt lineare Laufzeit, um das entsprechende Element zu finden) oder openlist.enqueue (benötigt logarithmische Laufzeit) aufgerufen. Dabei wird die logarithmische von der linearen Laufzeit dominiert. Ein Schleifendurchlauf innerhalb von expandNode benötigt somit lineare Laufzeit.

Alle Funktionen werden für jeden Nachfolgeknoten aufgerufen. Es wird angenommen, dass jeder Knoten nur maximal ${\displaystyle d}$ ausgehende Kanten hat. Die Anzahl der Schleifendurchläufe innerhalb von expandNode ist somit konstant und kann bei der asymptotischen Laufzeitbetrachtung vernachlässigt werden. Diese Annahme gilt nicht für Graphen, in denen jeder Knoten mit fast jedem anderen Knoten verbunden ist.

${\displaystyle {\mathcal {O}}_{\textit {expandNode}}={\mathcal {O}}(d\cdot \vert V\vert )={\mathcal {O}}(\vert V\vert )}$

Die Gesamtlaufzeit ergibt sich als:

${\displaystyle {\mathcal {O}}{\big (}\vert V\vert \cdot (\log \vert V\vert +\vert V\vert ){\big )}={\mathcal {O}}(\vert V\vert \cdot \vert V\vert )}$

Optimierungspotential in Bezug auf die worst-case Laufzeit besteht vor allem bei openlist.decreaseKey. Das teure Suchen im Heap entfällt, wenn jeder Knoten die Position seines entsprechenden Eintrages im Heap speichert. Damit würde sich die Laufzeit von decreaseKey zu logarithmisch und die Gesamtlaufzeit zu linear-logarithmisch reduzieren:

${\displaystyle {\mathcal {O}}(\vert V\vert \cdot \log \vert V\vert )}$

Der begrenzende Faktor bei A* ist oft nicht die Rechenzeit, sondern der Speicherplatz. Da alle bekannten Knoten im Speicher gehalten werden (Open und Closed List), ist A* für viele Probleme nicht geeignet. Schon beim einfachen 15-Puzzle hat der komplette Graph bereits ${\displaystyle 16!=20.922.789.888.000}$ Knoten. Bei einem entsprechend langen Lösungsweg reicht der verfügbare Speicher nicht aus und A* kann keine Lösung finden. Im Abschnitt Verwandte Algorithmen finden sich ähnliche Algorithmen, die versuchen, den Speicherplatzverbrauch zu beschränken.