Ricerca A*
Dijkstra con il senso dell’orientamento. Al costo di ogni punto aggiunge una stima del costo che resta, così prova prima i punti che sembrano più vicini all’arrivo.
- tempo O((V + E) log V)
- spazio O(V)
- usa una coda di priorità
Cosa significano questi termini?
- Costo: quanto costa una mossa. Nel labirinto il terreno costa 1, il fango 3 e l’acqua 9; nel grafo è il numero sull’arco.
- Coda di priorità: una coda in cui passa prima il più economico, non il primo arrivato.
- Stima (h): un’ipotesi del costo che resta. A* resta esatto solo se non è mai troppo alta.
- Rilassare un arco: controllare se passare dal punto corrente dà a un vicino un costo più basso e, se sì, adottarlo.
- in coda
- attuale
- finito
- percorso più economico
- terreno · 1
- fango · 3
- acqua · 9
- muro
Nuovo: Partenza da A1 con costo 0 e una stima di 26 fino all’arrivo. È l’unico elemento in coda.
Spazio: riproduci o metti in pausa. Frecce sinistra e destra: passo passo. Home e Fine: salta.
Prova così: Scegli il campo aperto e passa da Dijkstra ad A*: entrambi trovano un percorso dello stesso costo, ma A* toglie dalla coda molte meno caselle.
Come funziona
A* funziona come Dijkstra, ma ordina la coda per f = costo accumulato + h, dove h stima il costo che resta. Nel labirinto h è il numero di mosse fino a M ignorando muri e fango; nel grafo è la distanza in linea d’aria divisa per 10. Finché h non sovrastima mai, il percorso che A* ha quando prende l’arrivo è il più economico, proprio come con Dijkstra. Migliore la stima, meno punti deve esaminare.
Quando conviene usarlo
Usa A* quando cerchi un solo arrivo e sai stimare quanto è lontano: pathfinding nei videogiochi, robot, calcolo di itinerari su una mappa. Con h = 0 è esattamente Dijkstra. Una stima che può sovrastimare rende A* più veloce, ma può farti perdere il percorso più economico.