Iterative deepening depth-first search: differenze tra le versioni

Versione delle 01:37, 23 set 2008

Versione delle 20:27, 22 ago 2009

Riga 7:

Il maggior vantaggio in questo algoritmo nella ricerca su alberi è che le prime ricerche tendono a migliorare le euristiche maggiormente utilizzate, come la [[euristica killer]] e il [[pruning alpha-beta]], e quindi si ha una stima più accurata del peso dei vari nodi alla fine della ricerca in profondità, e il completamento della ricerca avviene più velocemente inquanto effettuata in un ordine migliore.

In fatti la [[complessità in tempo]] dell'IDDFS in alberi bilanciati è dello stesso ordine della ricerca Depth-first &mdash;— <math>O(b^{d})</math>.

In una ricerca iterative deepening i nodi posti in basso sono espansi una volta, quelli successivi all'ultimo livello sono espansi due volte, e così via, sino alla radice dell'albero di ricerca, che è espanso d + 1 volte. Così il numero totale di espansioni in una ricerca iterative deepening è