Ein Best-First-Graph-Suchalgorithmus, der die Knotenausweitung nach einer Kostenfunktion f(n)=g(n)+h(n) ordnet, wobei g(n) die Kosten vom Start bis Knoten n und h(n) eine heuristische Schätzung der Kosten von n zum Ziel ist; mit einer zulässigen (und vorzugsweise konsistenten) Heuristik findet A* effizient kürzeste Pfade.

Prinzip

Priorisiere Knoten mit niedrigsten geschätzten Gesamtkosten (g + h); die Zulässigkeit von h (sie überschätzt die tatsächlichen Kosten nie) stellt sicher, dass beim ersten Herausnehmen eines Zielknotens aus der Frontier dessen Pfad optimal ist, und Konsistenz (Monotonie) vereinfacht die Buchführung und garantiert nicht abnehmende f-Werte entlang von Pfaden.

Demonstration

Pfadsuche auf einem Raster: Verwende g(n) als bisherige Pfadlänge und h(n) als Manhattan-Distanz zum Ziel. A* erweitert Knoten, die nach f vielversprechend erscheinen; ist h die Manhattan-Distanz bei 4-verbundener orthogonaler Bewegung, findet A* den kürzesten Rasterweg, ohne alle Zellen zu erkunden. In der Robotik plant A* diskrete Routen auf Belegungsrastern.

Fehlanwendung

Verwendung einer unzulässigen Heuristik (die überschätzt) kann zu suboptimalen Pfaden führen; schwache Heuristiken (nahe null) degradieren A* zu Dijkstras Algorithmus, was zu übermäßigen Erweiterungen und hohem Speicherverbrauch führt; das Ignorieren von Speichergrenzen kann A* auf großen Graphen unpraktikabel machen.

Konsequenz

Wenn eine gute zulässige Heuristik verfügbar ist, reduziert A* die Knotenausweitungen im Vergleich zur uninformierten Suche erheblich und liefert optimale Pfade; es bietet auch ein flexibles Rahmenwerk für Varianten (gewichtetes A*, IDA*), die Optimalität gegen Geschwindigkeit oder Speicher tauschen.

Umkehrung

Dijkstras Algorithmus entspricht A* mit h=0 (uninformiert) und ist optimal, kann aber mehr erkunden; Greedy-Best-First-Suche verwendet f=h und kann schneller sein, ist jedoch nicht garantiert optimal.

Abgrenzung

Entwickelt für diskrete Zustandsraum-Suche und Kürzeste-Wege-Probleme mit nicht-negativen Kantengewichten und wohldefinierten Zieltests; kontinuierliche Probleme erfordern Diskretisierung oder spezialisierte kontinuierliche Varianten; Optimalität hängt von Eigenschaften der Heuristik und Kostenannahmen ab.

Semantische Spannung

Spannung zwischen Zulässigkeit/Optimalität und praktischer Geschwindigkeit: Zulässige Heuristiken garantieren Optimalität, können aber konservativ sein; gewichtete oder unzulässige Heuristiken beschleunigen die Suche, riskieren jedoch suboptimale Lösungen. Es besteht auch Spannung zwischen Speicherverbrauch (Größe der Frontier) und Expansionsrate.

Synthese

A* vereint die tatsächlichen Kosten vom Start und die heuristischen Restkosten in einer Ordnung, die bei zulässiger Heuristik optimale und oft effiziente Suche ergibt; der praktische Einsatz erfordert einen Ausgleich zwischen Heuristikdesign, Speicherbeschränkungen und akzeptablen Kompromissen zwischen Geschwindigkeit und Optimalität.