A*-Suche
Dijkstra mit Orientierungssinn. Zu den Kosten jedes Orts addiert er eine Schätzung der restlichen Kosten und probiert deshalb zuerst die Orte, die dem Ziel am nächsten scheinen.
- Zeit O((V + E) log V)
- Speicher O(V)
- nutzt eine Prioritätswarteschlange
Was bedeutet das?
- Kosten: was ein Schritt kostet. Im Labyrinth kostet Boden 1, Schlamm 3 und Wasser 9; im Graphen die Zahl an der Kante.
- Prioritätswarteschlange: eine Warteschlange, in der der Günstigste zuerst drankommt, nicht der Erste.
- Schätzung (h): eine Vermutung der restlichen Kosten. A* bleibt nur exakt, wenn sie nie zu hoch ist.
- Kante relaxieren: prüfen, ob der Weg über den aktuellen Ort einem Nachbarn günstigere Kosten gibt, und sie dann übernehmen.
- in der Warteschlange
- aktuell
- erledigt
- günstigster Weg
- Boden · 1
- Schlamm · 3
- Wasser · 9
- Wand
Neu: Start bei A1 mit Kosten 0 und Schätzung 26 bis zum Ziel. A1 ist der einzige Eintrag in der Warteschlange.
Leertaste: abspielen oder pausieren. Pfeiltasten links/rechts: Schritt. Pos1 und Ende: springen.
Probieren Sie es aus: Wähle das offene Feld und wechsle zwischen Dijkstra und A*: Beide finden einen gleich teuren Weg, aber A* nimmt viel weniger Felder aus der Warteschlange.
So funktioniert es
A* arbeitet wie Dijkstra, ordnet die Warteschlange aber nach f = bisherige Kosten + h, wobei h die restlichen Kosten schätzt. Im Labyrinth ist h die Zahl der Schritte bis M ohne Wände und Schlamm, im Graphen die Luftlinie geteilt durch 10. Solange h nie zu hoch schätzt, ist der Weg, den A* beim Nehmen des Ziels hat, der günstigste, genau wie bei Dijkstra. Je besser die Schätzung, desto weniger Orte muss er ansehen.
Wann es sich eignet
A* passt, wenn du ein bestimmtes Ziel suchst und abschätzen kannst, wie weit es ist: Wegfindung in Spielen, Roboter, Routenplaner auf Karten. Mit h = 0 ist es genau Dijkstra. Eine Schätzung, die zu hoch liegen kann, macht A* schneller, kann aber den günstigsten Weg kosten.