Der A*-Algorithmus („A Stern“ oder englisch „a star“, auch A*-Suche) gehört zur Klasse der informierten Suchalgorithmen. Er 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 J. Nilsson und Bertram Raphael beschrieben. Der Algorithmus gilt als Verallgemeinerung und Erweiterung des Dijkstra-Algorithmus, in vielen Fällen kann aber umgekehrt A* auch auf Dijkstra reduziert werden.
Im Gegensatz zu uninformierten Suchalgorithmen verwendet der A*-Algorithmus eine Schätzfunktion (Heuristik), um zielgerichtet zu suchen und damit die Laufzeit zu verringern. Der Algorithmus ist vollständig und optimal. Das heißt, dass immer eine optimale Lösung gefunden wird, falls eine existiert.
Idee des Algorithmus Bearbeiten
Der A*-Algorithmus untersucht immer die Knoten zuerst, die wahrscheinlich schnell zum Ziel führen. Um den vielversprechendsten Knoten zu ermitteln, wird allen bekannten Knoten jeweils durch eine Metrik ein Wert zugeordnet, der eine Abschätzung angibt, wie lang der Pfad vom Start zum Ziel unter Verwendung des betrachteten Knotens im günstigsten Fall ist. Der Knoten mit dem niedrigsten -Wert wird als nächster untersucht.
Für einen Knoten bezeichnet die bisherigen Kosten vom Startknoten aus, um zu erreichen. bezeichnet die geschätzten Kosten von bis zum Zielknoten. 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.
Funktionsweise Bearbeiten
Die Knoten werden während der Suche in drei verschiedene Klassen eingeteilt:
- unbekannte Knoten: Diese Knoten wurden während der Suche noch nicht gefunden. Zu ihnen ist noch kein Weg bekannt. Jeder Knoten (außer dem Startknoten) ist zu Beginn des Algorithmus unbekannt.
- bekannte Knoten: Zu diesen Knoten ist ein (möglicherweise suboptimaler) Weg bekannt. Alle bekannten Knoten werden zusammen mit ihrem -Wert in der sogenannten Open List gespeichert. Aus dieser Liste wird immer der vielversprechendste Knoten ausgewählt und untersucht. Die Implementierung der Open List hat großen Einfluss auf die Laufzeit und wird oft als einfache Prioritätswarteschlange (z. B. binärer Heap) realisiert. Zu Beginn ist nur der Startknoten bekannt.
- abschließend untersuchte Knoten: Zu diesen Knoten ist der kürzeste Weg bekannt. Die abschließend untersuchten Knoten werden in der sogenannten Closed List gespeichert, damit sie nicht mehrfach untersucht werden. Um effizient entscheiden zu können, ob sich ein Element auf der Closed List befindet, wird diese oft als Menge implementiert. Die Closed List ist zu Beginn leer.
Jeder bekannte oder abschließend besuchte Knoten enthält einen Zeiger auf seinen (bisher besten) Vorgängerknoten. Mit Hilfe dieser Zeiger kann der Pfad bis zum Startknoten rückverfolgt werden.
Wird ein Knoten abschließend untersucht (auch expandiert oder relaxiert), so werden seine Nachfolgeknoten in die Open List eingefügt und in die Closed List aufgenommen. Für neu eingefügte Nachfolgeknoten werden die Vorgängerzeiger auf gesetzt. Ist ein Nachfolgeknoten bereits auf der Closed List, so wird er nicht erneut in die Open List eingefügt und auch sein Vorgängerzeiger nicht geändert. Ist ein Nachfolgeknoten bereits auf der Open List, so wird der Knoten nur aktualisiert (-Wert und Vorgängerzeiger), wenn der neue Weg dorthin kürzer ist als der bisherige.
Falls der Zielknoten abschließend untersucht wird, terminiert der Algorithmus. Der gefundene Weg wird mit Hilfe der Vorgängerzeiger rekonstruiert und ausgegeben. Falls die Open List leer ist, gibt es keine Knoten mehr, die untersucht werden könnten. In diesem Fall terminiert der Algorithmus, da es keine Lösung gibt.
Bedingt durch die Vorgängerzeiger wird der gefundene Weg vom Ziel ausgehend rückwärts bis zum Start ausgegeben. Um den Weg in der richtigen Reihenfolge zu erhalten, kann z. B. vor der Wegsuche Start und Ziel vertauscht werden. Somit wird vom eigentlichen Ziel zum Start gesucht und die Wegausgabe beginnt beim ursprünglichen Startknoten.
declare openlist as PriorityQueue with Nodes // Prioritätenwarteschlange declare closedlist as Set with Nodes program a-star // Initialisierung der Open List, die Closed List ist noch leer // (die Priorität bzw. der f-Wert des Startknotens ist unerheblich) openlist.enqueue(startknoten, 0) // diese Schleife wird durchlaufen bis entweder // - die optimale Lösung gefunden wurde oder // - feststeht, dass keine Lösung existiert repeat // Knoten mit dem geringsten f-Wert aus der Open List entfernen currentNode := openlist.removeMin() // Wurde das Ziel gefunden? if currentNode == zielknoten then return PathFound // Der aktuelle Knoten soll durch nachfolgende Funktionen // nicht weiter untersucht werden, damit keine Zyklen entstehen closedlist.add(currentNode) // Wenn das Ziel noch nicht gefunden wurde: Nachfolgeknoten // des aktuellen Knotens auf die Open List setzen expandNode(currentNode) until openlist.isEmpty() // die Open List ist leer, es existiert kein Pfad zum Ziel return NoPathFound end
// überprüft alle Nachfolgeknoten und fügt sie der Open List hinzu, wenn entweder // - der Nachfolgeknoten zum ersten Mal gefunden wird, oder // - ein besserer Weg zu diesem Knoten gefunden wird function expandNode(currentNode) foreach successor of currentNode // wenn der Nachfolgeknoten bereits auf der Closed List ist – tue nichts if closedlist.contains(successor) then continue // g-Wert für den neuen Weg berechnen: g-Wert des Vorgängers plus // die Kosten der gerade benutzten Kante tentative_g = g(currentNode) + c(currentNode, successor) // wenn der Nachfolgeknoten bereits auf der Open List ist, // aber der neue Weg nicht besser ist als der alte – tue nichts if openlist.contains(successor) and tentative_g >= g(successor) then continue // Vorgängerzeiger setzen und g Wert merken oder anpassen successor.predecessor := currentNode g(successor) = tentative_g // f-Wert des Knotens in der Open List aktualisieren // bzw. Knoten mit f-Wert in die Open List einfügen f := tentative_g + h(successor) if openlist.contains(successor) then openlist.updateKey(successor, f) else openlist.enqueue(successor, f) end end
Anwendungsgebiete Bearbeiten
Der A*-Algorithmus findet allgemein einen optimalen Pfad zwischen zwei Knoten in einem Graphen. Optimal kann dabei am kürzesten, am schnellsten oder auch am einfachsten bedeuten, je nach Art der Gewichtungsfunktion, die den Kanten ihre Länge zuordnet. Theoretisch kann der Algorithmus alle Probleme lösen, die durch einen Graphen dargestellt werden können und bei denen eine Schätzung über die Restkosten bis zum Ziel gemacht werden kann. Zu den Beschränkungen von A* siehe den Abschnitt Nachteile.
A* wird oft zur Wegsuche bei Routenplanern oder in Computerspielen benutzt. Als Heuristik wird dabei meist der Luftlinienabstand zum Ziel verwendet, da er auf Grund der Dreiecksungleichung stets optimistisch schätzt. Weitere Anwendungsgebiete sind Spiele wie das 15-Puzzle oder das Damenproblem, bei dem ein vorgegebener Zielzustand erreicht werden soll. Als Heuristik kann dabei die Anzahl der falsch platzierten Steine verwendet werden.
Beispiel Bearbeiten
Im Beispiel soll der kürzeste Weg von Saarbrücken nach Würzburg gefunden werden. Das Diagramm zeigt eine kleine Auswahl an Städten und Wegen. Die Kantenbeschriftung entspricht den Kosten (hier: Entfernung in Kilometern), um von einer Stadt zur nächsten zu kommen. Jeder Knoten enthält die geschätzte Entfernung zum Zielknoten (Wert der -Funktion). Als Heuristik wird hier die Luftlinie verwendet. Auf den Schritt-für-Schritt Bildern zeigt die Farbe eines Knotens seinen Status an:
Sobald ein Knoten erreicht wurde, zeigt eine Kante auf den Vorgängerknoten. Für alle Knoten auf der Open List ist der -Wert angegeben. |
Schritt 1: Es werden alle Nachfolgeknoten vom Startknoten Saarbrücken betrachtet:
Saarbrücken wird in beiden Knoten als Vorgängerknoten eingetragen. Der Knoten Saarbrücken ist nun abschließend betrachtet und wird auf die Closed List gesetzt. (Intuitiv: Es ist sinnlos, erst eine Weile umherzufahren, dabei wieder am Start anzukommen, dann irgendwann anzukommen und zu behaupten, das wäre der optimale Weg.) |
Schritt 2: Die Open List enthält nun zwei Punkte. Da Kaiserslautern den geringeren -Wert hat, wird nun Kaiserslautern als Nächstes untersucht und seine Nachfolgeknoten betrachtet. (Der Weg über Kaiserslautern ist mindestens 228 km lang, der über Karlsruhe mindestens 285 km. Daher ist es am geschicktesten, zuerst Kaiserslautern genauer zu überprüfen.)
Kaiserslautern wird auf die Closed List gesetzt. |
Schritt 3: Der Knoten mit dem geringsten -Wert ist Ludwigshafen. (Die tatsächlichen Kosten von Ludwigshafen nach Würzburg (183 km) weichen deutlich von der Schätzung (108 km) ab, da in diesem Beispiel nur Autobahnen verwendet werden sollen.)
Ludwigshafen wird auf die Closed List gesetzt. Hier wird ein wichtiger Unterschied zwischen „Knoten befindet sich auf der Open List“ und „Knoten befindet sich auf der Closed List“ deutlich: Solange ein Knoten nicht abschließend betrachtet wurde, ist der Pfad zu diesem Knoten nur vorläufig. Eventuell gibt es noch einen besseren Pfad! Knoten auf der Closed List hingegen sind abschließend betrachtet. Der kürzeste Pfad dorthin ist bekannt. |
Schritt 4: Frankfurt wird erkundet. Als einziger Nachfolgeknoten, der sich noch nicht auf der Closed List befindet, wird Würzburg gefunden. Als -Wert wird 289 berechnet, was geringer als der bisherige -Wert für Würzburg ist. Dies bedeutet, dass der Weg über Frankfurt kürzer ist als der zuerst gefundene Weg über Ludwigshafen. Daher wird der -Wert von Würzburg geändert. Außerdem wird als Vorgängerknoten nun Frankfurt gespeichert. Frankfurt wird auf die Closed List gesetzt. |
Schritt 5: Da Karlsruhe nun den kleinsten -Wert hat, wird dieser Knoten als Nächstes untersucht. Heilbronn wird in die Open List eingefügt und Karlsruhe auf die Closed List gesetzt. |
Schritt 6: Jetzt hat Würzburg den geringsten -Wert und wird untersucht: Das Ziel ist gefunden und der kürzeste Weg ist: Saarbrücken–Kaiserslautern–Frankfurt–Würzburg. Dieses Beispiel dient lediglich dem Verständnis der Funktionsweise des Algorithmus. Die Besonderheit des zielgerichteten Suchens wird hier nicht deutlich, da alle Knoten im Bereich der direkten Verbindungslinie Saarbrücken–Würzburg liegen. Unter Weblinks finden sich Java-Applets, die das zielgerichtete Suchen besser darstellen. |
Heuristiken Bearbeiten
Es gibt zwei Arten von Heuristiken für den A*-Algorithmus: Zulässige und monotone Heuristiken. Jede monotone Heuristik ist auch zulässig. Monotonie ist also eine stärkere Eigenschaft als die der Zulässigkeit. Im Allgemeinen werden monotone Heuristiken verwendet. Die Heuristik zur Abschätzung der Entfernung zweier Städte – die Luftlinie – ist zum Beispiel monoton.
Zulässige Heuristik Bearbeiten
Eine Heuristik ist zulässig, wenn die Kosten nie überschätzt werden. Das heißt, die geschätzten Kosten müssen stets im Intervall liegen, wenn 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 und in die Open List eingetragen.
- Im zweiten Schritt wird der Knoten U expandiert, da sein -Wert am niedrigsten ist. Der Nachfolgeknoten K2 wird gefunden und mit dem Wert in die Open List eingetragen.
- Im dritten Schritt besteht die Open List aus den Knoten K2 mit und dem Knoten K1 mit . Also wird der Knoten K2 expandiert. Die beiden Nachfolgeknoten K1 und Ziel werden gefunden. Der neue Wert ist größer als der alte Wert. Daher wird der -Wert für den Knoten K1 in der Open List nicht aktualisiert. Der Zielknoten wird mit in die Open List eingefügt.
- Im vierten Schritt befinden sich die Knoten K1 mit und Ziel mit 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 und in die Open List eingetragen.
- Im zweiten Schritt wird der Knoten U mit expandiert. Die Nachfolgeknoten K2 und Start werden gefunden und mit den Werten und in die Open List eingetragen.
- Im dritten Schritt wird der Knoten K2 expandiert. Die Nachfolgeknoten K1 (), U () und Ziel () werden gefunden.
- Im vierten Schritt werden die Nachfolgeknoten von K1 () in die Open List eingefügt: Start mit und K2 mit .
- Im fünften Schritt wird K2 zum zweiten Mal expandiert, jetzt mit . Die Knoten K1 (), U () und Ziel () werden gefunden.
- Im sechsten Schritt befinden sich 8 Knoten auf der Open List (, , , , , , , ). Die beiden Knoten U und Ziel haben jeweils mit 40 den niedrigsten -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.
Monotone Heuristik Bearbeiten
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 und jeden Nachfolgeknoten von muss gelten . Hierbei bezeichnet die tatsächlichen Kosten, um von nach zu kommen.
Die zweite Bedingung ist eine Form der Dreiecksungleichung: Die geschätzten Kosten von einem Knoten dürfen nicht größer sein als die tatsächlichen Kosten zu einem Nachfolgeknoten 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 .
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.
Eigenschaften Bearbeiten
Der A*-Algorithmus ist
- vollständig: Falls eine Lösung existiert, wird sie gefunden.
- optimal: Es wird immer die optimale Lösung gefunden. Existieren mehrere optimale Lösungen, wird eine davon gefunden (abhängig von Implementierungsdetails).
- optimal effizient: Es gibt keinen anderen Algorithmus, der die Lösung unter Verwendung der gleichen Heuristik schneller findet. (genauer: A* expandiert eine minimale Anzahl an Knoten.)
Optimalität Bearbeiten
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 eine optimale Lösung mit Kosten und eine suboptimale Lösung. Da die Heuristik die Kosten bis zum Ziel nie überschätzt, gilt für jeden Zielknoten und insbesondere für :
Da eine suboptimale Lösung ist, gilt für die Kosten :
Die Heuristik schätzt die tatsächlichen Kosten oder unterschätzt sie. Also gilt für einen beliebigen Knoten auf dem kürzesten Pfad zur optimalen Lösung :
Damit gilt:
Dies bedeutet, dass der A*-Algorithmus die suboptimale Lösung nicht wählt, solange sich Knoten eines optimalen Pfades in der Open List befinden (da bei jedem Schritt der Knoten mit minimalem -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.
Zeitkomplexität Bearbeiten
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 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:
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 -mal aufgerufen. openlist.removeMin enthält maximal 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:
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 -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 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.
Die Gesamtlaufzeit ergibt sich als:
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:
Nachteile Bearbeiten
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 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.
Verwandte Algorithmen Bearbeiten
Der A*-Algorithmus ist verwandt mit dem Dijkstra-Algorithmus und ein Greedy-Algorithmus. Der Algorithmus von Dijkstra verwendet keine Heuristik (, also ) und wählt Knoten nur anhand der bisherigen Kosten aus. Ist die Heuristik des A*-Algorithmus monoton, so kann man sie in die Kostenfunktion einberechnen (also , ) und äquivalent den Algorithmus von Dijkstra verwenden. Ein Greedy-Algorithmus hingegen beachtet die Kosten nicht (, also ) und wählt Knoten nur anhand der geschätzten Restkosten aus. Für das Beispiel der Wegsuche ist der Dijkstra-Algorithmus besser geeignet, falls das Ziel nicht bereits vor der Wegsuche bekannt ist (z. B. nächste Tankstelle), und daher die Verwendung einer Heuristik nicht möglich ist.
Viele zu A* ähnliche Algorithmen versuchen das Speicherproblem zu lösen. Unter anderem sind dies:
- IDA* (Iterative Deepening A*), eine Variante der iterativen Tiefensuche
- RBFS (Recursive Best-First Search), beschränkt den Speicherplatzverbrauch linear zur Länge der Lösung
- MA* (Memory-Bounded A*), SMA* (Simplified MA*), benutzen jeweils eine fest vorgegebene Menge an Speicherplatz
Diese Algorithmen beschränken den Speicherplatzverbrauch auf Kosten der Laufzeit. Dadurch können unter Umständen nicht mehr alle benötigten Knoten im Speicher gehalten werden. Schlechte Knoten werden dann vergessen und müssen später eventuell neu generiert werden. Bei Verwendung einer monotonen Heuristik, und unter der Voraussetzung, dass genügend Speicher zur Verfügung steht, sind alle diese Algorithmen optimal. Ist die Speicherplatzbeschränkung zu restriktiv, kann die optimale Lösung unerreichbar sein. In diesem Fall wird eine suboptimale Lösung oder überhaupt keine Lösung gefunden.
Eine Erweiterung von A* ist der D*-Algorithmus (dynamischer A*). Dieser Algorithmus ist in der Lage, neue Informationen über die Umgebung effizient zu verarbeiten. Ist zum Beispiel eine Brücke entgegen der anfänglichen Annahme unpassierbar, so wird der Weg nur teilweise neu geplant, anstatt A* erneut auf den leicht geänderten Graphen anzuwenden. Besonders in dynamischen oder unbekannten Umgebungen (Roboter bewegt sich durch ein Katastrophengebiet) kann eine wiederholte Neuplanung des bereits gefundenen Weges erforderlich sein. D* ist wie A* optimal und optimal effizient.
Andere graphbasierte Algorithmen sind der Bellman-Ford-Algorithmus (erlaubt negative Kantengewichte) oder der Algorithmus von Floyd und Warshall (berechnet die kürzesten Pfade zwischen allen Knotenpaaren).
Literatur Bearbeiten
- 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), 1968, S. 100–107.
- P. E. Hart, N. J. Nilsson, B. Raphael: Correction to „A Formal Basis for the Heuristic Determination of Minimum Cost Paths“. SIGART Newsletter, 37, 1972, S. 28–29.
- Stuart Russell, Peter Norvig: Künstliche Intelligenz – Ein moderner Ansatz. 2004, Prentice Hall, ISBN 3-8273-7089-2.