Iterative deepening depth-first search

Iterative deepening depth-first search
ClasseAlgoritmo di ricerca
Struttura datiGrafo
Caso peggiore temporalmente O ( b d ) {\displaystyle O(b^{d})} [1]
Caso peggiore spazialmente O ( d ) {\displaystyle O(d)} [2]
OttimaleSì
CompletoSì
Manuale

Iterative deepening depth-first search o IDDFS è una strategia di ricerca in uno spazio di stati (state space search) nella quale è eseguita ripetutamente una ricerca depth-limited, incrementando il limite di profondità (depth limit) ad ogni iterazione sino al raggiungimento di d {\displaystyle d} , la profondità più piccola in cui trovare lo stato obiettivo.[3]

È una strategia di ricerca particolarmente efficace, poiché ad ogni iterazione, visita i nodi 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 in ampiezza.

Valutazione della strategia

Ottimalità e completezza

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). Dal momento che la strategia restituisce lo stato soluzione legato al nodo con la profondità minore nell'albero di ricerca, è ottimale quando il costo del percorso è una funzione non-decrescente (monotona) della profondità del nodo.

Complessità spaziale e temporale

La complessità in spazio dell'IDDFS è O ( d ) {\displaystyle O(d)} ,[2] dove d {\displaystyle d} è la profondità della soluzione più vicina alla radice. Questo è dovuto al fatto che l'algoritmo non è altro che un susseguirsi di ricerche in profondità, quindi in memoria verrà mantenuto uno stack di al più d {\displaystyle d} stati contemporaneamente.

L'iterative deepening genera più volte gli stessi nodi 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.[3] Maggiore è il branching factor, minore è l'overhead dell'espansione ripetuta 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.

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à — O ( b d ) {\displaystyle O(b^{d})} , dove b {\displaystyle b} è il branching factor.

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 + d b 1 + ( d − 1 ) b 2 + ⋯ + 3 b d − 2 + 2 b d − 1 + b d {\displaystyle (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 {\displaystyle 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 {\displaystyle d} , quando b = 10 {\displaystyle b=10} .

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 iterative deepening: sfrutta l'algoritmo di ricerca in profondità limitata incrementando a ogni iterazione la profondità massima a cui cercare. 

IterativeDeepening(root, goal){
  for(profondità = 1; root != goal; profondità++) => : root = DLS(root, goal, profondità) 
}

DepthLimitedSearch(nodo, goal, profondità){
  if(profondità >= 0):
    if(nodo == goal) => : return(nodo)
    foreach(child in visita(nodo)) => : DepthLimitedSearch(child, goal, profondità-1)
}

Note

  1. ^ dove b {\displaystyle b} è il fattore di ramificazione (branching factor) e d {\displaystyle d} è la profondità della soluzione più vicina alla radice
  2. ^ a b (EN) Richard E. KORF, Depth-first iterative deepening (PDF), 1985.
  3. ^ a b Stuart Russell and Peter Norvig, Artificial Intelligence A Modern Approach 2nd Edition, pp. 88-90, Upper Saddle River, New Jersey, Pearson Education, 2003, ISBN 0-13-080302-2.

Collegamenti esterni

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica