Iterative deepening

Da Wikipedia, l'enciclopedia libera.

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 d, 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 b è 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 la potatura alfa-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 in quanto effettuata in un ordine migliore.

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

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)b^0 + db^{1} + (d- 1)b^{2} + \dots + 3b^{d-2} + 2b^{d-1} + b^{d}

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 O(b^{d}), e la complessità in spazio è O(bd). In generale, l'iterative deepening è la ricerca preferita quando c'è un vasto spazio di ricerca e la profondità della soluzione non è nota a priori.

Collegamenti esterni[modifica | modifica wikitesto]