Algoritmo A*: differenze tra le versioni

Versione delle 14:54, 5 feb 2018

Versione delle 13:47, 21 ott 2018

Riga 23:

== 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à 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 meta. Un esempio di euristica pratica ammissibile è la distanza in linea d'aria dalla meta su una mappa.