Algoritmo A*
Algoritmo A* | |
---|---|
![]() | |
Classe | Algoritmo di ricerca |
Struttura dati | Grafo |
Caso peggiore temporalmente | |
Caso peggiore spazialmente | |
Ottimale | sì |
Completo | sì |
In informatica, A* (pronunciato /eɪ stɑːr/ in inglese) è 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
[modifica | modifica wikitesto]Consideriamo un esempio motivante. Ci troviamo ad un incrocio A, e vorremmo andare ad un incrocio B che fortunatamente sappiamo trovarsi a nord rispetto a noi. In questo caso gli incroci sono i vertici di un grafo e le strade sono gli archi.
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 efficace 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'esplorazione degli incroci posizionati a nord del primo, perché essi saranno probabilmente i vertici più prossimi a B. Bisogna tuttavia notare che le strade potrebbero essere chiuse obbligandoci ad andare a sud per poter raggiungere la destinazione con un percorso a forma di C. Allora, se le strade ce lo permettono, andremo ad esplorare gli incroci sempre più vicini all'incrocio goal B. Ci sarà bisogno di qualche backtrack occasionale, ma intuitivamente questa è una strategia che ha buone chance di trovare l'obiettivo velocemente. Inoltre, può essere provato che questa strategia troverà in ogni caso la strada migliore possibile, cioè la soluzione ottimale, 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 nostra 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
[modifica | modifica wikitesto]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* compirà 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, è l'effettiva distanza minima verso la 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
[modifica | modifica wikitesto]![Funzionamento dell'algoritmo](http://upload.wikimedia.org/wikipedia/commons/5/5d/AstarExample.gif)
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 lista, spesso chiamata "open".
L'algoritmo allora rimuove il primo nodo dalla lista (perché avrà valore della funzione euristica più basso). Se la lista è 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 i nodi vicini ammissibili; il modo di fare questo dipende dal problema. Per ciascun 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 lista "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 lista e posto nella lista di "closed". Il prossimo nodo sarà ottenuto dalla lista di open e con esso si ripeterà il processo descritto.
Perché A* è ammissibile e computazionalmente ottimo
[modifica | modifica wikitesto]![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/60/A%2A_Search_Example_on_North_American_Freight_Train_Network.gif/400px-A%2A_Search_Example_on_North_American_Freight_Train_Network.gif)
C'è una spiegazione intuitiva del perché A* è sia ammissibile che ottimo 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 rimasti 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*.
Monotonicità
[modifica | modifica wikitesto]Se si può garantire che il primo percorso trovato da A* verso un nodo qualsiasi è quello ottimo, allora la lista CLOSED non sarà necessaria. Sarà necessaria solo una lista dei nodi già visitati (OPEN), così tali nodi non saranno rivisitati (in quanto non sarà necessario farlo). Questa garanzia può essere ottenuta se la funzione euristica è, oltre che ammissibile, anche monotona (o consistente), cioè se la differenza tra i valori dell'euristica per ogni coppia di nodi connessi non supera il costo effettivo associato all'arco che li collega (h(n1) ≤ c(n1,n2) + h(n2)). Questa è una forma di disuguaglianza triangolare, e garantisce che i nodi lungo un qualunque cammino nello spazio di ricerca abbiano sempre f(n) (funzione di valutazione) non decrescente. Si dimostra che A*, con tale euristica, espande i nodi in ordine non decrescente di f(n), poiché grazie al requisito di monotonicità non verrà mai generato un nodo con f(n) minore di quella del padre. Se A* espande i nodi in ordine non decrescente, allora quando anche si trovasse un nuovo cammino verso un nodo già in CLOSED, lo si potrebbe ignorare perché avrebbe sicuramente f(n) maggiore o uguale a quella del nodo già espanso, ed avendo lo stesso valore di stima euristica (è lo stesso nodo) il cammino percorso fino a quel punto avrà sicuramente un costo maggiore o uguale. Lo si può dunque scartare, ed asserire che il primo percorso trovato da A* verso un nodo è il cammino ottimo fino a quel nodo.
Si dimostra che una euristica monotona è ammissibile, e quindi se si rispetta la restrizione di monotonicità si ottiene anche il percorso ottimo fino al goal. Intuitivamente, se il primo cammino trovato verso un nodo è quello ottimo (verso quel nodo) allora ciò vale anche per il nodo goal, e quindi se l'algoritmo termina, lo fa con la soluzione ottima. È utile ricordare che A*, con euristica ammissibile, termina sempre su grafi finiti e con costi strettamente positivi.
La restrizione di monotonicità è un requisito più stringente dell'ammissibilità, ma per molti problemi classici si vede che un'euristica ammissibile è, solitamente, anche monotona. Un esempio molto valido di euristica ammissibile e consistente è quella della distanza in linea d'aria tra due punti, usata nel calcolo del percorso stradale ottimo tra le città di una mappa. Questa euristica ci permette di "vedere" cosa significhi essere ammissibile e consistente. Essa è sicuramente ammissibile, poiché nessuna strada tra due punti può essere più breve della distanza in linea d'aria tra essi, e quindi l'euristica non sovrastima mai il costo da un nodo al goal. È consistente, come si vede facilmente disegnando un triangolo in cui i vertici siano tre città di una piccola mappa. Scegliamo la città di partenza e quella di arrivo, immaginando che la strada passi dalla terza città. Se disegniamo una strada qualsiasi tra la partenza e l'arrivo, la sua lunghezza è maggiore o uguale a quella del lato che li unisce, e ogni lato di un triangolo è a sua volta maggiore o uguale alla differenza tra gli altri due lati. È quindi rispettata la restrizione di monotonicità.
Pseudocodice
[modifica | modifica wikitesto]Il seguente pseudocodice descrive l'algoritmo:
function A*(start,goal) closedset := the empty set % The set of nodes already evaluated. openset := set containing the initial node % The set of tentative nodes to be evaluated. g_score[start] := 0 % Distance from start along optimal path. came_from := the empty map % The map of navigated nodes. h_score[start] := heuristic_estimate_of_distance(start, goal) f_score[start] := h_score[start] % Estimated total distance from start to goal through y. while openset is not empty x := the node in openset having the lowest f_score[] value if x = goal return reconstruct_path(came_from,goal) remove x from openset add x to closedset foreach y in neighbor_nodes(x) if y in closedset continue tentative_g_score := g_score[x] + dist_between(x,y) if y not in openset add y to openset tentative_is_better := true elseif tentative_g_score < g_score[y] tentative_is_better := true else tentative_is_better := false if tentative_is_better = true came_from[y] := x g_score[y] := tentative_g_score h_score[y] := heuristic_estimate_of_distance(y, goal) f_score[y] := g_score[y] + h_score[y] return failure function reconstruct_path(came_from,current_node) if came_from[current_node] is set p = reconstruct_path(came_from,came_from[current_node]) return (p + current_node) else return the empty path
Bibliografia
[modifica | modifica wikitesto]- 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.
Voci correlate
[modifica | modifica wikitesto]Altri progetti
[modifica | modifica wikitesto]Wikimedia Commons contiene immagini o altri file sull'algoritmo A*
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Justin Heyes-Jones' A* algorithm tutorial (archiviato dall'url originale il 3 novembre 2012).
- (EN) Another A* Pathfinding for Beginners, su policyalmanac.org. URL consultato il 28 gennaio 2006 (archiviato dall'url originale il 24 dicembre 2005).
- (EN) Amit's Thoughts on Path-Finding and A*.
- (EN) Sven Koenig's Demonstration of Lifelong Planning A* and A*.
- (EN) Remko Tronçon and Joost Vennekens's JSearch demo (archiviato dall'url originale l'11 febbraio 2006).: demonstrates various search algorithms, including A*.
- (EN) Sune Trudslev's Path finding in C# article (archiviato dall'url originale il 21 luglio 2006).