Algoritmo A*: differenze tra le versioni

Versione delle 12:23, 2 ott 2016

Versione delle 14:22, 13 nov 2016

Riga 20:

== Descrizione ==

A* comincia a partire dal [[NodoVertice (teoria dei grafi)|nodo]] selezionato. Per ogni nodo è definito un costo di entrata (di solito zero per il nodo iniziale). A* allora valuta la distanza dal nodo meta a partire da quello corrente. Questa stima ed il costo assieme formano l'euristica che sarà assegnata al percorso passante per questo nodo. Il nodo è aggiunto allora a una [[Lista (informatica)|lista]], spesso chiamata "open".

L'algoritmo allora rimuove il primo nodo dalla lista (perché avrà valore della funzione euristica più basso). Se la lista è vuota, non ci saranno percorsi dal nodo iniziale al nodo meta e l'algoritmo si arresterà. Se il nodo è il nodo meta, A* ricostruisce e pone in output il percorso ottenuto e si arresta. Questa ricostruzione del percorso a partire dai nodi più vicini significa che non è necessario memorizzare il percorso in ogni nodo.