Iterative deepening depth-first search: differenze tra le versioni

Versione delle 03:58, 22 feb 2015

Versione delle 03:59, 22 feb 2015

Riga 4:

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

Riga 26 ⟶ 25:

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

Riga 32 ⟶ 31:

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

'''for'''(profondità = 1; root != goal; i++) '''''=> :''''' 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)

}