A*-Suche
Der Dijkstra-Algorithmus findet den kürzesten Weg zu einem Ziel, sucht aber in alle Richtungen zugleich, auch vom Ziel weg. Die A*-Suche fügt ein Stück Wissen hinzu, eine Schätzung, wie weit das Ziel noch entfernt ist, und plötzlich steuert die Suche direkt darauf zu.
Die Idee
Wenn Sie auf einer Karte eine Route suchen, erkunden Sie Straßen, die von Ihrem Ziel wegführen, nicht so gründlich wie Straßen, die darauf zuführen. Die A*-Suche macht es genauso. Jeder Knoten bekommt eine Bewertung: den bisherigen Abstand vom Start, g, plus eine Schätzung des noch verbleibenden Abstands, h. Die Suche macht immer beim Knoten mit der niedrigsten Bewertung weiter, also kommen Knoten in Richtung Ziel zuerst.
Schritt für Schritt
Der Start bekommt Abstand 0 und kommt mit der Bewertung h(Start) in eine Warteschlange. Wiederholen Sie: Nehmen Sie den Knoten mit der niedrigsten Bewertung und markieren Sie seinen Abstand als endgültig. Ist es das Ziel, hören Sie auf: Folgt man den gemerkten Knoten zurück, ergibt sich der Weg. Sonst berechnen Sie für jeden Nachbarn, der nicht endgültig ist, seinen Abstand über diesen Knoten. Ist er kürzer als sein bisheriger Abstand, senken Sie ihn, merken Sie sich diesen Knoten als Weg dorthin und geben Sie dem Nachbarn als Bewertung seinen neuen Abstand plus seine Schätzung. Sind zwei Bewertungen gleich, erreicht man das Ziel meist schneller, wenn man zuerst den Knoten mit der kleineren Schätzung nimmt.
Ein Beispiel
Nehmen wir einen Start A und ein Ziel D. A–B ist 2 lang und B–D 2, während A–C 1 lang ist und C–D 5. Die Luftlinien-Schätzungen bis D sind 3 von A, 2 von B und 3 von C. A beginnt mit der Bewertung 0 + 3 = 3. Wird A genommen, bekommt B die Bewertung 2 + 2 = 4 und C die Bewertung 1 + 3 = 4. Bei Gleichstand nimmt A* B, den Knoten mit der kleineren Schätzung, und B gibt D die Bewertung 4 + 0 = 4. D hat jetzt die niedrigste Bewertung mit der kleinsten Schätzung und wird genommen: Der kürzeste Weg ist A → B → D mit Länge 4, und C, das in die falsche Richtung führt, wird nie endgültig. Der Dijkstra-Algorithmus hätte C zuerst endgültig gemacht, weil es der nächstgelegene Knoten zu A ist.
Eine gute Schätzung
Die Schätzung darf nie länger sein als der echte Abstand zum Ziel; eine solche Schätzung heißt zulässig, und mit ihr findet A* immer einen kürzesten Weg. Die Luftlinie ist zulässig, weil keine Route kürzer ist als eine gerade Linie. Sinkt die Schätzung außerdem von einem Knoten zum nächsten nie um mehr als die Länge der Kante, ist sie konsistent, und kein endgültiger Knoten muss je erneut betrachtet werden. Je näher die Schätzung an der Wahrheit liegt, desto weniger Knoten braucht A*. Eine Schätzung von 0 ist zulässig, aber nutzlos: A* wird dann zum Dijkstra-Algorithmus. Eine zu große Schätzung macht A* schneller, kann aber den kürzesten Weg verfehlen.
Geschichte und Einsatz
Peter Hart, Nils Nilsson und Bertram Raphael vom Stanford Research Institute veröffentlichten A* 1968, während sie an Shakey arbeiteten, einem der ersten mobilen Roboter. Ihre früheren Versionen hießen A1 und A2; der Stern kennzeichnete die Version, deren Optimalität sie bewiesen. Heute bewegt A* Figuren in Videospielen um Hindernisse herum, plant Routen und Roboterbewegungen und löst Puzzles wie das 15-Puzzle, bei dem die Schätzung zusammenzählt, wie weit jeder Stein von seinem Platz entfernt ist.
Selbst ausprobieren
Öffnen Sie die App und drücken Sie Schritt. Die Zahlen auf den Kanten sind ihre Längen, die hier dazu passen, wie lang sie gezeichnet sind, und die gestrichelte Linie zeigt die Luftlinien-Schätzung zum Ziel. Die Warteschlange unter dem Graphen listet die Knoten nach Bewertung, die niedrigste zuerst. Ist das Ziel endgültig, vergleicht die Statuszeile, wie viele Knoten A* endgültig gemacht hat und wie viele der Dijkstra-Algorithmus gebraucht hätte. Wählen Sie ein Ziel in einer fernen Ecke eines großen Graphen, um den größten Unterschied zu sehen.
Häufig gestellte Fragen
Was bedeutet der Stern in A*?
Hart, Nilsson und Raphael beschrieben zuerst Algorithmen, die sie A1 und A2 nannten. A* („A-Stern“) war die Version, von der sie bewiesen, dass sie bei konsistenter Schätzung einen kürzesten Weg findet und dabei unter vergleichbaren Algorithmen mit derselben Schätzung die wenigsten Knoten expandiert.
Welche Zeitkomplexität hat A*?
Im schlimmsten Fall, mit einer nutzlosen Schätzung, leistet A* dieselbe Arbeit wie der Dijkstra-Algorithmus: O((V + E) log V) mit einem binären Heap. Mit einer guten Schätzung macht A* nur einen Bruchteil der Knoten endgültig, darum ist es in der Praxis schnell.
Was macht eine gute Heuristik für A* aus?
Sie sollte schnell zu berechnen sein, den echten Abstand nie überschätzen und ihm so nahe wie möglich kommen. Auf einem Gitter, auf dem man sich nur nach oben, unten, links und rechts bewegen kann, ist die Manhattan-Distanz eine übliche Wahl; auf einer Karte die Luftlinie.
Was passiert, wenn die Heuristik überschätzt?
Dann gibt A* womöglich einen Weg zurück, der nicht der kürzeste ist, weil die Suche enden kann, bevor sie den besseren Weg betrachtet. Manche Programme tun das absichtlich (gewichtetes A*), um ein wenig Wegqualität gegen viel Tempo einzutauschen.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
A*-Suche ausprobieren