Wikipedia

Iterative deepening depth-first search: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
fix +infobox +portale
Riga 18:
 
=== Complessità spaziale e temporale ===
La [[Complessità computazionale|complessità]] in spazio dell'IDDFS è ''<math>O(bd)''</math>, 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.
Estratto da "https://it.wikipedia.org/wiki/Iterative_deepening_depth-first_search"