Algoritmo A*: differenze tra le versioni

Versione delle 18:31, 26 apr 2016

Versione delle 19:37, 26 apr 2016

Riga 33:

== Perché A* è ammissibile e computazionalmente ottimo ==

C'è una spiegazione intuitiva del perché A* è sia ammissibile che ottimaottimo rispetto ad altri algoritmi di ricerca ammissibili. A* ha una 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.