Iterative deepening depth-first search: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
m ortografia |
||
Riga 6:
La [[complessità in spazio]] dell'IDDFS è ''O(bd)'', dove <math>b</math> è il branching factor. L'iterative deepening visita più volte lo stesso stato 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.
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
Infatti la [[complessità in tempo]] dell'IDDFS in alberi bilanciati è dello stesso ordine della ricerca Depth-first — <math>O(b^{d})</math>.
| |||