Profundización iterativa frente a la búsqueda de profundidad primero

Question

Sigo leyendo sobre profundización iterativa, pero no entiendo cómo difiere de búsqueda de profundidad.

Entendí que la búsqueda de profundidad primero sigue siendo más profunda y profunda.

En la profundización iterativa, establece un valor de un nivel, si no hay solución en ese nivel, incrementa ese valor y comienza nuevamente desde cero (la raíz).

¿No sería esto lo mismo que la búsqueda de profundidad?

Quiero decir que seguirías incrementando e incrementando, profundizando hasta que encuentres una solución. ¡Veo esto como lo mismo! Sentaría por la misma rama, porque si empiezo de nuevo desde cero, iría por la misma rama que antes.

Answer 1

En una búsqueda en profundidad, comienza en algún nodo en el gráfico y explora continuamente más y más profundamente en el gráfico mientras puede encontrar nuevos nodos que aún no haya alcanzado (o hasta que encuentre la solución). Cada vez que el DFS se queda sin movimientos, retrocede al último punto donde podría tomar una decisión diferente, luego explora desde allí. Esto puede ser un problema grave si su gráfico es extremadamente grande y solo hay una solución, ya que puede terminar explorando todo el gráfico a lo largo de una ruta DFS solo para encontrar la solución después de mirar cada nodo. Peor aún, si el gráfico es infinito (tal vez su gráfico consiste en todos los números, por ejemplo), la búsqueda podría no terminar. Además, una vez que encuentre el nodo que está buscando, es posible que no tenga la ruta óptima (¡podría haber recorrido todo el gráfico buscando la solución a pesar de que estaba justo al lado del nodo de inicio!)

Una posible solución a este problema sería limitar la profundidad de cualquier ruta tomada por el DFS. Por ejemplo, podríamos hacer una búsqueda DFS, pero detenga la búsqueda si alguna vez tomamos una ruta de longitud mayor que 5. Esto asegura que nunca exploremos ningún nodo que esté de distancia mayor de cinco desde el nodo de inicio, lo que significa que nunca exploramos fuera infinitamente o (a menos que el gráfico sea extremadamente denso) no buscamos todo el gráfico. Sin embargo, esto significa que podríamos no encontrar el nodo que estamos buscando, ya que no necesariamente exploramos todo el gráfico.

La idea detrás de la profundización iterativa es usar este segundo enfoque, pero seguir aumentando la profundidad en cada nivel. En otras palabras, podríamos intentar explorar el uso de todas las rutas de longitud una, luego todas las rutas de longitud dos, luego longitud tres, etc. hasta que terminemos encontrando el nodo en cuestión. Esto significa que nunca terminamos explorando a lo largo de infinitos caminos sin salida, ya que la longitud de cada ruta está limitada por cierta longitud en cada paso. También significa que encontramos la ruta más corta posible al nodo de destino, ya que si no encontramos el nodo en profundidad D pero lo encontramos en profundidad d + 1, no puede haber una ruta de longitud d (o nosotros lo habría tomado), por lo que el camino de la longitud D + 1 es de hecho óptimo.

La razón por la que esto es diferente de un DFS es que nunca se encuentra en el caso en el que toma un camino extremadamente largo e tortuoso alrededor del gráfico sin terminar. Las longitudes de los caminos siempre están limitados, por lo que nunca terminamos explorando ramas innecesarias.

La razón por la que esto es diferente de BFS es que en un BFS, debe mantener todos los nodos marginales en la memoria a la vez. Esto toma memoria o (b^d), donde B es el factor de ramificación. Compare esto con el uso de memoria O (D) desde la profundización iterativa (para mantener el estado para cada uno de los nodos D en la ruta actual). Por supuesto, BFS nunca explora el mismo camino varias veces, mientras que la profundización iterativa puede explorar cualquier camino varias veces a medida que aumenta el límite de profundidad. Sin embargo, asintóticamente los dos tienen el mismo tiempo de ejecución. BFS termina en O (B^d) Pasos después de considerar todo O (B^d) nodos a la distancia d. La profundización iterativa usa o (b^d) Tiempo por nivel, que resume hasta o (b^d) en general, pero con un factor constante más alto.

En breve:

• DFS no está garantizado para encontrar una ruta óptima; La profundización iterativa es.
• DFS puede explorar todo el gráfico antes de encontrar el nodo de destino; La profundización iterativa solo hace esto si la distancia entre el nodo de inicio y el final es el máximo en el gráfico.
• BFS y la profundización iterativa se ejecutan en O (B^d), pero la profundización iterativa tiene un factor constante más alto.
• BFS usa O (B^d) memoria, mientras que la profundización iterativa usa solo o (d).

¡Espero que esto ayude!

Answer 2

Hay una página decente en Wikipedia sobre esto.

La idea básica que creo que te perdiste es que la profundización iterativa es principalmente una heurístico. Cuando es probable que una solución se encuentre cerca de la profundización iterativa de la raíz, la IS lo encontrará relativamente rápido, mientras que la búsqueda directa de profundidad primero podría tomar una decisión "incorrecta" y pasar mucho tiempo en una rama profunda infructuosa.

(Esto es particularmente importante cuando el árbol de búsqueda puede ser infinito. En este caso son aún menos equivalentes Dado que DFS puede quedarse atascado para siempre, mientras que BFS o la profundización iterativa seguramente encontrarán la respuesta algún día si existe)

Answer 3

Simplemente agregando a lo que ya está aquí, pero aquí hay algunos videos del Laboratorio AI conmovedor de la Universidad de Denver que muestran las diferencias.

http://movingai.com/dfid.html

Puede ver en sus ejemplos gana la profundización iterativa cuando el objetivo es superficial (profundidad de la solución 3, profundidad del árbol) y la solución está a la derecha, pero DFS gana sin importar qué si la solución está en la última fila.

Me metí en esta lectura sobre la programación de ajedrez, lo siguiente para mí fue pensar en búsqueda de quiescence Vea eso si desea saber más sobre las estrategias de búsqueda para la programación de IA.