Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 18. November 2007 um 03:04 Uhr durch Sargeras(Diskussion | Beiträge)(falsches ref tag entfernt). Sie kann sich erheblich von der aktuellen Version unterscheiden.
Im Gegensatz zu uninformierten Suchalgorithmen verwendet der A*-Algorithmus eine Schätzfunktion (Heuristik), um zielgerichtet zu suchen. Bei Verwendung einer geeigneten Heuristik ist der Algorithmus optimal. Das heißt, es wird immer die optimale Lösung gefunden, falls eine existiert.
Funktionsweise
Der A*-Algorithmus untersucht immer die Knoten zuerst, die wahrscheinlich zum Ziel führen. Um den vielversprechendsten Knoten zu ermitteln, wird allen bekannten Knoten ein Wert zugeordnet, der angibt, wie lange der Pfad zum Ziel unter Verwendung des betrachteten Knoten im günstigsten Fall ist. Der Knoten mit dem niedrigsten Wert wird als nächstes untersucht.
Für einen Knoten bezeichnet die bisherigen Kosten vom Startknoten aus, um zu erreichen. bezeichnet die geschätzten Kosten bis zum Zielknoten. Um den Knoten mit dem niedrigsten Wert effizient ermitteln zu können, wird meist eine Prioritätswarteschlange verwendet.
Die verwendete Heuristik darf die Kosten nie überschätzen. Für das Beispiel der Wegsuche ist die Luftlinie eine geeignete Schätzung: Die tatsächliche Strecke ist nie kürzer als die direkte Verbindung. Außerdem ist diese Heuristik monoton. Der Unterschied zwischen zulässiger und monotoner Heuristik wird im Abschnitt Heuristiken weiter unten erklärt.
Algorithmus
Der A*-Algorithmus erhält vier Eingaben: Den Graphen (G), auf welchem er laufen soll, den Startknoten (s), von dem aus die Suche gestartet werden soll, der Zielknoten (z), zu dem ein kürzester Pfad gefunden werden soll und die Heuristik (h), welche für jeden Knoten die Entfernung bis zum Ziel abschätzt. Als Datenstruktur braucht er außerdem eine Prioritätswarteschlange (Q), in der er die noch zu betrachtenden Knoten abspeichert.
Im ersten Schritt wird der Graph initialisiert, wobei die Entfernungen zu allen Knoten auf unendlich gesetzt werden, und die Entfernung zum Startknoten auf Null gesetzt wird. Danach wird der Startknoten in die Prioritätswarteschlange eingefügt, und eine Schleife gestartet, welche solange läuft, bis entweder ein kürzester Pfad zum Ziel gefunden wurde oder jeder Knoten bereits einmal betrachtet wurde (d.h. die Prioritätswarteschlange ist leer). Tritt der zweite Fall ein, so kann man daraus schließen, dass kein Pfad zwischen dem Start- und Zielknoten existiert.
Innerhalb der Schleife wird zuerst der erste Knoten k der Prioritätswarteschlange entfernt, welcher – da es sich um eine Prioritätswarteschlange handelt – auch genau der Knoten mit dem niedrigsten f-Wert ist. Nun wird überprüft ob k gleich dem Zielknoten z ist, also ob man den Algorithmus eventuell schon abbrechen kann. Kann kein Knoten entfernt werden, da Q bereits leer ist, so terminiert der Algorithmus ebenfalls, da kein Weg von Start zu Zielknoten existieren kann. Eine genauere Begründung findet man unter Optimalitätsbeweis weiter unten im Artikel.
Terminiert der Algorithmus, weil er das Ziel gefunden hat, 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 wurden, 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. reconstruct_shortest_path berechnet solange rekursiv den Vorgänger dieses Vorgängers, 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 alle vom aktuellen Knoten u aus direkt erreichbaren Knoten v bestimmt, und die Kanten zu diesen Knoten relaxiert. Falls die Entfernung eines entdeckten Knoten v noch unendlich ist ,so wird sowohl gespeichert von welchem Knoten aus v gerade erkundet wurde (Vorgängerzeiger), als auch sein f-Wert nach der Formel f(v) = g(u) + w(u,v) + h(v) angepasst. Den Wert für g(u) kann man hierbei genau wie das Gewicht der Kante zwischen u und v direkt aus dem Graph ablesen. Die Berechnung von h(v) ist einfach, da sie dem A*-Algorithmus direkt mitgeliefert wird.
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 welcher expandiert wird führt auf jeden Fall auch der kürzeste Pfad zu diesem Knoten. Somit ist es nicht nötig die Pfadkosten entdeckter Knoten eventuell später ein zweites mal 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.
/*
* Rekonstruktion des kürzesten Pfades
* -----------------------------------
* p: berechneter kürzester Pfad
* n: Zielknoten
*/
reconstructShortestPath (n)
{
p := new stack; // leer initialisieren
// Prüfe ob schon beim Startknoten angekommenwhile (π(n) != NIL))
{
// Füge Knoten dem Pfad hinzu
push(n, p);
// Mache dasselbe für den Vorgängerknoten
n := π(n);
}
// Liefere den gefundenen Pfad zurückreturn p;
}
/*
* Initialisieren des Graphen
* --------------------------
* G: Zu untersuchender Graph
* s: Startknoten
*/
initialize(G, s)
{
// Setze Entfernung zu allen Knoten auf Unendlich
forall v do
d[v] := ∞
// Setze Entfernung zum Startknoten auf Null
d[s] := 0;
}
/*
* Relaxieren einer Kante
* ----------------------
* u: Knoten der gerade expandiert wurde
* v: Aktuell betrachteter Nachfolger von u
* w: Gewichtsfunktion zum Berechnen der Kosten für eine Kante
* f: Kombination der Abstandsfunktion d mit der Heuristik h (f[v] = d[v] + h[v])
*/
relax(u,v,w,h)
{
// Prüfe ob der Weg über u zu v kürzer ist als der aktuelleif f[v] = ∞ {
// v noch nicht besucht
// Berechne den f-Wert von v
f[v] := d[u] + w(u,v) + h[v];
// Aktualisiere Vorgänger in kürzestem Pfad
π[v] := u;
// Aktualisiere Distanz zu v
d[v] := d[u] + w(u,v);
// trage v in die Prioritätswarteschlange
// Q mit Priorität f[v] ein
insert(Q, v, f[v]);
}
else
; // Ändere nichts, da bereits besserer Pfad bekannt
}
/*
* Der eigentliche A*-Algorithmus
* ------------------------------
* G: Zu untersuchender Graph
* s: Startknoten
* z: Der Zielknoten
* w: Gewichtsfunktion zum Berechnen der Kosten für eine Kante
* f: Kombination der Abstandsfunktion d mit der Heuristik h (f[v] = d[v] + h[v])
* Q: Prioritätswarteschlange der Knoten, deren f-Wert bereits bekannt ist
*/
A-Star (s, z, w, h, G) {
01 initialize(G, s);
02 insert(Q, s, 0) // Füge den Startknoten in die Warteschlage ein
03 whilenot isEmpty(Q) {
04 // Betrachte Knoten mit geringsten Abstand zum Startknoten
05 u := pop(Q);
06 if (u == z) then
07 return reconstructShortestPath(g);
08 else {
09 // Betrachte alle vom aktuellen Knoten u aus erreichbaren Knoten (Nachfolger)
10 forall v := successors(u) do {
11 // relaxiere die Kante zwischen u und seinem Nachfolger
12 relax(u, v, w, h);
13 }
14 }
15 }
16 // Es konnte kein Pfad gefunden werden
17 return fail;
18 }
Beispiel
Beispiellandkarte von Deutschland mit den Entfernungen zwischen den einzelnen Städten.
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 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, so dass 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 folgenden 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 Mindestkosten 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 28 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 musste 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.
Zeitkomplexität
Die Zeitkomplexität des A*-Algorithmus hängt sehr stark von der verwendeten Heuristik ab. Ist die Heuristik nicht monoton, so kann die Komplexität im Prinzip exponentiell sein. Der Grund ist, dass mit einer nicht-monotonen Heuristik ein Knoten mehrfach kann behandelt werden. Geht man allerdings von einer monotonen Heuristik aus, dann ist die Zeitkomplexität des Algorithmus leichter zu schätzen. Verwendet man hier einen Fibonacci-Heap, um die noch nicht besuchten Knoten Q zu speichern, so hat der Algorithmus insgesamt eine Laufzeit von .
Diese Laufzeit ergibt sich wie folgt:
In der zweiten Zeile wird die Prioritätswarteschlange mit allen Knoten aus dem Graph gefüllt. Um viele Knoten in einer durch einen Fibonacci Heap dargestellten Prioritätswarteschlange zu speichern benötigt man Zeit .
In der dritten Zeile wird eine Schleife gestartet, welche im schlimmsten Fall mal durchlaufen wird. In Zeile fünf wird das Minimum aus der Prioritätswarteschlange entnommen, wobei das Entfernen des Minimums aus einem Fibonacci Heap Zeit kostet. Die zehnte Zeile kostet Schlussendlich noch einmal Laufzeit , da jeder Knoten nur einmal betrachtet wird, und somit auch jede Kante nur einmal betrachtet werden kann, weswegen relax insgesamt maximal mal aufgerufen wird. Ein Aufruf von relax selbst verursacht jedoch nur konstante Kosten, da das setzen von Pointern in kostanter Zeit geht, und das eventuell nötige verringern der Entfernung eines Knotens und seine damit verbundene Positionsänderung in der Prioritätswarteschlange Q mittels eines Fibonacci Heaps ebenfalls in Konstanter Zeit möglich ist.
Insgesamt ergibt sich somit eine Komplexität von .
Heuristiken
Man unterscheidet zwei Arten von Heuristiken für den A*-Algorithmus: Zulässige und monotone Heuristiken. Zulässige Heuristiken dürfen zwar nie die Kosten bis zum Ziel, aber sehr wohl die Kosten von einem Knoten zum nächsten, überschätzen. Monotone Heuristiken dürfen weder die einen noch die anderen Kosten überschätzen; Monotonie ist also eine stärkere Eigenschaft als die der Zulässigkeit. Es ist zwar möglich, Heuristiken zu konstruieren, die zulässig aber nicht monoton sind, jedoch kommen diese Heuristiken in der Praxis sehr selten vor. Die Heuristik zur Abschätzung der Entfernung zweier Städte – die Luftlinie – ist zum Beispiel monoton: Man kann keinen Weg von der einen Stadt zur anderen finden, der kürzer wäre als die Luftlinie der betrachteten Städte.
Die wichtigste Konsequenz dieser Unterscheidung beider 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 v tatsä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 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 sinnlos, und in der Berechnung extrem teuer, da man für sie erst einmal für jeden Knoten den kürzesten Pfad bis zum Ziel finden muss, was genau der ursprünglich zu lösenden Problemstellung entspricht. 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 irgendwann auf diese Weise 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 verwendete 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 G2, wobei die optimale Lösung G1 Kosten von C1 hat.
Da für alle Zielknoten gilt dass die geschätzte Entfernung vom Zielknoten bis zum Zielknoten 0 ist, gilt insbesondere:
h(G2) = 0
Da nach Annahme eine suboptimale Lösung ist gilt nun aber folgende Gleichung:
f(G2) = g(G2) + h(G2) = g(G2) > C1
Betrachtet man nun einen beliebigen Knoten n auf dem kürzesten Pfad zum optimalen Ziel G1 und die Tatsache dass die Heuristik die tatsächlichen Kosten niemals überschätzt, gilt:
f(n) = g(n) + h(n) ≤ C1
Fasst man nun die beiden Gleichungen zusammen, so erhält man:
f(n) ≤ C1 < f(G2)
Dies bedeutet aber nun dass der A*-Algorithmus den Knoten G2 niemals erkundet bevor er die optimale Lösung (G1) findet. Somit findet der Algorithmus zuerst die Lösung , und berechnet damit tatsächlich einen kürzesten Pfad.
Anwendungsgebiete
Anwendung findet der A*-Algorithmus bei der Berechnung eines kürzesten Pfades zwischen zwei Punkten, wie zum Beispiel bei der Wegberechnung eines Routenplaners in einem Auto oder via Internet. Auch in Computerspielen wird der Algorithmus häufig verwendet, zum Beispiel, wenn der Spieler einer Einheit den Befehl gibt zu einem bestimmten Punkt zu gehen, und somit ein Weg für diese Einheit berechnet werden muss. Dieses Beispiel kann man auch auf Roboter oder Software-Agenten, welche selbstständig einen Weg in einer vorgegebenen Welt finden sollen, verallgemeinern.
Andere Verfahren zur Berechnung kürzester Pfade
Eine Erweiterung von A* ist D* (dynamischer A*), der besonders in dynamischen bzw. unbekannten Umgebungen Anwendung findet.
Hat man keine Heuristik oder kein bestimmtes Ziel (z.B. nächste Tankstelle), kann der Algorithmus von Dijkstra verwendet werden.
Der Bellman-Ford-Algorithmus berechnet alle kürzesten Pfade von einem Knoten zu allen anderen Knoten in einem Graphen mit negativen Kantengewichten.
Sucht man nicht nur die kürzesten Pfade eines Knotens zu allen anderen Knoten im Graph, sondern die kürzesten Pfade zwischen allen Knotenpaaren, so ist der Algorithmus von Floyd und Warshall geeignet.
Ferner sollte hier auch der Ameisenalgorithmus erwähnt werden.
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.
