Algoritmo A*: differenze tra le versioni

Versione delle 09:08, 28 nov 2021

Versione attuale delle 03:44, 24 ago 2024

(9 versioni intermedie di 7 utenti non mostrate)

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

Riga 115:

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