Diferencia entre la primera búsqueda de la amplitud y la profundización iterativa

Question

Entiendo BFS y DFS, pero por la vida de mí no puedo descubrir la diferencia entre la profundización iterativa y los BF. Aparentemente, la profundización iterativa tiene el mismo uso de memoria que DFS, pero no puedo ver cómo esto es posible, ya que sigue expandiéndose como BFS. Si alguien puede aclarar, eso sería increíble.

árbol para trabajar si es necesario:

    A
   / \
  B   C
 /   / \
D   E   F

Answer 1

Por lo que entiendo, la profundización iterativa se reduce a DFS hasta la profundidad 1 y luego DFS hasta la profundidad de 2 ... hasta la profundidad N, y así sucesivamente hasta que no encuentre más niveles

Por ejemplo, creo que se leería el árbol

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

Creo que está haciendo un DFS separado con límite de profundidad para cada nivel y tirar la memoria.

Answer 2

A partir de mi comprensión del algoritmo, los IDDF (búsqueda de profundidad de profundidad iterativa primero) es simplemente una búsqueda de profundidad realizada varias veces, profundizando el nivel de nodos buscados en cada iteración. Por lo tanto, los requisitos de memoria son los mismos que la búsqueda de profundidad primero porque la iteración de profundidad máxima es solo la búsqueda completa de profundidad primero.

Por lo tanto, para el ejemplo del árbol que dio, la primera iteración visitaría el nodo A, la segunda iteración visitaría los nodos A, B y C, y la tercera iteración visitaría todos los nodos del árbol.

La razón por la que se implementa así es para que, si la búsqueda tiene una restricción de tiempo, el algoritmo al menos tendrá una idea de lo que un nodo de "buen puntaje" es si llega al límite de tiempo antes de hacer un recorrido completo de el árbol.

Esto es diferente a una búsqueda de amplitud primero porque en cada iteración, los nodos se visitan al igual que estarían en una búsqueda en profundidad, no como en una búsqueda de amplitud. Por lo general, los algoritmos IDDFS probablemente almacenarían el nodo de "mejor puntuación" que se encuentra en cada iteración.

Answer 3

El uso de la memoria es el número máximo de nodos que ahorra en cualquier punto. No es el número de nodos visitados.

En cualquier momento, IDFS necesita almacenar solo los nodos en la rama que se está expandiendo. Solo el A y C si estamos expandiendo C (en su EG). BFS debe guardar todos los nodos de la profundidad que está buscando. Para ver el efecto, tome un árbol con el factor de ramificación 8 en lugar de 2. Para buscar en una profundidad de 3, BFS necesita almacenar 64 nodos masivos. Las IDFS solo necesitan 3.

Answer 4

En cada iteración de búsqueda de profundización iterativa, tenemos un límite y atravesamos el gráfico utilizando el enfoque DFS, sin embargo, para cada paso de cada iteración, solo necesitamos realizar un seguimiento de solo nodos dentro de la ruta desde la raíz hasta la profundidad D . Ese es el ahorro en la memoria.

Por ejemplo, mire la última fila de la imagen a continuación. Si hemos usado BFS, tuvimos que realizar un seguimiento de todos los nodos hasta la profundidad 2. Pero debido a que estamos usando DFS, no necesitamos mantenerlos todos en la memoria ya que algunos nodos ya están visitados, por lo que no lo hacemos. los necesita o no visitarlos, por lo que lo agregaremos más tarde. Simplemente mantenemos nuestro camino hacia la raíz (la ruta gris).

La imagen es del libro de inteligencia artificial de Peter Norvig y Stuart Russel