Iterative deepening depth-first search: differenze tra le versioni

Versione delle 16:18, 8 giu 2011

Versione attuale delle 16:37, 29 ott 2023

(35 versioni intermedie di 19 utenti non mostrate)

Riga 1:

{{Algoritmo

{{Algoritmi ricerca grafi}}

|classe = [[Algoritmo di ricerca]]

'''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 <math>d</math>, 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]].

|immagine =

|didascalia =

|struttura dati = [[Grafo]]

|tempo = <math>O(b^d)</math><ref>dove <math>b</math> è il fattore di ramificazione (''branching factor'') e <math>d</math> è la profondità della soluzione più vicina alla radice</ref>

|spazio = <math>O(d)</math><ref name="re1985">{{Cita pubblicazione|cognome=KORF|nome=Richard E.|data=|anno=1985|titolo=Depth-first iterative deepening|url=https://cse.sc.edu/~mgv/csce580f09/gradPres/korf_IDAStar_1985.pdf|lingua=en|datapubblicazione=1985}}</ref>

|completo = Sì

|ottimale = Sì

}}

'''Iterative deepening depth-first search''' o '''IDDFS''' è una strategia di [[ricerca nelloin uno spazio deglidi stati]] (''state space search'') nella quale è eseguita ripetutamente una [[Depth-limited search|ricerca depth-limited]], incrementando il limite di profondità (''depth limit'') ad ogni iterazione sino al raggiungimento di <math>d</math>, la profondità più piccola in cui trovare lo stato obiettivo.<ref name="rn3">Stuart AdRussell ogniand Peter iterazioneNorvig, l'algoritmoArtificial IDDFSIntelligence visitaA ilModern nodoApproach nell'[[albero2nd diEdition, ricerca]]pp. nello stesso ordine di una [[ricerca depth88-first]]90, maUpper inSaddle questoRiver, casoNew l'ordineJersey, cumulativoPearson nelEducation, quale2003, iISBN nodi sono visitati per primi (assumendo l'assenza di [[pruning]]) è effettivamente una [[ricerca breadth0-13-080302-first]]2.</ref>

È una strategia di ricerca particolarmente efficace, poiché ad ogni iterazione, visita i nodi nell'[[Albero (informatica)|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]].

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.

== Valutazione della strategia ==

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.

=== Ottimalità e completezza ===

La ricerca iterative deepening depth-first combina l'efficienza in spazio della [[ricerca depth-first]] e la completezza della [[Ricerca in ampiezza|ricerca breadth-first]] (quando il [[branching factor]] è finito). LaDal 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 ===

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 inquanto effettuata in un ordine migliore.

La [[Complessità computazionale|complessità]] in spazio dell'IDDFS è <math>O(d)</math>,<ref name="re1985"/> dove <math>d</math> è 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ù <math>d</math> stati contemporaneamente.

La [[complessità in spazio]] dell'IDDFS è ''O(bd)'', dove <math>b</math> è il branching factor. L'iterative deepening visitagenera più volte logli stessostessi statonodi 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.<ref name="rn3"/> 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.

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

Il maggior vantaggio in questo algoritmo nella ricerca su alberi è che le prime ricerche tendono a migliorare le [[Euristica (informatica)|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 inquantoin quanto effettuata in un ordine migliore.

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 è

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

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

:<math>(d + 1)b^0 + db^{1} + (d- 1)b^{2} + \dots + 3b^{d-2} + 2b^{d-1} + b^{d}</math>

Sia ad esempio b = 10 e d = 5, allora si avrà

:<math>6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456</math>

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 <math>d</math>, quando <math>b = 10</math>.

6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

In generale, l'iterative deepening è la ricerca preferita quando c'è un vasto spazio di ricerca e la profondità della soluzione non è nota a priori.

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.

== Algoritmo ==

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.

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

<syntaxhighlight lang="php">

IterativeDeepening(root, goal){

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

}

DepthLimitedSearch(nodo, goal, profondità){

==Collegamenti esterni==

if(profondità >= 0):

* [http://www.seanet.com/~brucemo/topics/iterative.htm Iterative deepening]

if(nodo == goal) => : return(nodo)

foreach(child in visita(nodo)) => : DepthLimitedSearch(child, goal, profondità-1)

}

</syntaxhighlight>

== Note ==

[[Categoria:Algoritmi]]

<references />

== Collegamenti esterni ==

* {{FOLDOC|iterative deepening|iterative deepening}}

{{Algoritmi ricerca grafi}}

{{portale|informatica}}

[[Categoria:Algoritmi di ricerca]]

[[de:Iterative Tiefensuche]]

[[Categoria:Algoritmi sui grafi]]

[[en:Iterative deepening depth-first search]]

[[ja:反復深化深さ優先探索]]

[[nl:Iteratief diepte-eerst zoeken]]