Algoritmo A*: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Corretta l'illustrazione, che mostrava l'esecuzione di una variante di A*, con quella che esegue l'algoritmo canonico |
→Veduta d'insieme: +wl Etichette: Modifica da mobile Modifica da web per mobile |
||
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 [[euristica (scienza dei computer)|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
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.
| |||