Antes de comprender cómo la búsqueda de profundización iterativa combina lo mejor de la búsqueda de profundidad primero (DFS) y la búsqueda de amplitud primero (BFS), veamos primero BFS y DFS.
Búsqueda de amplitud primero (BFS)
- ¿Debería un algoritmo de aprendizaje automático estar completo?
- ¿Por qué el método Arrays.sort en Java implementa timsort en lugar de contar?
- Cómo escribir algoritmo para asignaturas requeridas
- Según Knuth, un algoritmo puede tener cero o más entradas. ¿Alguien puede darme un ejemplo de un algoritmo sin entrada?
- ¿Cuáles son las principales diferencias en términos de definición / idea clave, dominio de aplicación y eficiencia entre árboles de segmento, árboles de intervalo, árboles indexados binarios y árboles de rango?
(Imagen tomada de Breadth-first search – Wikipedia)
Como su nombre indica, la estrategia BFS expande primero el nodo raíz, luego todos sus sucesores se expanden a continuación, y así sucesivamente. Si observa la imagen, los números dentro de los nodos representan el orden en que se expanden los nodos. En palabras simples, todos los nodos en cualquier nivel dado se expanden primero antes de que se expanda cualquier nodo en el siguiente nivel .
Ventajas de usar la estrategia BFS
- La estrategia de BFS se completa siempre que el factor de ramificación b (número de hijos en cada nodo) es finito Significa que está garantizado encontrar el nodo objetivo a la profundidad d, ya que eventualmente llegaría al nodo objetivo después de expandir todos los nodos menos profundos.
- La estrategia BFS es óptima siempre que el costo del trayecto sea una función no decreciente de la profundidad del nodo (por ejemplo, cuando todos los bordes tienen el mismo costo)
Contras de usar la estrategia BFS
La estrategia BFS tiene requisitos de memoria locos. Para darle un ejemplo, considere un espacio de estado donde cada estado tiene b sucesores. La búsqueda comienza desde el nodo raíz que genera b sucesores en el primer nodo, luego esos b nodos generan [matemática] b ^ 2 [/ matemática] nodos al segundo nivel y así sucesivamente.
Ahora considere que el estado del objetivo está en el nivel d , entonces el número total de nodos generados sería
[matemáticas] b + b ^ 2 +. . + b ^ d + (b ^ {d + 1} – b) = O (b ^ {d + 1}) [/ matemática]
Puede ver claramente que el número de nodos y el requisito de espacio aumenta exponencialmente con la profundidad . Y debe mantener todos esos nodos en la memoria, ya que cada uno de ellos es una franja (nodos que se han generado pero no se han expandido) o es un antepasado de un nodo marginal.
Búsqueda de profundidad primero (DFS)
(Imagen tomada de la búsqueda de profundidad primero – Wikipedia)
La estrategia DFS comienza en el nodo raíz y atraviesa una rama hasta llegar al nodo más profundo. Si hace referencia a la imagen, puede ver cómo solo se atraviesa la rama de un nodo antes de expandir cualquiera de sus hermanos. Después de alcanzar un nodo más profundo sin sucesor en una ruta, la búsqueda “retrocede” y expande el siguiente nodo sucesor.
Ventajas de usar DFS
DFS no tiene un alto requisito de memoria . Necesita almacenar solo la ruta desde el nodo raíz a un nodo hoja junto con los nodos hermanos no expandidos para cada nodo en la ruta. Tan pronto como se exploran todos los descendientes de un nodo, se puede eliminar de la memoria.
Como los nodos b se generan en cada nivel, los nodos máximos en la memoria en el peor de los casos serían bm + 1, donde m es la profundidad máxima (tenga en cuenta que m podría ser mayor que d) . Por lo tanto, el requisito de espacio está limitado por [math] O (bm) [/ math]
Contras de usar DFS
DFS puede atascarse en la rama incorrecta incluso cuando una elección diferente de rama podría haber llevado a una solución cerca de la raíz del árbol de búsqueda. Si la rama elegida es de profundidad ilimitada, DFS nunca terminaría y, por lo tanto, no está completa.
DFS no es óptimo ya que nunca se puede saber si había otra solución a un nivel más bajo que la solución encontrada (ya que DFS no mira a los nodos hermanos en el mismo nivel)
DFS de profundización iterativa
(Fuente de la imagen RESOLVIENDO PROBLEMAS BUSCANDO)
La profundización iterativa DFS en palabras simples ejecuta DFS al aumentar gradualmente el límite de profundidad – 0, luego repite DFS desde el principio con el límite de profundidad 1, luego repite DFS desde el principio con el nivel de profundidad 2, y así sucesivamente, hasta encontrar una solución . Entonces, ¿cómo combina esto los beneficios de DFS y BFS?
- Tiene requisitos de memoria modestos como DFS, es decir, [math] O (bm) [/ math]. Creo que esto es bastante sencillo de entender. Dado que ejecuta un DFS (aunque al aumentar el nivel de profundidad con cada iteración), sus requisitos de memoria serían los mismos que los de DFS.
- Es óptimo siempre que el costo de la ruta sea una función no decreciente de la profundidad del nodo, como BFS. Como está repitiendo la estrategia DFS al aumentar el límite de profundidad con cada iteración, puede estar seguro de que atravesó a los hermanos de sus antepasados en iteraciones anteriores, lo que a su vez garantiza que no existió un estado de solución en un nivel más superficial.
- Está completo como BFS, siempre que el factor de ramificación sea finito. Dado que también atraviesa la amplitud, ya que está repitiendo DFS con niveles de profundidad cada vez mayores, no puede atascarse en un camino infinito.
TLDR: la profundización iterativa DFS combina la eficiencia de la memoria de DFS y la integridad y la optimización de BFS.
Aquí hay una tabla que le daría una comparación objetiva:
donde b es el factor de ramificación, d es la profundidad de la solución más superficial ym es la profundidad máxima del árbol de búsqueda.
Información de bonificación
Si se pregunta si IDS es ineficiente, ya que expande muchos nodos varias veces en cada iteración, entonces la respuesta es no, no es tan ineficiente. La razón de esto es realmente simple, los nodos que se generarían la mayor cantidad de veces serían los nodos en la parte superior y dado que se genera una menor cantidad de nodos en la parte superior, no tendría un impacto significativo.
Espero que haya ayudado 🙂
Fuentes:
Búsqueda de profundidad primero – Wikipedia
Búsqueda de amplitud primero – Wikipedia
Profundización iterativa búsqueda en profundidad – Wikipedia
Inteligencia artificial: un enfoque moderno (3a edición): Stuart Russell, Peter Norvig: 8601419506989: Amazon.com: Libros
