Iterative deepening depth-first search: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m smistamento lavoro sporco e fix vari |
m →Complessità spaziale e temporale: fix wl |
||
Riga 9:
=== Complessità spaziale e temporale ===
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"/>▼
▲La 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 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.
| |||