Iterative deepening depth-first search: differenze tra le versioni

Versione delle 01:10, 8 apr 2011

Versione delle 16:18, 8 giu 2011

Riga 6:

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, in 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 illa [[pruningpotatura alphaalfa-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.

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