Algoritmo A*: differenze tra le versioni

Versione delle 14:04, 30 gen 2016

Versione attuale delle 03:44, 24 ago 2024

(37 versioni intermedie di 20 utenti non mostrate)

Riga 1:

{{NN|informatica|ottobre 2018}}

{{Algoritmo|class = [[Algoritmo di ricerca]]|data = [[Grafo]]|image = |space = |optimal = }}Nell'[[informatica]], '''A*''' (pronunciato {{IPA|[eɪ stɑːr]}} in [[lingua inglese|inglese]]) è un [[algoritmo di ricerca]] su [[grafo|grafi]] che individua un percorso da un dato [[Nodo (grafi)|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]].

{{Algoritmo

|classe = [[Algoritmo di ricerca]]

|struttura dati = [[Grafo]]

|immagine = Astar_progress_animation.gif

|didascalia =

|tempo = <math>O(|E|) = O(b^d)</math>

|spazio = <math>O(|V|) = O(b^d)</math>

|ottimale = sì

|completo = sì

}}

{{Algoritmo|classIn = [[Algoritmo di ricerca]]|data = [[Grafo]]|image = |space = |optimal = }}Nell'[[informatica]], '''A*''' (pronunciato {{IPA|[/eɪ stɑːr]/}} in [[lingua inglese|inglese]]) è un [[algoritmo di ricerca]] su [[grafo|grafi]] che individua un percorso da un dato [[Nodo (grafi)|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]].

Line 8 ⟶ 19:

Se si effettua una [[Visita in ampiezza|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 chanceschance 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 ==

Un algoritmo di ricerca che garantisce sempre di trovare il percorso più corto verso una meta è detto ammissibile. Se A* utilizza una [[euristicaEuristica (scienza dei computerinformatica)|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à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 ==

[[File:AstarExample.gif|right|Funzionamento dell'algoritmo]]

A* comincia a partire dal [[NodoVertice (teoria dei grafi)|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 (informatica)|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.

Line 32 ⟶ 44:

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 ottimaottimo ==

[[File:A* Search Example on North American Freight Train Network.gif|thumb|upright=1.8|Animazione dell'algoritmo A* che esplora il Nord America cercando un percorso tra Washington D.C. e Los Angeles.]]

C'è una spiegazione intuitiva del perché A* è sia ammissibile che ottimaottimo rispetto ad altri algoritmi di ricerca ammissibili. A* ha una [[Euristica ammissibile|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.

Line 40 ⟶ 53:

== Monotonicità ==

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 disegnamodisegniamo 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à.

== Pseudo CodicePseudocodice ==

Il seguente [[pseudo codicepseudocodice]] descrive l'algoritmo:

<sourcesyntaxhighlight lang="cpp">

function A*(start,goal)

closedset := the empty set % The set of nodes already evaluated.

Line 89 ⟶ 102:

else

return the empty path

</syntaxhighlight>

</source>

== Bibliografia ==

Line 95 ⟶ 108:

* P. E. Hart, N. J. Nilsson, B. Raphael: ''Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"'', [[Association for Computing Machinery|SIGART]] Newsletter, 37, pp.&nbsp;28–29, 1972.

* N. J. Nilsson, ''Principles of Artificial Intelligence'', Tioga Publishing Company, Palo Alto, California, 1980.

== Voci correlate ==

* [[Algoritmo euristico]]

* [[IDA*]]

* [[SMA*]]

== Altri progetti ==

{{interprogetto|commonspreposizione=A* Algorithmsull'}}

== Collegamenti esterni ==

* {{en}} Justin Heyes-Jones' [{{cita testo|url=http://www.heyes-jones.com/astar.html |titolo=A* algorithm tutorial]|accesso=27 ottobre 2019|dataarchivio=3 novembre 2012|urlarchivio=https://web.archive.org/web/20121103080323/http://www.heyes-jones.com/astar.html|urlmorto=sì}}

* {{cita web|url=http://www.policyalmanac.org/games/aStarTutorial.htm|titolo=Another A* Pathfinding for Beginners|lingua=en|urlmorto=sì|accesso=28 gennaio 2006|urlarchivio=https://web.archive.org/web/20051224192823/http://www.policyalmanac.org/games/aStarTutorial.htm}}

* {{en}} Amit's [{{cita testo|url=http://theory.stanford.edu/~amitp/GameProgramming/ |titolo=Thoughts on Path-Finding and A*]}}

* {{en}} Sven Koenig's [{{cita testo|url=http://idm-lab.org/applet.html |titolo=Demonstration of Lifelong Planning A* and A*]}}

* {{en}}Remko Tronçon and Joost Vennekens's [{{cita testo|url=http://www.cs.kuleuven.ac.be/~remko/jsearchdemo/ |titolo=JSearch demo]|urlarchivio=https://web.archive.org/web/20060211143354/http://www.cs.kuleuven.ac.be/~remko/jsearchdemo/ }}: demonstrates various search algorithms, including A*.

* {{en}} Sune Trudslev's [{{cita testo|url=http://www.tanis.dk/wiki/index.php/Path_finding_in_C_sharp |titolo=Path finding in C# article]|accesso=5 febbraio 2018|dataarchivio=21 luglio 2006|urlarchivio=https://web.archive.org/web/20060721132449/http://www.tanis.dk/wiki/index.php/Path_finding_in_C_sharp|urlmorto=sì}}

{{Algoritmi ricerca grafi}}