Iterative deepening depth-first search: differenze tra le versioni

Versione delle 14:42, 3 mar 2010

Versione delle 22:10, 15 feb 2011

Riga 12:

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 è

<math>(d + 1)1b^0 + (d)bdb^{1} + (d- 1)<math>b^{2}</math> + •••\dots + 3<math>b3b^{d-2}</math> + 2<math>b2b^{d-1}</math> + <math>b^{d}</math>

Sia ad esempio b = 10 e d = 5, allora si avrà

6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

Una ricerca iterative deepening che parte dalla profondità 1 e cerca per tutte le strade sino alla profondità d espande circa l'11 % di nodi in più rispetto a una singola ricerca breadth-first o a una ricerca depth-limited con limite d, quando b = 10.