A*-Algorithmus

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, wodurch er – im Gegensatz zu uninformierten Suchalgorithmen – zuerst jene Knoten untersucht, welche am wahrscheinlichsten zum Ziel führen.

Allgemeines

Das Besondere am A*-Algorithmus ist, 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, weswegen der Algorithmus das Ziel im Allgemeinen sehr schnell findet.

Die Abschätzung welche Knoten am wahrscheinlichsten zum Ziel führen kann jedoch erst durch eine Heuristik, mittels derer man Annahmen über den Graphen, auf dem der A*-Algorithmus angewendet werden soll, erreicht werden. Der Algorithmus arbeitet hierbei umso zielgerichteter, je genauer die von der Heuristik für einen Knoten geschätzten Kosten bis zum Ziel den tatsächlichen Kosten von diesem Knoten zum Ziel entsprechen.

Stellt man die Anforderung an die Heuristik, dass diese monoton ist, also den tatsächlichen Weg zwischen zwei Knoten nie überschätzt, so kann man beweisen dass der A*-Algorithmus tatsächlich immer einen kürzesten Weg findet. Dies bedeutet jedoch im Umkehrschluss auch, dass der Algorithmus, falls man eine sehr schlechte Heuristik verwendet, 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.

Anmerkung: Modifiziert man den A*-Algorithmus etwas, so reicht es auch aus eine zulässige Heuristik, welche die Kosten von einem Knoten bis zum Ziel nie überschätzt, zu verwenden um immer einen kürzesten Pfad zu finden. Eine genauere Betrachtung der Unterschiede zwischen monotonen und optimistischen Heuristiken findet man unter Heuristiken weiter unten im Artikel.

Funktionsweise

Landkarte von Deutschland für dieses Beispiel mit den Entfernungen zwischen den einzelnen Städten. Die Zahlen geben jeweils die Entfernung zwischen den beiden verbundenen Städten an.

Wendet man den A*-Algorithmus auf einem Knoten u an, so werden zuerst alle von diesem Knoten aus erreichbaren Nachbarn berechnet. Danach wird durch die Heuristik für jeden dieser Nachbarn eine Schätzung abgegeben wie teuer es ist von ihm aus zum Ziel zu kommen. Für jeden dieser Nachbarknoten v addiert der A*-Algorithmus nun die von der Heuristik geschätzten Kosten bis zum Ziel zu den Kosten, um vom Knoten u zu eben jenem Knoten v zu kommen. Die Vorgehensweise des Algorithmus lässt sich dabei durch folgende Gleichung beschreiben:

f(v) = g(v) + h(v)

Hierbei steht h(v) für die von der Heuristik für Knoten v geschätzten Kosten bis zum Ziel, g(v) für die bisherigen gesamten Wegkosten um vom Knoten bei dem man den A*-Algorithmus gestartet hat zum Knoten v zu kommen, und f(v) steht für die wahrscheinlich zu erwartenden Kosten wenn man vom Startknoten aus über seine aktuelle Position (u) zu dem entsprechenden Nachbarn (v) weitergeht um von dort aus irgendwie weiter zum Ziel zu gelangen. Im nächsten Schritt wird nun der Knoten weiter untersucht, welcher den geringsten f-Wert besitzt.

Beispiel

Ein Beispiel für die Anwendung des A*-Algorithmus ist die Suche nach einem kürzesten Pfad auf einer Landkarte. (Im Beispiel will man in Deutschland einen kürzesten Pfad von Frankfurt nach München 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 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 München auf, so ergeben sich die folgenden Werte, welche im Beispiel die Kosten für die Funktion h(v) sein werden.

Augsburg <--> München: 43 km
Erfurt <--> München: 342 km
Frankfurt <--> München: 353 km
Karlsruhe <--> München: 260 km
Kassel <--> München: 446 km
Mannheim <--> München: 311 km
München <--> München: 0 km
Nürnberg <--> München: 151 km
Stuttgart <--> München: 199 km
Würzburg <--> München: 229 km

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 Frankfurt bis zur Stadt v und den geschätzten Kosten von dieser Stadt bis nach München zusammensetzt.

**Erster Schritt:** *Frankfurt* wurde erkundet, als nächstes wird *Mannheim* untersucht.

Im ersten Schritt werden nun alle von Frankfurt aus erreichbaren Städte betrachtet und für jede der Städte wird geschätzt wie weit es von der entsprechenden Stadt bis nach München ist. Auf diese geschätzte Weglänge wird die Weglänge um von Frankfurt in die entsprechende Stadt zu kommen addiert. Somit ist es in der momentanen Situation am vielversprechendsten von Frankfurt nach Mannheim zu gehen, da der Weg von Frankfurt über Mannheim nach München mit 396 km noch der kürzeste zu sein scheint.

**Zweiter Schritt:** *Mannheim* wurde erkundet, als nächstes wird *Karlsruhe* untersucht.

Im zweiten Schritt werden nun alle von Mannheim aus erreichbaren Städte genauer betrachtet. Von Mannheim aus gibt es nun zwei Möglichkeiten: Entweder man geht zurück nach Frankfurt, oder man geht weiter nach Karlsruhe, welches im besten Falle nur 425 km vom München entfernt ist, und somit – wenn man alle bisher bekannten Städte betrachtet – noch das vielversprechenste Ziel für die weitere Erkundung ist, da die Entfernung die man von Frankfurt aus über irgendeine der anderen Städte zurücklegen muss um nach München zu kommen auf jeden Fall größer als 425 km ist. Somit wird im nächsten Schritt Karlsruhe erkundet.

**Dritter Schritt:** *Karlsruhe* wurde erkundet, als nächstes wird *Würzburg* untersucht.

Im dritten Schritt werden nun alle Städte betrachtet welche man von Karlsruhe aus erreichen kann. Diese Städte sind zum einen Augsburg und zum anderen Mannheim, da man wenn man von Mannheim nach Karlsruhe gekommen ist, diesem Weg auch wieder zurück nach Mannheim folgen kann. Betrachtet man nun jedoch die geschätzten Kosten aller bisher entdeckten Städte, so stellt man fest, dass es nicht unbedingt das beste sein muss die Route nach Augsburg zu nehmen, da die Wegstrecke um von Frankfurt über Mannheim und Karlsruhe nach Augsburg und von dort weiter nach München zu kommen mindestens 458 km beträgt. Versucht man jedoch von Frankfurt aus direkt nach Würzburg zu kommen, so könnte die gesamte Wegstrecke von Frankfurt über Würzburg weiter nach München eventuell nur 446 km lang sein, und wäre somit 12 km kürzer als die Strecke über Augsburg. Somit wird im nächsten Schritt nun Würzburg erkundet.

**Vierter Schritt:** *Würzburg* wurde erkundet, stellte sich aber als eine schlechte Wahl dar, und es wird wieder der ursprüngliche Pfad durch *Augsburg* verfolgt.

Im vierten Schritt wird nun Würzburg erkundet und berechnet wohin man von Würzburg ausgehend kommen kann, geschätzt wie weit die neu entdeckten Städte von München entfernt sind, und die Mindestekosten um von Frankfurt via Würzburg über die Nachbarstädte von Würzburg – namentlich Nürnberg und Frankfurt – berechnet. Nach dieser Berechnung muss man feststellen, dass keine der zwei Möglichkeiten die Route durch Würzburg fortzusetzen besser ist, als die schon vorher betrachtete Route von Frankfurt über Mannheim und Karlsruhe nach Augsburg, weswegen der A*-Algorithmus als nächstes Augsburg genauer untersucht.

**Fünfter Schritt:** *Augsburg* wurde erkundet und es wurde ein Weg nach *München* gefunden der jedoch eventuell länger als nötig ist.

Im fünften Schritt wird nun Augsburg erkundet, wobei auch die Zielstadt München gefunden wird. Die Wegkosten für einen Pfad von Frankfurt via Mannheim, Karlsruhe und Augsburg nach München sind nun vollständig bekannt, betragen aber 499 km. Vergleicht man dies mit dem Pfad von Frankfurt über Würzburg und Nürnberg, so merkt man, dass man ,wenn man bei Würzburg weitersucht, vielleicht einen Weg findet der nur 471 km lang ist. Würde man also schon in diesem Schritt aufhören und sich mit der gefundenen Route zufriedengeben, so hätte man eventuell eine Strecke verwendet welche bis zu 27 km länger ist als nötig, weswegen diese Route erst weiterverfolgt wird, wenn alle anderen Strecken von Frankfurt aus im besten Fall mindestens ebenfalls 499 km lang sind. Erst dann kann man sich sicher sein, dass man auch wirklich keinen kürzeren Weg übersehen hat. Somit wird nun als nächstes Nürnberg genauer betrachtet, da dies aktuell die vielversprechenste Route ist.

**Sechster Schritt:** *Nürnberg* wurde erkundet, und es wurde ein kürzester Pfad nach *München* gefunden.

Wird nun im sechsten Schritt Nürnberg erkundet, so findet man unter all den möglichen Städten in die man von Nürnberg aus gehen kann auch die Stadt München Der Weg von Frankfurt via Würzburg über Nürnberg und schließlich nach München ist nun nur noch 487 km lang. Somit ist dieser Weg insbesondere kürzer als der im fünften Schritt bereits gefundene Weg von 499 km. Da die Stadt München nun die niedrigsten Entfernungskosten hat, wird sie im nächsten Schritt erkundet, wodurch der Algorithmus beendet ist und die Route Frankfurt, Würzburg, Nürnberg München erfolgreich als einen kürzesten Pfad von Frankfurt nach München 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 Frankfurt nach München zu kommen gar nicht erst betrachten. Weiterhin hat der Algorithmus sehr zielstrebig gearbeitet, sodass die Route von Frankfurt nach Kassel zum Beispiel gar nicht erst betrachtet wurde, da Kassel nördlich von Frankfurt liegt, man um von Frankfurt nach München zu kommen aber in südliche Richtung muss.

Algorithmus

Der A*-Algorithmus braucht um einen kürzesten Weg zu finden und zurückzugeben fünf Eingaben: Den Graph (graph) auf welchem er laufen soll, den Startknoten (start) von dem aus die Suche gestartet werden soll, der Zielknoten (goal) zu dem ein kürzester Pfad gefunden werden soll, eine Prioritätswarteschlange (S) welche alle Knoten speichert die der Algorithmus bereits kennt (und deren f-Werte daher bereits bekannt sind) aber noch nicht besucht hat, und die Heuristik h welche für jeden Knoten die Entfernung bis zum Ziel abschätzt.

Im ersten Schritt wird nun der Startknoten in die Prioritätswarteschlange eingefügt, und danach eine Schleife gestartet welche solange läuft bis entweder ein kürzester Pfad zum Ziel gefunden wurde, oder keine weiteren Knoten mehr zur Expansion zur Verfügung stehen, und somit kein Pfad zwischen dem Start- und Zielknoten existiert.

Innerhalb der Schleife wird zuerst der erste Knoten der Prioritätswarteschlange entfernt, welcher – da es sich um eine Prioritätswarteschlange handelt – auch genau der Knoten mit dem niedrigsten f-Wert ist. Dieser Knoten wird nun in die Liste der besuchten Knoten eingetragen, und es wird überprüft ob man den Algorithmus eventuell schon abbrechen kann weil man das Ziel bereits gefunden hat.

Ist dies der Fall, so wird die Hilfsfunktion reconstruct_shortest_path aufgerufen, welche ihrerseits vom Zielknoten aus rückwärts den Pfad zum Startknoten berechnet. Hierzu bekommt die Funktion den Startknoten, den Zielknoten und den Graph übergeben, und folgt nun Schritt für Schritt vom Zielknoten startend den Vorgängerzeigern. Diese Zeiger wurde während der Algorithmus Knoten expandiert hat in den Graph geschrieben, sodass die Funktion reconstruct_shortest_path für einen Knoten v nur noch direkt aus dem Graph ablesen muss von welchem Knoten u aus v besucht wurde. Nachdem nun der Vorgänger bestimmt wurde, wird dieser in einem Stack gespeichert, und reconstruct_shortest_path berechnet rekursiv den Vorgänger dieses Vorgängers, solange bis die Berechnung beim Startzustand angekommen ist. Sobald dies der Fall ist, kann der Stack – welcher nun den kürzesten Pfad vom Start zum Ziel in der richtigen Reihenfolge enthält – direkt zurückgegeben werden.

Sollte im A*-Algorithmus das Ziel jedoch noch nicht gefunden worden sein, so werden nun mittels der Funktion expand alle vom aktuellen Knoten aus direkt erreichbaren Knoten bestimmt. Bei diesem Schritt wird auch für jeden der neu Entdeckten Knoten gespeichert von welchem Knoten aus er gefunden wurde. Somit kann man, wenn der Knoten selbst später einmal expandiert, wird diese Information über den Vorgänger direkt in den Graph schreiben. Da diese Implementierung des A*-Algorithmus auf einer monotonen Heuristik aufbaut ist der erste zu jedem Knoten gewählte Pfad optimal, womit diese Methode, den Vorgänger endgültig festzulegen sobald der Knoten expandiert wird, sicher ist. Nun werden für alle neu Entdeckten Knoten noch die f-Kosten berechnet, wobei diese Berechnung nach der Anfangs bereis genannten Formel f(n) = g(n) + h(n) für einen Knoten n erfolgt. Der Wert für g(n) kann hierbei direkt aus dem Graph abgelesen werden, und untspricht dem Gewicht der Kante zwischen dem aktuellen und dem gerade gefunden Knoten, und die Funktion h(n) wird dem A*-Algorithmus mitgeliefert. Schlussendlich werden alle neu Entdeckten Knoten in die Prioritätswarteschlange einsortiert, die Schleife beginnt von vorne, und es wird wieder der Knoten mit den geringsten f-Kosten aus der Prioritätswarteschlange betrachtet.

Anmerkung: Neben der hier vorgestellten Methode den A*-Algorithmus zu Implementieren gibt es häufig auch noch Implementierungen welche eine sogenannte Closed List von bereits besuchten Knoten mitführen welche sie in jedem Schritt überprüfen. Dies ist nötig falls eine Heuristik verwendet werden soll welche zwar zulässig aber nicht monoton ist. Da diese Implementierung jedoch davon ausgeht, dass eine monotone Heuristik verwendet wird, ist der erste genutzte Pfad der zu einem beliebigen Knoten führt auf jeden Fall auch der kürzeste Pfad zu diesem Knoten. Somit ist es nicht nötig die Pfadkosten eventuell später ein zweites mal entdeckter Knoten mit den Pfadkosten, welche die Knoten bei ihrer ersten Entdeckung hatten, zu vergleichen, da die Pfadkosten bei der ersten Entdeckung garantiert niedriger waren. Die genauen Unterschiede zwischen einer monotonen Heuristik und einer zulässigen Heuristik findet man weiter unten unter Heuristiken im Artikel.

/*
 * Algorithmus zur Rekonstruktion des kürzesten Pfades
 * ---------------------------------------------------
 * P: berechneter kürzester Pfad
 * start: Startknoten
 * node: Zielknoten
 */
reconstruct_shortest_path (start, node, graph)
{
   if (node != start)
   {
      push(node, P);

      // Lese den Vorgänger des aktuellen Knoten aus
      predecessor := getPredecessor(node, graph);

      reconstruct_shortest_path (start, predecessor, graph)
   }
   else
      return P;
}

/*
 * Der eigentliche A*-Algorithmus
 * ------------------------------
 * graph: Zu untersuchender Graph
 * start: Startknoten
 * goal: Der Zielknoten
 * h: Heuristikfunktion zum Schätzen des Abstandes eines Knotens bis zum Ziel
 * S: Prioritätswarteschlange der Knoten, deren f-Wert bereits bekannt ist
 */
A-Star (graph, start, goal, h, S)
{
   insert (start,S);
   while not isEmpty(S)
   {
      current_node := pop(S);
      insert (current_node, N);
      if (current_node == goal) then
         return reconstruct_shortest_path(start,goal, graph);
      else
      {
         // Finde alle vom aktuellen Knoten aus erreichbaren Knoten
         successors := expand(current_node, graph);

         // Speichere Vorgänger des expandierten Knotens im Graph
         save_predecessor_in_graph(current_node, graph)

         forall s in sucessors do 
         {
            // Speichere Knoten von dem aus s erkundet wurde
            predecessor(s) := current_node;

            // Berechne und speichere die f-Kosten
            f(s) := g(s) + h(s);

            insert(s,S);
         }
      }
   }
   // Es konnte kein Pfad gefunden werden
   return fail;
}

Heuristiken

Bei Heuristiken für den A*-Algorithmus unterscheidet man zwischen zwei Sorten: Einmal die zulässigen Heuristiken, welche zwar die Kosten bis zum Ziel nie überschätzen, aber die Kosten um von einem Knoten zum nächsten zu kommen durchaus überschätzen dürfen, und die monotonen Heuristiken auf der anderen Seite, welche nicht nur die Entfernung bis zum Ziel nie überschätzen, sondern auch die Kosten zwischen zwei Knoten immer unterschätzen. Wenn eine Heuristik monoton ist, so ist dies also eine stärkere Aussage ,als wenn sie nur zulässig wäre. Es ist zwar möglich Heuristiken zu konstruieren welche zwar monoton aber nicht zulässig sind, jedoch sind diese Heuristiken in der Regel sehr selten. Die Heuristik um die Entfernung zwischen zwei Städten zu schätzen – die Luftlinie zwischen diesen beiden Städten – ist zum Beispiel monoton. So kann man keinen Weg finden um von einer Stadt in eine andere zu kommen, der kürzer wäre als die direkte Luftlinie zwischen diesen beiden Städten.

Die wichtigste Konsequenz dieser Unterscheidung bei der Heuristiken tritt bei der Implementierung des A*-Algorithmus zu Tage: Sollte man nur eine zulässige Heuristik verwenden, so kann es passieren dass die Entfernung zwischen zwei Knoten u und v überschätzt wird, und der Algorithmus somit den Knoten v auf einem Umweg über den Knoten w erreicht. Dies hat nun aber zur Folge dass die berechnete Entfernung zwischen u und v nicht optimal ist, da der Weg über w nach Annahme ein Umweg war. Lässt man den Algorithmus noch einige Zeit laufen, so wird er jedoch auch die direkte Verbindung zwischen u und v finden, wodurch nun zwei Pfade gefunden wurden um von u nach v zu kommen. Da die gewählte Heuristik aber nur zulässig und nicht monoton war kann nicht mehr garantiert werden dass der erste gefundene Pfad zum Knoten vtatsächlich der kürzeste war. Somit muss man nun die Kosten für die beiden Pfade um von u nach v zu kommen vergleichen, um am ende den Pfad zu wählen welcher kürzer war. Wählt man jedoch eine monotone Heuristik, so ist dieser Schritt unnötig, da der erste entdeckte Pfad von zu einem Knoten v auf jeden Fall auch der kürzestmögliche Pfad ist.

Die gewählte Heuristik hat ebenfalls große Auswirkungen auf die Laufzeit des A*-Algorithmus. Auf der einen Seite gibt es die perfekte Heuristik, welche in jedem Schritt die tatsächlichen Kosten für einen Knoten bis zum Ziel als Schätzwert abgibt, wodurch der A*-Algorithmus nur die Knoten erkunden wird, welche auch tatsächlich auf dem kürzesten Pfad liegen. Eine solch genaue Heuristik ist aber in der Berechnung extrem teuer, da man dazu erst einmal für jeden Knoten den kürzesten Pfad bis zum Ziel finden muss. Auf der anderen Seite gibt es extrem schlechte aber dafür sehr einfach zu berechnende Heuristiken. So kann man die Entfernung zwischen zwei Knoten mit Kosten von 0 schätzen, wodurch effektiv gar keine Heuristik mehr verwendet wird, und der A*-Algorithmus alle Knoten blind untersuchen muss bis er durch Zufall das Ziel findet. Diese Version des Algorithmus ist besser als der Algorithmus von Dijkstra bekannt. Eine gute Heuristik stellt somit einen Kompromiss zwischen dem Berechnungsaufwand für die Heuristik und ihrer Genauigkeit dar.

Optimalitätsbeweis

Wie bereits erwähnt ist eine gute Heuristik eine der wichtigsten Voraussetzungen damit der A*-Algorithmus effizient arbeiten kann. Setzt man weiterhin voraus, dass die verwedete Heuristik monoton ist – also sowohl die Kosten bis zum Ziel, als auch die Kosten zwischen zwei beliebigen Knoten nie überschätzt – und dass der Graph keine negativen Kantengewichte besitzt, so kann man beweisen dass der A*-Algorithmus immer einen kürzesten Pfad vom Start zum Ziel findet. Betrachtet man die Vorgehensweise des Algorithmus, so sieht man, dass immer erst jene Knoten u betrachtet werden welche die niedrigsten f-Kosten haben. Da die Heuristik, welche zur Berechnung der f-Kosten herangezogen wird, aber nach Voraussetzung die tatsächlichen Kosten nie überschätzt, und die Kosten, um zu dem aktuell zu schätzenden Knoten u zu kommen, bekannt sind (da der Algorithmus schon einen Weg vom Startknoten zu u gefunden hat), ist auch der endgültige f-Wert für u eine optimistische Schätzung, welche garantiert nicht über den tatsächlichen Kosten liegen wird. Gibt es nun einen Knoten a mit f(a) = 450, so wird dieser Knoten erst weiter erkundet wenn alle anderen Knoten x erkundet wurden für die gilt f(x) < 450. Somit kann der Algorithmus keine Knoten auslassen welche schneller zum Ziel führen könnten. Würde man jedoch negative Kantengewichte zulassen, so könnten hinter dem Knoten mit Kosten von 450 durchaus noch weitere Knoten existieren welche – durch negative Kantengewichte – f-Kosten von weniger als 450 haben. Schreibt man diese Überlegungen nun formal auf, so ergibt sich der formale Beweis der Optimalität des A*-Algorithmus:

Zu zeigen: Der A*-Algorithmus findet immer einen kürzesten Pfad

Annahme: Der A*-Algorithmus findet eine suboptimale Lösung G₂, wobei die optimale Lösung G₁ Kosten von C₁ hat.

Da für alle Zielknoten gilt dass die geschätzte Entfernung vom Zielknoten bis zum Zielknoten 0 ist, gilt insbesondere:

h(G₂) = 0

Da $G_{2}$ nach Annahme eine suboptimale Lösung ist gilt nun aber folgende Gleichung:

f(G₂) = g(G₂) + h(G₂) = g(G₂) > C₁

Betrachtet man nun einen beliebigen Knoten n auf dem kürzesten Pfad zum optimalen Ziel G₁ und die Tatsache dass die Heuristik die tatsächlichen Kosten niemals überschätzt, gilt:

f(n) = g(n) + h(n) ≤ C₁

Fasst man nun die beiden Gleichungen zusammen, so erhält man:

f(n) ≤ C₁ < f(G₂)

Dies bedeutet aber nun dass der A*-Algorithmus den Knoten G₂ niemals erkundet bevor er die optimale Lösung (G₁) findet. Somit findet der Algorithmus zuerst die Lösung $G_{1}$ , und berechnet damit tatsächlich einen kürzesten Pfad.

Anwendungsgebiete

Der A*-Algorithmus wird 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: Künstliche Intelligenz - Ein moderner Ansatz, 2004, Prentice Hall, ISBN 3-8273-7089-2
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.

Weblinks

Vorlage:Kandidat (Lesenswert)