La profundización iterativa con Depth-First Search usa mucha menos memoria que Breadth-First Search.
En cualquier punto del DFS, la cantidad de memoria en uso proporcional a los vecinos de una sola ruta a través del árbol de búsqueda. (Posiblemente menos si se pueden generar vecinos de manera ordenada). BFS usa una cantidad de memoria proporcional a todo el ancho del árbol de búsqueda. BFS rápidamente se vuelve inviable.
La compensación es que la profundización iterativa vuelve a visitar los mismos estados muchas veces. Pero, si el número de estados está creciendo exponencialmente, entonces la cantidad de tiempo dedicado a volver a visitar estados anteriores agrega solo un factor constante.
- ¿Cómo podrías escribir un programa que ingrese un número entero positivo N y genere el número de Fibonacci F2N?
- ¿Cuáles son algunos ejemplos bien conocidos donde se usa la programación dinámica?
- ¿Cómo puedo escribir un programa para encontrar el MCM de dos enteros positivos de su factorización prima?
- ¿Por qué se usa el sistema binario?
- ¿Cuál es el enfoque algorítmico para el problema spoj SPOJ.com - Problema ROBOTGRI?
Suponga que el árbol de búsqueda tiene un factor de ramificación de 10. Luego, buscarlo a la profundidad 12 significa que hay [matemáticas] 10 ^ {12} [/ matemáticas] = un billón de hojas. La profundización iterativa usa solo aproximadamente [matemática] 10 \ veces 12 = 120 [/ matemática] valor de memoria de los nodos durante la búsqueda, pero BFS tendría que utilizar casi [matemática] 10 ^ {10} [/ matemática] veces más memoria. Los nodos internos en la profundidad 11 o inferior tienen que revisarse varias veces, pero
profundidad 0, 1 nodo, se visita 13 veces
profundidad 1, 10 nodos, son visitados 12 veces
profundidad 2, 100 nodos, son visitados 11 veces
profundidad 3, 1000 nodos, son visitados 10 veces
etc., entonces DFS tiene que buscar [matemáticas] 13 \ veces 1 + 12 \ veces 10 + 11 \ veces 10 ^ 2 + 10 \ veces 10 ^ 3 + 9 \ veces 10 ^ 4 + 8 \ veces 10 ^ 5 + 7 \ veces 10 ^ 6 + 6 \ veces 10 ^ 7 + 5 \ veces 10 ^ 8 + 4 \ veces 10 ^ 9 + 3 \ veces 10 ^ {10} + 2 \ veces 10 ^ {11} + 1 \ veces 10 ^ {12} = 1234567901233 [/ math] nodos, solo un poco más (proporcionalmente) que los [math] 1111111111111 [/ math] nodos que BFS visitaría.
