Căutarea A*
Dijkstra cu simț al orientării. La costul fiecărui loc adaugă o estimare a costului rămas, așa că încearcă întâi locurile care par cel mai aproape de țintă.
- timp O((V + E) log V)
- memorie O(V)
- folosește o coadă de prioritate
Ce înseamnă acești termeni?
- Cost: cât costă o mutare. În labirint, pământul costă 1, noroiul 3 și apa 9; în graf, numărul de pe muchie.
- Coadă de prioritate: o coadă în care trece întâi cel mai ieftin, nu cel venit primul.
- Estimare (h): o presupunere a costului rămas. A* rămâne exact doar dacă nu e niciodată prea mare.
- Relaxarea unei muchii: verificarea dacă trecerea prin locul curent dă unui vecin un cost mai mic și, dacă da, preluarea lui.
- în coadă
- curent
- gata
- cel mai ieftin drum
- pământ · 1
- noroi · 3
- apă · 9
- zid
Nou: Start în A1 cu costul 0 și o estimare de 26 până la țintă. E singurul din coadă.
Space: redă sau pauză. Săgețile stânga și dreapta: pas cu pas. Home și End: salt.
Încearcă: Alege câmpul deschis și comută între Dijkstra și A*: amândouă găsesc un drum cu același cost, dar A* scoate mult mai puține căsuțe din coadă.
Cum funcționează
A* lucrează ca Dijkstra, dar ordonează coada după f = costul de până acum + h, unde h estimează costul rămas. În labirint, h e numărul de mutări până la M ignorând pereții și noroiul; în graf, distanța în linie dreaptă împărțită la 10. Cât timp h nu supraestimează niciodată, drumul pe care îl are A* când ia ținta este cel mai ieftin, exact ca la Dijkstra. Cu cât estimarea e mai bună, cu atât mai puține locuri trebuie verificate.
Când este o alegere bună
Folosește A* când cauți o singură țintă și poți estima cât de departe e: căutarea drumului în jocuri, roboți, planificatoare de rute pe hartă. Cu h = 0 este exact Dijkstra. O estimare care poate supraestima face A* mai rapid, dar te poate costa drumul cel mai ieftin.