W i l l k o m m e n   b e i   [ www.mauspfeil.com ]
 
 



 

Wörterbuch der Bedeutung
<<Zurück
Bitte wählen Sie einen Buchstaben:
A, Ä | B | C | D | E | F | G | H | I | J | K | L | M | N | O, Ö | P | Q | R | S | T | U, Ü | V | W | X | Y | Z | 0-9

Suchen:

(Groß-/Kleinschreibung wird nicht unterschieden)

Google


A*-Algorithmus

*** Shopping-Tipp: A*-Algorithmus

Der '''A*-Algorithmus''' (''a-star'') dient in der Informatik der Berechnung eines Kürzester Pfad kürzesten Pfades zwischen zwei Glossar Graphentheorie#Knoten Knoten in einem Glossar Graphentheorie#Graph Graphen mit positiven Kantengewichten. Er wurde das erste mal 1968 von Peter Hart, Nils Nilsson und Bertram Raphael beschrieben. Beim A*-Algorithmus handelt es sich um eine sogenannte Informierter Suchalgorithmus informierte Suche, was heißt, dass der Algorithmus auf eine Heuristik zurückgreift, um zielgerichtet zu suchen, wodurch er – im Gegensatz zu Uninformierter Suchalgorithmus uninformierten Suchalgorithmen – zuerst jene Knoten untersucht, welche am Wahrscheinlichkeit wahrscheinlichsten zum Ziel führen.

Allgemeines
Die Besonderheit des A*-Algorithmus ist, dass er im Gegensatz zu den ''uninformierten Suchalgorithmen'' zielgerichtet sucht. Er betrachtet von den vielen möglichen Knoten, die zum Ziel führen könnten, tatsächlich nur sehr wenige, und findet das Ziel daher im allgemeinen sehr schnell. Die Abschätzung, welche Knoten am wahrscheinlichsten zum Ziel führen, liefert jedoch erst eine Heuristik, die Annahmen über den Graphen, auf dem der A*-Algorithmus angewendet werden soll, ermöglicht. Der Algorithmus arbeitet hierbei umso effizienter, 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. Fordert man von der Heuristik, dass sie ''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 nicht mit Sicherheit den kürzesten Weg zum Ziel findet, falls man eine sehr schlechte Heuristik verwendet. Ein formaler Beweis der Optimalität des Algorithmus findet sich im Abschnitt #Optimalitätsbeweis Optimalitätsbeweis weiter unten im Artikel. '''Anmerkung:''' Modifiziert man den A*-Algorithmus geringfügig, so reicht es 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 Beschreibung der Unterschiede zwischen ''monotonen'' und ''zulässigen'' Heuristiken findet sich im Abschnitt #Heuristiken Heuristiken weiter unten im Artikel.

Funktionsweise
Wendet man den A*-Algorithmus auf einem Knoten ''u'' an, so wird für jeden von diesem Knoten aus erreichbaren Nachbarn durch die Heuristik eine Schätzung abgegeben, wie teuer es ist, von diesem 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 ''g(v)'' für die bisherigen gesamten Wegkosten vom Start zum Knoten ''v'', ''h(v)'' für die von der Heuristik für Knoten ''v'' geschätzten Kosten bis zum Ziel, und ''f(v)'' steht demnach für die geschätzten Gesamtkosten, um vom Startknoten über ''v'' zum Ziel zu gelangen. Im nächsten Schritt wird nun der Knoten weiter untersucht, der den geringsten ''f''-Wert besitzt.

Algorithmus
Der A*-Algorithmus erhält vier Eingaben: Den Graph (''G''), auf welchem er laufen soll, den Startknoten (''s''), von dem aus die Suche gestartet werden soll, der Zielknoten (''g''), 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 nicht besuchten Knoten speichert. 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 werden alle Knoten des Graphen in die Prioritätswarteschlange eingefügt, und eine Schleife (Programmierung) Schleife gestartet, welche solange läuft, bis entweder ein kürzester Pfad zum Ziel gefunden wurde oder jeder Knoten bereits einmal betrachtet wurde. 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 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. Der Algorithmus kann hier aus zweierlei Gründen abgebrochen werden: Einerseits kann es sein, dass der eben besuchte Knoten schon einmal besucht wurde, was aufgrund der ''monotonen Heuristik'' jedoch eigentlich nicht hätte passieren dürfen. Expandiert der A* Algorithmus einen Knoten trotzdem zum zweiten mal, so kann es keinen Weg vom Start zum Ziel geben, da dieser Weg sonst vorher gefunden worden wäre. Eine genauere Begründung findet man unter #Optimalitätsbeweis 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 Stapelspeicher 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 bestimmt, und die Kanten zu diesen Knoten ''relaxiert''. Bei diesem Schritt wird für jeden der entdeckten Knoten ''v'' geprüft ob der gerade entdeckte Pfad besser ist als der bereits bekannte. Falls dies der Fall ist, 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 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 angekommen'' '''while''' (π(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ück'' '''return''' 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 aktuelle'' '''if''' f[v] > d[u] + w(u,v) + h[v] { // ''Neuer weg kürzer als bisher gefundener Weg'' // ''Aktualisiere geschätzte restliche Weglänge'' f[v] := d[u] + w(u,v) + h[v]; // ''Aktualisiere Vorgänger in kürzestem Pfad'' π[v] := u; } '''else''' ; // ''Ändere nichts, da bereits besserer Pfad bekannt } /* * Der eigentliche A*-Algorithmus * ------------------------------ * G: Zu untersuchender Graph * s: Startknoten * g: 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, g, w, h, G) { 01 initialize(G, s); 02 Q := V[G]; // ''Füge alle Knoten aus dem Graph in die Warteschlage ein'' 03 '''while''' '''not''' isEmpty(Q) { 04 // Betrachte Knoten mit geringsten Abstand zum Startknoten 05 u := pop(Q); 06 '''if''' (u == g) '''then''' 07 '''return''' reconstructShortestPath(g); 08 '''else''' { 09 // ''Betrachte alle vom aktuellen Knoten u aus erreichbaren Knoten (Nachfolger)'' 10 '''forall''' v := sucessors(u) do { 11 // ''relaxiere die Kante zwischen u und seinem Nachfolger'' 12 relax(u, v, w, h); 13 } 14 } 15 } 15 // ''Es konnte kein Pfad gefunden werden'' 16 '''return''' fail; 17 }

Beispiel
{| |Bild:MapGermanyGraph.svg 275px|thumb|right|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 am Main 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. {| |Bild:A-Star2.svg thumb|275px|left|'''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. |} {| |Bild:A-Star3.svg thumb|275px|right|'''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. |} {| |Bild:A-Star4.svg thumb|275px|left|'''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. |} {| |Bild:A-Star5.svg thumb|275px|right|'''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. |} {| |Bild:A-Star6.svg thumb|275px|left|'''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. |} {| |Bild:A-Star7.svg thumb|275px|right|'''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, da ''Kassel'' nördlich von ''Frankfurt'' liegt, man um von ''Frankfurt'' nach ''München'' zu kommen aber in südliche Richtung muss. |}

Zeitkomplexität
Die Zeitkomplexität des A*-Algorithmus hängt sehr stark von der Datenstruktur ab, welche man verwendet um die noch nicht besuchten Knoten ''Q'' zu speichern. Verwendet man hier einen Fibonacci-Heap, so hat der Algorithmus insgesamt eine Laufzeit von O(\vert V \vert log \vert V \vert + \vert E \vert) Diese Laufzeit ergibt sich wie folgt: In der zweiten Zeile wird die Prioritätswarteschlange mit allen Knoten aus dem Graph gefüllt. Um \vert V \vert viele Knoten in einer durch einen Fibonacci Heap dargestellten Prioritätswarteschlange zu speichern benötigt man Zeit O(\vert V \vert). In der dritten Zeile wird eine Schleife gestartet, welche im schlimmsten Fall \vert V \vert 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 O(log \vert V \vert) kostet. Die zehnte Zeile kostet Schlussendlich noch einmal Laufzeit O(\vert E \vert), da jeder Knoten nur einmal betrachtet wird, und somit auch jede Kante nur einmal betrachtet werden kann, weswegen ''relax'' insgesamt maximal O(\vert E \vert) 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 O(\vert V \vert log \vert V \vert + \vert E \vert)

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 G_2 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 G_1, 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
Hat man keine Heuristik, um die Entfernung der Knoten abzuschätzen, kann man statt des A*-Algorithmus den Algorithmus von Dijkstra verwenden. Um alle kürzesten Pfade von einem Knoten zu allen anderen Knoten in einem Graph mit negativen Kantengewichten zu berechnen, kann der Bellman-Ford-Algorithmus verwendet werden. 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 kann man den Algorithmus von Floyd und Warshall verwenden.

Literatur
*Stuart Russell, Peter Norvig: ''[http://aima.cs.berkeley.edu/ 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"'', Association for Computing Machinery SIGART Newsletter, 37, pp. 28-29, 1972.

Weblinks

- Ausführlicher Grundlagenartikel zum Thema A*-Algorithmus
- Seite über A*-Algorithmus und Wegfindung im allgemeinen (englisch)
- Praktische Beschreibung und Java-Applet zum A*-Algorithmus
- Einzelschrittsimulation in VB 6 (englisch), implementiert als DLL, mit GUI
- Uni-Seminararbeit zum Thema 3D-Pathfinding (Schwerpunkt Spieleentwicklung, deutsch)
- Visualisierung des A*-Algorithmus (Hauptseminar, deutsch) {{Lesenswert}} Kategorie:Graphentheorie Kategorie:Suchalgorithmus en:A* search algorithm es:Algoritmo de búsqueda A* fi:A*-algoritmi fr:Algorithme A* it:A* ja:A* nl:A*-algoritme pl:Algorytm A* pt:Algoritmo A* vi:Giải thuật tìm kiếm A*

*** Shopping-Tipp: A*-Algorithmus




[Der Artikel zu A*-Algorithmus stammt aus dem Nachschlagewerk Wikipedia, der freien Enzyklopädie. Dort findet sich neben einer Übersicht der Autoren die Möglichkeit, den Original-Text des Artikels A*-Algorithmus zu editieren.
Die Texte von Wikipedia und dieser Seite stehen unter der GNU Free Documentation License.]

<<Zurück | Zur Startseite | Impressum | Zum Beginn dieser Seite