Algoritmus A*
Dijkstra se smyslem pro směr. K ceně každého místa přičte odhad zbývající ceny, takže nejdřív zkouší místa, která vypadají nejblíž cíli.
- čas O((V + E) log V)
- paměť O(V)
- používá prioritní frontu
Co to znamená?
- Cena: kolik stojí tah. V bludišti stojí zem 1, bahno 3 a voda 9; v grafu číslo na hraně.
- Prioritní fronta: fronta, ve které jde první nejlevnější, ne ten, kdo přišel první.
- Odhad (h): předpověď zbývající ceny. A* zůstává přesný, jen když není nikdy moc vysoký.
- Relaxace hrany: ověření, zda cesta přes aktuální místo dá sousedovi nižší cenu, a pokud ano, její převzetí.
- ve frontě
- aktuální
- hotový
- nejlevnější cesta
- zem · 1
- bahno · 3
- voda · 9
- zeď
Nový: Start v A1 s cenou 0 a odhadem 26 do cíle. Je jediný ve frontě.
Mezerník: přehrát nebo pozastavit. Šipky vlevo/vpravo: krok. Home a End: přeskočit.
Zkuste: Vyberte otevřené pole a přepínejte mezi Dijkstrou a A*: oba najdou stejně drahou cestu, ale A* vezme z fronty mnohem méně políček.
Jak to funguje
A* funguje jako Dijkstra, ale řadí frontu podle f = dosavadní cena + h, kde h odhaduje zbývající cenu. V bludišti je h počet tahů do M bez ohledu na zdi a bahno; v grafu vzdálenost vzdušnou čarou dělená 10. Dokud h nikdy nepřecení, cesta, kterou má A* v okamžiku vzetí cíle, je nejlevnější, stejně jako u Dijkstry. Čím lepší odhad, tím méně míst musí projít.
Kdy se hodí
A* použijte, když hledáte jeden cíl a umíte odhadnout, jak je daleko: hledání cesty ve hrách, roboti, plánovače tras na mapě. S h = 0 je to přesně Dijkstra. Odhad, který může přecenit, A* zrychlí, ale může vás připravit o nejlevnější cestu.