Algoritmus A*
Dijkstra so zmyslom pre smer. K cene každého miesta pripočíta odhad zostávajúcej ceny, takže najprv skúša miesta, ktoré vyzerajú najbližšie k cieľu.
- čas O((V + E) log V)
- pamäť O(V)
- používa prioritný rad
Čo to znamená?
- Cena: koľko stojí ťah. V bludisku stojí zem 1, blato 3 a voda 9; v grafe číslo na hrane.
- Prioritný rad: rad, v ktorom ide prvý najlacnejší, nie ten, kto prišiel prvý.
- Odhad (h): predpoveď zostávajúcej ceny. A* zostáva presný, len keď nie je nikdy priveľký.
- Relaxácia hrany: overenie, či cesta cez aktuálne miesto dá susedovi nižšiu cenu, a ak áno, jej prevzatie.
- v rade
- aktuálny
- hotový
- najlacnejšia cesta
- zem · 1
- blato · 3
- voda · 9
- stena
Nový: Štart v A1 s cenou 0 a odhadom 26 do cieľa. Je jediný v rade.
Medzerník: prehrať alebo pozastaviť. Šípky vľavo/vpravo: krok. Home a End: preskočiť.
Skúste: Vyberte otvorené pole a prepínajte medzi Dijkstrom a A*: oba nájdu rovnako drahú cestu, ale A* vezme z radu oveľa menej políčok.
Ako to funguje
A* funguje ako Dijkstra, ale radí rad podľa f = doterajšia cena + h, kde h odhaduje zostávajúcu cenu. V bludisku je h počet ťahov do M bez ohľadu na steny a blato; v grafe vzdialenosť vzdušnou čiarou delená 10. Kým h nikdy nepreceňuje, cesta, ktorú má A* v okamihu vzatia cieľa, je najlacnejšia, rovnako ako pri Dijkstrovi. Čím lepší odhad, tým menej miest musí prejsť.
Kedy sa hodí
A* použite, keď hľadáte jeden cieľ a viete odhadnúť, ako je ďaleko: hľadanie cesty v hrách, roboty, plánovače trás na mape. S h = 0 je to presne Dijkstra. Odhad, ktorý môže preceňovať, A* zrýchli, ale môže vás pripraviť o najlacnejšiu cestu.