L'algoritmo di Dijkstra esplora il grafo in tutte le direzioni allo stesso modo. Se cerco il percorso da Bologna a Firenze, Dijkstra considera con la stessa attenzione le strade verso Venezia e verso Milano, finché la sua «onda» di distanze non arriva a Firenze. È corretto, ma spreca lavoro: io so che Firenze è a sud, e vorrei che l'algoritmo lo sapesse.
A (si legge «A star») fa esattamente questo. Aggiunge a Dijkstra una stima* di quanto manca all'obiettivo e usa questa stima per dare priorità ai vertici che sembrano andare nella direzione giusta. Presentato nel 1968 da Hart, Nilsson e Raphael, è ancora oggi l'algoritmo standard per il pathfinding in videogiochi, robotica e pianificazione di percorsi.
La formula f = g + h
Per ogni vertice n, A* considera:
- g(n): il costo del miglior cammino trovato finora dalla partenza a n (lo stesso valore di Dijkstra);
- h(n): la stima euristica del costo da n all'obiettivo;
- f(n) = g(n) + h(n): la stima del costo totale di un percorso che passa da n.
La coda di priorità è ordinata per f invece che per g. Se h vale sempre 0, A* coincide esattamente con Dijkstra. Più h è informativa, più la ricerca punta dritta verso l'obiettivo.
import heapq
def a_star(adj, start, goal, h):
g = {start: 0}
padre = {start: None}
heap = [(h(start), start)]
while heap:
f, u = heapq.heappop(heap)
if u == goal:
break
if f > g[u] + h(u):
continue
for v, w in adj[u]:
ng = g[u] + w
if v not in g or ng < g[v]:
g[v] = ng
padre[v] = u
heapq.heappush(heap, (ng + h(v), v))
return g.get(goal), padre
Ammissibilità: la condizione per l'ottimo
Un'euristica è ammissibile se non sovrastima mai il costo reale residuo: h(n) ≤ costo vero da n all'obiettivo. Con un'euristica ammissibile A* restituisce sempre un percorso ottimo.
L'idea della dimostrazione: finché sulla coda c'è un vertice lungo il percorso ottimo, il suo valore f è al massimo il costo ottimo, perché h non esagera. Quindi un percorso subottimo, che ha f maggiore, non può essere estratto prima.
Una condizione più forte è la consistenza (o monotonia): per ogni arco (u, v) di peso w vale h(u) ≤ w + h(v). In parole: la stima non cala mai più del costo dell'arco percorso. Con un'euristica consistente ogni vertice, una volta estratto, ha già il costo definitivo, come in Dijkstra. Quasi tutte le euristiche geometriche usate in pratica sono consistenti.
Euristiche classiche sulle griglie
Nei giochi e nella robotica il grafo è spesso una griglia di celle. La scelta dell'euristica dipende dai movimenti consentiti:
| Movimenti consentiti | Euristica | Formula (dx, dy = differenze di coordinate) |
|---|---|---|
| Solo 4 direzioni | Manhattan | dx + dy |
| 8 direzioni, diagonale costo 1 | Chebyshev | max(dx, dy) |
| 8 direzioni, diagonale costo √2 | Octile | max(dx, dy) + (√2 − 1) · min(dx, dy) |
| Movimento libero | Euclidea | √(dx² + dy²) |
Usare un'euristica pensata per un altro tipo di movimento è un errore frequente. La distanza di Manhattan su una griglia con diagonali sovrastima il costo, perde l'ammissibilità e può produrre percorsi non ottimi.
Sulle reti stradali si usa spesso la distanza in linea d'aria divisa per la velocità massima della rete: è una stima del tempo che non può mai essere superiore al tempo reale.
Il compromesso tra velocità e qualità
A volte un percorso quasi ottimo trovato in fretta vale più di quello perfetto trovato tardi. A* pesato usa f = g + ε · h con ε > 1. La ricerca diventa più «avida», esplora meno vertici, e il costo del percorso trovato è garantito non superiore a ε volte l'ottimo. Con ε = 1,2, per esempio, si accetta al massimo un 20% in più in cambio di una ricerca molto più rapida.
All'estremo opposto, un'euristica troppo debole (vicina a zero) mantiene l'ottimalità ma riporta A* verso il comportamento di Dijkstra.
Problemi pratici frequenti
- Memoria: A conserva tutti i vertici scoperti. Su spazi enormi, come i giochi di puzzle con miliardi di stati, si usano varianti come IDA, che ripete ricerche in profondità con soglie crescenti su f.
- Parità di f: in campi aperti molti vertici hanno lo stesso f e A* li esplora tutti. Spareggiare a favore del g più alto (i vertici più avanzati) riduce molto il lavoro.
- Obiettivo irraggiungibile: se non esiste un percorso, A* esplora l'intera componente prima di arrendersi. Conviene verificare prima la connettività, magari con componenti precalcolate.
Oltre le mappe
A* funziona su qualunque problema esprimibile come ricerca in uno spazio di stati: risolvere il gioco del 15 (con euristica la somma delle distanze di Manhattan delle tessere dalla posizione finale), pianificare sequenze di azioni, allineare sequenze. Basta definire gli stati, le mosse con il loro costo e una stima ammissibile della distanza residua.
In sintesi
- A* ordina la ricerca per f = g + h, dove h stima il costo residuo all'obiettivo.
- Con un'euristica ammissibile, che non sovrastima mai, il percorso trovato è ottimo.
- L'euristica deve corrispondere ai movimenti consentiti: Manhattan, Chebyshev, octile, euclidea.
- A* pesato scambia una perdita di qualità garantita con una ricerca più rapida.
- Lo stesso schema si applica a qualunque ricerca in uno spazio di stati.
