A*-sökning
Dijkstra med lokalsinne. Till varje plats kostnad lägger den en uppskattning av kostnaden som återstår, så den provar först platserna som ser närmast målet ut.
- tid O((V + E) log V)
- minne O(V)
- prioritetskö
Prioritetskö: en kö där den billigaste går först, inte den som kom först.
Fler begrepp på sidan
- Kostnad: vad ett drag kostar. I labyrinten kostar mark 1, lera 3 och vatten 9; i grafen talet på kanten.
- Uppskattning (h): en gissning av kostnaden som återstår. A* förblir exakt bara om den aldrig är för hög.
- Att relaxera en kant: kontrollera om vägen via den aktuella platsen ger en granne lägre kostnad, och i så fall ta den.
Prova det här: Välj det öppna fältet och växla mellan Dijkstra och A*: båda hittar en väg som kostar lika mycket, men A* tar betydligt färre rutor ur kön.
Så fungerar det
A* fungerar som Dijkstra men ordnar kön efter f = kostnad hittills + h, där h uppskattar kostnaden som återstår. I labyrinten är h antalet drag till M utan väggar och lera; i grafen avståndet fågelvägen delat med 10. Så länge h aldrig gissar för högt är vägen som A* har när den tar målet den billigaste, precis som hos Dijkstra. Ju bättre uppskattning, desto färre platser behöver den titta på.
När det är ett bra val
Använd A* när du letar efter ett enda mål och kan uppskatta hur långt bort det är: vägsökning i spel, robotar, ruttplanerare på en karta. Med h = 0 är det precis Dijkstra. En uppskattning som kan gissa för högt gör A* snabbare men kan kosta dig den billigaste vägen.