Iterative deepening depth-first search: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Aggiungo: en:Iterative deepening depth-first search |
Fonti |
||
Riga 1:
'''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 [[
▲'''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 (algoritmi)|pruning]]) è effettivamente una [[ricerca breadth-first]].
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.
Riga 20 ⟶ 18:
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.
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.▼
▲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.
==Collegamenti esterni==
* [http://www.seanet.com/~brucemo/topics/iterative.htm Iterative deepening]
[[Categoria:Algoritmi]]
| |||