Iterative deepening depth-first search: differenze tra le versioni

Versione delle 20:35, 7 nov 2018

Versione delle 17:31, 30 mag 2019

Riga 1:

{{tmp|Algoritmo}}

|classe = [[Algoritmo di ricerca]]

'''Iterative deepening depth-first search''' o '''IDDFS''' è una strategia di ricerca in uno spazio di 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 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.</ref>

|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">{{Cite journal|last=KORF|first=Richard E.|date=|year=1985|title=Depth-first iterative deepening|url=https://cse.sc.edu/~mgv/csce580f09/gradPres/korf_IDAStar_1985.pdf|language=en|publication-date=1985}}</ref>

|completo = Sì

|ottimale = Sì

}}

'''Iterative deepening depth-first search''' o '''IDDFS''' è una strategia di ricerca in uno spazio di stati ('State'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 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.</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]].

Riga 11 ⟶ 20:

La [[Complessità computazionale|complessità]] in spazio dell'IDDFS è ''O(bd)'', dove <math>b</math> è il branching factor. 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.<ref name="rn3"/>

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 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>.

Riga 29 ⟶ 38:

== 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.

<syntaxhighlight lang="php">

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

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

}

DepthLimitedSearch(nodo, goal, profondità){

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

''' if'''(profondità >= 0):

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

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

}

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

}

'''if'''(profondità >= 0):

</syntaxhighlight>

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

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

}

== Note ==

Riga 43 ⟶ 54:

{{Algoritmi ricerca grafi}}

{{portale|informatica}}

[[Categoria:Algoritmi di ricerca]]