|
|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]].
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 ==
== 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 A* algorithm tutorial]|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/ |data=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}}
| 