Algoritmo A*: differenze tra le versioni

Versione delle 13:19, 24 giu 2017

Versione attuale delle 03:44, 24 ago 2024

(27 versioni intermedie di 16 utenti non mostrate)

Riga 1:

{{NN|informatica|ottobre 2018}}

{{Algoritmo

|classe = [[Algoritmo di ricerca]]

|struttura dati = [[Grafo]]

|immagine = Weighted A star with eps 5Astar_progress_animation.gif

|didascalia =

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

Line 9 ⟶ 10:

|completo = sì

}}

Nell'In [[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 23 ⟶ 24:

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

Line 44 ⟶ 45:

== Perché A* è ammissibile e computazionalmente ottimo ==

[[File:A* Search Example on North American Freight Train Network.gif|right|thumb|400pxupright=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 ottimo 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 52 ⟶ 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 [[Pseudocodicepseudocodice]] descrive l'algoritmo:

<sourcesyntaxhighlight lang="cpp">

function A*(start,goal)

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

Line 101 ⟶ 102:

else

return the empty path

</syntaxhighlight>

</source>

== Bibliografia ==

Line 107 ⟶ 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}}