algorithm - preferente - busqueda profundidad iterativa java
Profundización iterativa vs búsqueda en profundidad (3)
Sigo leyendo sobre la profundización iterativa , pero no entiendo cómo difiere de la búsqueda en profundidad .
Comprendí que la búsqueda en profundidad continúa más y más.
En la profundización iterativa establece un valor de un nivel, si no hay solución en ese nivel, incrementa ese valor y comienza de nuevo desde cero (la raíz).
¿No sería esto lo mismo que una búsqueda en profundidad?
Quiero decir que seguirías incrementando e incrementando, profundizando hasta encontrar una solución. ¡Veo esto como lo mismo! Bajaría por la misma bifurcación, porque si vuelvo a empezar desde cero iría por la misma bifurcación que antes.
En una búsqueda en profundidad, comienza en algún nodo del gráfico y explora cada vez más y más profundamente en el gráfico, mientras que 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 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 recorrido 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 el que toma 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 por la que esto es 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 ramificació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 breve:
- No se garantiza que DFS encuentre una ruta óptima; la profundización iterativa es.
- DFS puede explorar todo el gráfico antes de encontrar el nodo objetivo; 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 se ejecutan en O (b d ), pero la profundización iterativa tiene un factor constante más alto.
- BFS usa memoria O (b d ), mientras que la profundización iterativa usa solo O (d).
¡Espero que esto ayude!
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ística . Cuando es probable que se encuentre una solución cerca de la raíz, la profundización iterativa la encontrará relativamente rápido, mientras que la búsqueda directa en profundidad recta podría tomar una decisión "incorrecta" y pasar mucho tiempo en una rama profunda sin resultados.
(Esto es particularmente importante cuando el árbol de búsqueda puede ser infinito. En este caso, son incluso menos equivalentes ya que el DFS puede quedarse atascado para siempre mientras que BFS o la profundización iterativa seguramente encontrarán la respuesta un día si existe)
Solo agregué lo que ya está aquí, pero aquí hay algunos videos del Moving AI Lab de la Universidad de Denver que muestran las diferencias.
En sus ejemplos, puede ver triunfos iterativos cuando el objetivo es poco profundo (profundidad de la solución 3, profundidad del árbol) y la solución está a la derecha, pero DFS gana sin importar si la solución está en la última fila.
Entré en esta lectura sobre la programación de ajedrez, el siguiente para mí fue pensar en la búsqueda de quiescencia, verificar si quieres saber más sobre las estrategias de búsqueda para la programación de IA.