Iterative deepening depth-first search: differenze tra le versioni

Versione delle 22:20, 29 ago 2009

Versione delle 14:42, 3 mar 2010

Riga 4:

La ricerca iterative deepening depth-first combina l'efficienza in spazio della [[ricerca depth-first]] e la completezza della [[ricerca breadth-first]] (quando il [[branching factor]] è finito). La ricerca è ottimale quando il costo del percorso è una funzione non-decrescente (monotona) della profondità del nodo.

La [[complessità in spazio]] dell'IDDFS è ''O(bd)'', dove <math>b</math> è il branching factor. L'iterative deepening visita più volte lo stesso stato e ciò potrebbe sembrare dispendioso, ma in fin dei conti non lo è tanto, inquantoin quanto in un albero la maggior parte dei nodi sono nel livello più basso, quindi non preoccupa molto il fatto che i livelli superiori siano visitati più volte.

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 fattiInfatti la [[complessità in tempo]] dell'IDDFS in alberi bilanciati è dello stesso ordine della ricerca Depth-first — <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 è