En una búsqueda en profundidad, comienza en algún nodo del gráfico y explora cada vez más en el gráfico mientras puede encontrar nuevos nodos que aún no ha alcanzado (o hasta encontrar la solución). Cada vez que el DFS se queda sin movimientos, retrocede al último punto donde podría hacer una elecció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 podría terminar explorando todo el gráfico a lo largo de una ruta DFS solo para encontrar la solución luego de observar cada nodo. Peor aún, si el gráfico es infinito (tal vez su gráfico se compone de todos los números, por ejemplo), la búsqueda podría no finalizar. Además, una vez que encuentre el nodo que está buscando, es posible que no tenga la ruta óptima (podría haber colocado un bucle en todo el gráfico buscando la solución aunque estuviera 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 detener la búsqueda si alguna vez tomamos una ruta de longitud mayor que 5. Esto asegura que nunca exploremos ningún nodo que esté a una distancia mayor que cinco desde el nodo de inicio, lo que significa que nunca exploraremos infinitamente o (a menos que el gráfico sea extremadamente denso) no buscamos el gráfico completo. Sin embargo, esto significa que es posible que no encontremos el nodo que estamos buscando, ya que no exploramos necesariamente todo el gráfico.
La idea detrás de la profundización iterativa es utilizar este segundo enfoque, pero para seguir aumentando la profundidad en cada nivel. En otras palabras, podríamos intentar explorar usando todos los caminos de longitud uno, luego todos los caminos de longitud dos, luego longitud tres, etc. hasta que terminemos encontrando el nodo en cuestión. Esto significa que nunca terminaremos 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 la profundidad d pero lo encontramos en la profundidad d + 1, no puede haber una ruta de longitud d (o lo habría tomado), por lo que la ruta de longitud d + 1 es realmente óptima.
La razón por la que esto es diferente de un DFS es que nunca se ejecuta en el caso en que se necesita una ruta extremadamente larga y tortuosa alrededor del gráfico sin terminar nunca. Las longitudes de las rutas siempre tienen un límite, por lo que nunca terminaremos explorando ramas innecesarias.
La razón de que esto sea diferente de BFS es que en un BFS, debe mantener todos los nodos de franjas en la memoria a la vez. Esto toma la memoria O (b d), donde b es el factor de bifurcación. Compare esto con el uso de la memoria O (d) a partir de la profundización iterativa (para mantener el estado de cada uno de los nodos d en la ruta actual). Por supuesto, BFS nunca explora la misma ruta varias veces, mientras que la profundización iterativa puede explorar cualquier ruta 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 finaliza en O (b d) pasos después de considerar todos los nodos O (b d) a la distancia d. La profundización iterativa usa O (b d) tiempo por nivel, que suma hasta O (b d) en general, pero con un factor constante más alto.
En resumen:
- DFS no está garantizado para encontrar un camino óptimo; la profundización iterativa es.
- DFS puede explorar todo el gráfico antes de encontrar el nodo de destino; la profundización iterativa solo lo hace si la distancia entre el nodo inicial y el final es el máximo en el gráfico.
- BFS y la profundización iterativa ambos se ejecutan en O (b d), pero la profundización iterativa tiene un factor de constante más alto.
- BFS usa la memoria O (b d), mientras que la profundización iterativa usa solo O (d).
Espero que ayude!
En la búsqueda en profundidad, explora cada rama que ingresa por completo antes de retroceder e ir a la siguiente. En la profundización iterativa, no vas por debajo de la profundidad actual, y por lo tanto no exploras cada rama que visitas por completo antes de retroceder. – HelloGoodbye