Profundización iterativa vs búsqueda en profundidad

En una búsqueda en profundidad primero, comienza en algún nodo en el gráfico y explora continuamente más y más profundo en el gráfico mientras puede encontrar nuevos nodos que aún no ha alcanzado (o hasta que encuentre la solución). Cada vez que el DFS se queda sin movimientos, retrocede hasta el último punto donde podría tomar una decisión diferente, y 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 grafique 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 hacia él (¡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 camino tomado por el DFS. Por ejemplo, podríamos hacer una búsqueda DFS, pero detener la búsqueda si alguna vez tomamos un camino de longitud mayor que 5. Esto asegura que nunca exploremos ningún nodo que esté a una distancia mayor a cinco desde el nodo de inicio, lo que significa que nunca exploramos infinitamente o (a menos que el gráfico sea extremadamente denso) no buscamos todo el gráfico. Sin embargo, esto significa que es posible que no encontremos el nodo que estamos buscando, ya que no necesariamente exploramos la totalidad grafica.

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 terminamos explorando a lo largo de infinitos caminos sin salida, ya que la longitud de cada camino está limitada por alguna longitud en cada paso. También significa que encontramos lo más corto posible ruta 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 la habríamos tomado), por lo que la ruta de longitud d + 1 es de hecho óptima.

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 y tortuoso alrededor del gráfico sin terminar nunca. Las longitudes de los caminos siempre están limitadas, por lo que nunca terminamos explorando innecesariamente rama.

La razón por la que esto es diferente de BFS es que en un BFS, tienes que mantener todos los nodos marginales en la memoria a la vez. Esto toma la memoria O (b^d), donde b es el factor de ramificación. Compare esto con el uso de memoria O(d) 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 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 pasos O(b^d) después de considerar todos los nodos O(b^d) a distancia d. La profundización iterativa usa O(b^d) tiempo por nivel, que se suma a O(b^d) en general, pero con un factor constante más alto.

En breve:

• No se garantiza que DFS encuentre un camino óptimo; la profundización iterativa sí.
• DFS puede explorar todo el gráfico antes de encontrar el nodo de destino; iterativo la profundización solo hace esto si la distancia entre el nodo inicial y final es la máxima 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!