Algoritmo A*: differenze tra le versioni

Versione delle 09:24, 9 ago 2019

Versione attuale delle 03:44, 24 ago 2024

(16 versioni intermedie di 13 utenti non mostrate)

Riga 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]].

Riga 26:

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

Riga 58:

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

== Pseudocodice ==

Il seguente [[pseudocodice]] descrive l'algoritmo:

<sourcesyntaxhighlight lang="cpp">

function A*(start,goal)

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

Riga 102:

else

return the empty path

</syntaxhighlight>

</source>

== Bibliografia ==

Riga 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|1url=http://www.policyalmanac.org/games/aStarTutorial.htm|2titolo=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|dataarchivio=24 dicembre 2005}}

* {{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] {{Webarchive|urlurlarchivio=https://web.archive.org/web/20060211143354/http://www.cs.kuleuven.ac.be/~remko/jsearchdemo/ |date=11 febbraio 2006 }}: 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 Path finding in C# article]|urlmorto=sì}}

{{Algoritmi ricerca grafi}}