Iterative deepening depth-first search: differenze tra le versioni

Versione delle 14:14, 30 gen 2016

Versione delle 20:03, 7 mag 2017

Riga 14:

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 in profondità — <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 è

Riga 24:

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

== Algoritmo ==

Questo algoritmo (in pseudocodice) è una possibile implementazione della strategia di iterive deepening: sfrutta l'algoritmo di [[Depth-limited search |ricerca in profondità limitata]] incrementando a ogni iterazione la profondità massima a cui cercare.

'''''IterativeDeepening'''''(''root'', ''goal''){

Riga 41:

== Note ==

<references />

{{reflist}}

{{Algoritmi ricerca grafi}}