A*

Nell'informatica, A* è un algoritmo di ricerca su grafi che individua un percorso da un dato nodo iniziale verso un dato nodo goal (o che passi un test di goal dato). Utilizza una "stima euristica" che classifica ogni nodo attraverso una stima della strada migliore che passa attraverso tale nodo. Visita il nodo in base a tale stima euristica. L'algoritmo A* è anche un esempio di ricerca best-first.

L'algoritmo è stato descritto nel 1968 da Peter Hart, Nils Nilsson, e Bertram Raphael.

Intuizione

Consideriamo un esempio motivante. Ci troviamo ad un incrocio A, e vorremmo andare ad uno B che fortunatamente sappiamo che si trova a nord di dove siamo. In questo caso gli incroci sono i vertici di un grafo e le strade sono lati.

Se si effettua una ricerca breadth-first come illustrato dall'algoritmo di Dijkstra, cercheremo ogni punto con un raggio circolare fisso, gradualmente espanderemo questo cerchio per cercare gli incroci più lontani dal nostro punto iniziale. Questa può essere una strategia effettiva se non si conosce dove si trovi la destinazione, come fa la polizia nella ricerca di un criminale nascosto.

Comunque, essa porta ad uno spreco di tempo se si hanno più informazioni. Una strategia migliore consiste nell'esporazione degli incroci posizionati a nord del primo, perché essi saranno i vertici più prossimi a B. Allora, le strade ci autorizzano, ad esplorare gli incroci sempre più vicini all'incrocio goal B. Ci sarà bisognio di qualche backtrack occasionale, ma senza dubbio questa è una strategia migliore. Inoltre, può essere provato che questa strategia troverà la strada migliore possibile, come farebbe la ricerca breadth-first. Questa è l'essenza della ricerca A*.

Comunque, non è garantito che l'esecuzione dell'A* sia migliore rispetto ai semplici algoritmi di ricerca. In un ambiente molto contorto, il solo modo per raggiungere la notra destinazione potrebbe essere quello di dirigerci a sud e in seguito girarci attorno. In questi casi la prova dei nodi più prossimi alla nostra destinazione potrebbe essere uno spreco di tempo.

Veduta d'insieme

Un algoritmo di ricerca che garantisce sempre di trovare il percorso più corto verso una meta è detto ammissibile. Se A* utilizza una euristica allora non bisogna mai sovrastimare la distanza (o in genere, il costo) verso la meta, si può così verificare che A* sarà ammissibile. Una euristica che fa di una ricerca A* ammissibile è detta "euristica ammissibile".

Se la stima semplicemente ritorna sempre zero, che non sarà mai una sovrastima, allora A* compierà effettivamente l'algoritmo di Dijkstra e troverà ancora una soluzione ottimale, benché non rapidamente. L'euristica migliore possibile, benché non sia di solito pratico calcolarla, è la distanza attuale minima verso meta. Un esempio di euristica pratica ammissibile è la distanza in linea d'aria dalla meta su una mappa.

Può essere verificato che A* non considera più nodi di qualunque altro algoritmo di ricerca ammissibile, a meno che l'algoritmo alternativo non abbia una stima euristica più accurata. In questo senso A* è l'algoritmo computazionalmente più efficiente che garantisce la ricerca del percorso più breve.

Descrizione

A* comincia a partire dal nodo selezionato. Per ogni nodo è definito un costo di entrata (di solito zero per il nodo iniziale). A* allora valuta la distanza dal nodo meta a partire da quello corrente. Questa stima ed il costo assieme formano l'euristica che sarà assegnata al percorso passante per questo nodo. Il nodo è aggiunto allora a una coda di priorità, spesso chiamata "open".

L'algoritmo allora rimuove il prossimo nodo dalla coda di priorità (perché avrà valore della funzione euristica più basso). Se la coda è vuota, non ci saranno percorsi dal nodo iniziale al nodo meta e l'algoritmo si arresterà. Se il nodo è il nodo meta, A* ricostruisce e pone in output il percorso ottenuto e si arresta. Questa ricostruzione del percorso a partire dai nodi più vicini significa che non è necessario memorizzare il percorso in ogni nodo.

Se il nodo non è il nodo meta, nuovi nodi saranno creati per tutti nodi vicini ammissibili; il modo di fare questo dipende dal problema. Per ciascuno nodo successivo A* calcola il "costo" di entrata nel nodo e lo salva col nodo. Questo costo è calcolato dalla somma cumulativa dei pesi immagazzinati negli antenati, più il costo dell'operazione per raggiungere questo nuovo nodo.

L'algoritmo gestisce anche una lista di "closed", un elenco di nodi che sono già stati controllati. Se un nuovo nodo generato è già nella lista con un costo uguale o più basso, non ci sarà alcuna futura indagine su tale nodo o col percorso ad esso associato. Se un nodo nella lista di closed è uguale ad uno nuovo, ma è stato immagazzinato con un costo più alto, allora sarà rimosso dalla lista di closed, e il processo continuerà a partire dal nuovo nodo.

Successivamente, una stima della distanza dal nodo nuovo alla meta è aggiunta al costo per formare il suo valore euristico. Tale nodo è aggiunto allora alla coda di priorità "open", a meno che non esista un nodo identico con valore euristico minore o uguale.

L'algoritmo sarà adottato ad ogni nodo vicino, fatto ciò il nodo originale è preso dalla coda di priorità e posto nella lista di "closed". Il prossimo nodo sarà ottenuto dalla lista di open e con esso si ripeterà il processo descitto.

Perché A* è ammissibile e computazionalmente ottima

C'è una spiegazione intuitiva del perché A* è sia ammissibile che ottima rispetto ad altri algoritmi di ricerca ammissibili. A* ha una stima ottimistica del costo del percorso attraverso ogni nodo considerato, l'ottimismo consiste anche nel sapere che il vero costo del percorso attraverso ciascun nodo verso il nodo goal varrà almeno quanto vale la nostra stima. Tutto è basato su quanto A* "conosce".

Quando A* ha terminato la sua ricerca, per definizione avrà trovato un percorso il cui costo attuale è più basso del costo stimato per ogni percorso attraverso tutti i nodi in open. Ma essendo tale stima ottimista, A* potrà senza pericoli ignorare tali nodi. In altre parole, A* non trascurerà mai la possibilità di trovare un percorso dal costo minore, e quindi sarà ammissibile.

Supponiamo ora che un'altro algoritmo di ricerca A termini la sua ricerca con un percorso il cui costo non sia minore del costo stimato per qualche nodo appartenente ad open. L'algoritmo A non può eliminare la possibilità, basandosi sulle informazioni euristiche che possiede, che un percorso attraverso tale nodo possa avere un costo inferiore a quanto valutato. Così anche se A potrà considerare meno nodi rispetto ad A*, non potrà essere ammissibile. Quindi, A* considera il numero di nodi più basso di qualunque altro algoritmo di ricerca ammissibile che utilizzi una funzione euristica non più accurata di quella adottata da A*.

Monotonia

Se può essere garantito che il primo percorso trovato attraverso ogni nodo sia il più breve, allora la lista di "closed" non sarà necessaria. Sarà necessaria solo una lista dei nodi già visitati, così tali nodi non saranno rivisitati (inquanto non sarà necessario farlo). Questa garanzia può essere ottenuta se la funzione euristica sarà oltre che ammissibile, anche monotona, cioè la differenza tra l'euristica di ogni due nodi connessi non supererà la distanza tra essi. Questa è una forma di disuguaglianza triangolare. Non tutte le euristiche ammissibili saranno monotone, ma la distanza in linea d'aria su di una mappe lo è.

Riferimenti

P. E. Hart, N. J. Nilsson, B. Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics SSC4 (2), pp. 100-107, 1968.
P. E. Hart, N. J. Nilsson, B. Raphael: Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", SIGART Newsletter, 37, pp. 28-29, 1972.
N. J. Nilsson, Principles of Artificial Intelligence, Tioga Publishing Company, Palo Alto, California, 1980.

Collegamenti esterni

Justin Heyes-Jones' A* algorithm tutorial
Another A* Pathfinding for Beginners
Amit's Thoughts on Path-Finding and A*
Sven Koenig's Demonstration of Lifelong Planning A* and A*
Remko Tronçon and Joost Vennekens's JSearch demo: demonstrates various search algorithms, including A*.
Sune Trudslev's Path finding in C# article

Teoria dei grafi | Algoritmi di ottimizzazione