2.2.2.3 Búqueda de Profundidad Iterativa (iterative o progressive deepening)

El problema con exigir un límite de profundidad, está precisamente en escoger un límite adecuado. Profundidad iterativa va aumentando gradualmente la profundidad hasta encontrar una meta. Es óptimo y completo como breadth-first pero requiere de poca memoria como depth-first.

La cantidad de nodos expandidos es similar a breadth-first, solo que algunos nodos se expanden varias veces.

Aunque parece que se repite mucho trabajo de más, en la práctica es relativamente poco.

Por ejemplo, en lugar de que sea $1 + b + b^2 + ... + b^d$, el primero se expande $d + 1$ veces, el segundo $d$ veces, el tercero $d - 1$, etc.

Por ejemplo, con un branching factor de 10 y con profundidad 5, los nodos expandidos serían $1 + 10 + 100 + \ldots + 100,000 = 111,111$, con iterative deepending son: $(d + 1)1 + (d)b + (d-1)db^2 + \ldots + 1*b^d = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456 \approx 11\%$ más de nodos.

Entre más grande sea el factor de arborecencia, menor el trabajo extra.

Sin embargo, inclusive para un árbol binario se toma como el doble de tiempo que breadth-first pero con mucho menos memoria.

En general, si el espacio de búsqueda es grande y no se sabe la profundidad del árbol es el método a usar.