Iterative deepening depth-first search
Iterative deepening depth-first search o IDDFS è una strategia di ricerca nello spazio degli stati nella quale è eseguita ripetutamente una ricerca depth-limited, incrementando il limite di profondità (depth limit) ad ogni iterazione sino al raggiungimento di , la profondità più piccola in cui trovare lo stato obiettivo. Ad ogni iterazione, l'algoritmo IDDFS visita il nodo nell'albero di ricerca nello stesso ordine di una ricerca depth-first, ma in questo caso l'ordine cumulativo nel quale i nodi sono visitati per primi (assumendo l'assenza di pruning) è effettivamente una ricerca breadth-first.
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 è 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 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.
Infatti la complessità in tempo dell'IDDFS in alberi bilanciati è dello stesso ordine della ricerca Depth-first — .
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 è
(d + 1)1 + (d)b + (d- 1) + ••• + 3 + 2 +
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.
Maggiore è il branching factor, minore è l'overhead dell'espansione iterata degli stati intermedi, ma anche quando il branching factor è 2, l'iterative deepening spende solo il doppio in tempo rispetto ad una ricerca breadth-first completa. Ciò significa che la complessità in tempo dell'iterative deepening è circa , e la complessità in spazio è . In generale, l'iterative deepening è la ricerca preferita quando c'è un vasto spazio di ricerca e la profondità della soluzione non è nota a priori.
