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)
- använder en prioritetskö
Vad betyder det här?
- Kostnad: vad ett drag kostar. I labyrinten kostar mark 1, lera 3 och vatten 9; i grafen talet på kanten.
- Prioritetskö: en kö där den billigaste går först, inte den som kom först.
- 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.
- i kön
- aktuell
- klar
- billigaste väg
- mark · 1
- lera · 3
- vatten · 9
- vägg
Ny: Start i A1 med kostnad 0 och uppskattningen 26 till målet. Den är det enda i kön.
Blanksteg: spela upp eller pausa. Vänster och höger pil: steg. Home och End: hoppa.
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.