Algoritmo A*: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m →Veduta d'insieme: fix wikilink |
|||
Riga 45:
== Perché A* è ammissibile e computazionalmente ottimo ==
[[File:A* Search Example on North American Freight Train Network.gif|thumb|upright=1.8|Animazione dell'algoritmo A* che esplora il Nord America cercando un percorso tra Washington D.C. e Los Angeles.]]
C'è una spiegazione intuitiva del perché A* è sia ammissibile che ottimo rispetto ad altri algoritmi di ricerca ammissibili. A* ha una [[Euristica ammissibile|stima ottimistica]] del costo del percorso attraverso ogni nodo considerato, l'ottimismo consiste anche nel sapere che il vero costo del percorso attraverso ciascun nodo verso il nodo goal varrà almeno quanto vale la nostra stima. Tutto è basato su quanto A* "conosce".
Quando A* ha terminato la sua ricerca, per definizione avrà trovato un percorso il cui costo attuale è più basso del costo stimato per ogni percorso attraverso tutti i nodi rimasti in open. Ma essendo tale stima ottimista, A* potrà senza pericoli ignorare tali nodi. In altre parole, A* non trascurerà mai la possibilità di trovare un percorso dal costo minore, e quindi sarà ammissibile.
| |||