Ricerca A*
L'algoritmo di Dijkstra trova la via più breve verso un arrivo, ma cerca in tutte le direzioni insieme, anche lontano dall'arrivo. La ricerca A* aggiunge un'informazione, una stima di quanto manca all'arrivo, e d'un tratto la ricerca punta dritta verso di esso.
L'idea
Quando cerchi un percorso su una mappa, non esplori le strade che si allontanano dalla destinazione con la stessa cura di quelle che vi si avvicinano. La ricerca A* fa lo stesso. Ogni nodo riceve un punteggio: la distanza dalla partenza finora, g, più una stima della distanza rimanente, h. La ricerca prosegue sempre dal nodo con il punteggio più basso, quindi i nodi in direzione dell'arrivo vengono per primi.
Passo per passo
Dai alla partenza distanza 0 e mettila in una coda con punteggio h(partenza). Ripeti: prendi il nodo con il punteggio più basso e rendi definitiva la sua distanza. Se è l'arrivo, fermati: risalendo i nodi ricordati si ottiene il percorso. Altrimenti, per ogni vicino non definitivo, calcola la sua distanza passando da questo nodo. Se è minore della sua distanza finora, abbassala, ricorda questo nodo come via per arrivarci e dai al vicino come punteggio la sua nuova distanza più la sua stima. A parità di punteggio, prendere prima il nodo con la stima minore di solito raggiunge l'arrivo prima.
Un esempio
Prendiamo una partenza A e un arrivo D. A–B è lungo 2 e B–D 2, mentre A–C è lungo 1 e C–D 5. Le stime in linea d'aria fino a D sono 3 da A, 2 da B e 3 da C. A parte con punteggio 0 + 3 = 3. Prendere A dà a B il punteggio 2 + 2 = 4 e a C il punteggio 1 + 3 = 4. In caso di parità A* prende B, il nodo con la stima minore, e B dà a D il punteggio 4 + 0 = 4. Ora D ha il punteggio più basso con la stima minore, quindi viene preso: il percorso più breve è A → B → D, di lunghezza 4, e C, che porta nella direzione sbagliata, non diventa mai definitivo. L'algoritmo di Dijkstra avrebbe reso definitivo prima C, perché è il nodo più vicino ad A.
Una buona stima
La stima non deve mai essere più lunga della distanza reale dall'arrivo; una stima così si dice ammissibile, e con essa A* trova sempre un percorso più breve. La linea d'aria è ammissibile perché nessun percorso è più corto di una linea retta. Se inoltre la stima non scende mai più della lunghezza di un arco da un nodo al successivo, è consistente, e nessun nodo definitivo deve mai essere riesaminato. Più la stima è vicina al vero, meno nodi servono ad A*. Una stima di 0 è ammissibile ma inutile: A* diventa allora l'algoritmo di Dijkstra. Una stima troppo grande rende A* più veloce, ma può mancare il percorso più breve.
Storia e usi
Peter Hart, Nils Nilsson e Bertram Raphael dello Stanford Research Institute pubblicarono A* nel 1968, mentre lavoravano a Shakey, uno dei primi robot mobili. Le loro versioni precedenti si chiamavano A1 e A2; la stella indicava la versione di cui dimostrarono l'ottimalità. Oggi A* muove i personaggi attorno agli ostacoli nei videogiochi, pianifica percorsi e movimenti di robot e risolve rompicapi come il gioco del 15 (15-puzzle), dove la stima somma quanto ogni tessera è lontana dal suo posto.
Provalo
Apri l'app e premi Passo. I numeri sugli archi sono le loro lunghezze, che qui corrispondono a quanto sono lunghi nel disegno, e la linea tratteggiata mostra la stima in linea d'aria fino all'arrivo. La coda sotto il grafo elenca i nodi per punteggio, dal più basso. Quando l'arrivo è definitivo, la riga di stato confronta quanti nodi A* ha reso definitivi con quanti ne sarebbero serviti all'algoritmo di Dijkstra. Prova un arrivo in un angolo lontano di un grafo grande per vedere la differenza maggiore.
Domande frequenti
Che cosa significa la stella in A*?
Hart, Nilsson e Raphael descrissero prima degli algoritmi che chiamarono A1 e A2. A* («A star») era la versione di cui dimostrarono che trova un percorso più breve espandendo il minor numero di nodi tra gli algoritmi comparabili con la stessa stima, quando la stima è consistente.
Qual è la complessità temporale di A*?
Nel caso peggiore, con una stima inutile, A* fa lo stesso lavoro dell'algoritmo di Dijkstra: O((V + E) log V) con un heap binario. Con una buona stima rende definitiva solo una frazione dei nodi, ed è per questo che in pratica è veloce.
Che cosa rende buona un'euristica per A*?
Deve essere rapida da calcolare, non sovrastimare mai la distanza reale ed esserle il più vicina possibile. Su una griglia dove ci si può muovere solo in su, in giù, a sinistra e a destra, la distanza di Manhattan è una scelta comune; su una mappa, la distanza in linea d'aria.
E se l'euristica sovrastima?
Allora A* può restituire un percorso che non è il più breve, perché può finire prima di esaminare la via migliore. Alcuni programmi lo fanno apposta (A* pesato) per scambiare un po' di qualità del percorso con molta velocità.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova la ricerca A*