A*-Suche

Kurz: A* (A-Stern) findet den kürzesten Weg in einem Graphen schneller als Dijkstra, indem es mit einer Schätzung („Heuristik”) bevorzugt in Richtung Ziel sucht.

Genauer: A* bewertet jeden Knoten mit f = g + h. Dabei ist g der bisher bekannte Weg vom Start und h die geschätzte Restentfernung zum Ziel. Der Knoten mit dem kleinsten f wird als Nächstes untersucht.

Im Detail

• Heuristik: Muss das Ziel unterschätzen oder genau treffen (zulässig), damit der kürzeste Weg garantiert ist. Auf Gitterkarten eignet sich die Manhattan-Distanz.
• Datenstruktur: Eine Prioritätswarteschlange (Heap) liefert den besten Knoten schnell.
• Sonderfall: Mit h = 0 wird aus A* der Dijkstra-Algorithmus.
• Einsatz: Wegfindung in Spielen, Navigation, Robotik.
• Speicher: A* merkt sich viele Knoten und kann bei sehr großen Karten viel Speicher brauchen.

Siehe auch: Dijkstra-Algorithmus, Graph (Datenstruktur)