search - inteligencia - busqueda profundidad iterativa java
Diferencia entre la primera búsqueda de amplitud y la profundización iterativa (4)
De lo que entiendo, la profundización iterativa hace el DFS hasta la profundidad 1, luego el DFS hasta la profundidad del 2 ... hasta la profundidad n, y así sucesivamente hasta que no encuentra más niveles
por ejemplo creo que se leería ese árbol
read visited depth
A A 1
ABC ABAC 2
ABDCEF ABDBACECF 3
Creo que es prácticamente hacer un DFS separado con un límite de profundidad para cada nivel y tirar la memoria.
Entiendo BFS y DFS, pero por mi vida no puedo entender la diferencia entre la profundización iterativa y BFS. 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 genial.
árbol para trabajar si es necesario:
A
/ /
B C
/ / /
D E F
Desde mi entendimiento del algoritmo, IDDFS (búsqueda en profundidad de profundidad iterativa) es simplemente una búsqueda en 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 para la búsqueda en profundidad, ya que la iteración máxima de profundidad es solo la búsqueda en profundidad.
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 de esta manera es que, si la búsqueda tiene una restricción de tiempo, entonces el algoritmo tendrá al menos una idea de lo que es un nodo de "buena puntuación" si alcanza el límite de tiempo antes de hacer un recorrido completo de el árbol.
Esto es diferente a una búsqueda de amplitud en primer lugar porque en cada iteración, los nodos se visitan de la misma manera que lo harían en una búsqueda en profundidad, no como en una búsqueda de amplitud en primer lugar. Normalmente, los algoritmos IDDFS probablemente almacenarían el nodo "mejor puntuación" encontrado en cada iteración.
En cada iteración de la búsqueda de profundización iterativa, tenemos un límite y recorremos la gráfica utilizando el enfoque DFS; sin embargo, para cada paso de cada iteración, solo necesitamos realizar un seguimiento de los nodos dentro de la ruta desde la raíz hasta la profundidad d . Ese es el ahorro en la memoria.
Por ejemplo, mira la última fila de la imagen de abajo. Si hemos usado BFS, tuvimos que hacer un seguimiento de todos los nodos hasta la profundidad 2. Pero debido a que estamos usando DFS, no necesitamos mantenerlos en la memoria ya que algunos nodos ya están visitados, por lo que no lo hacemos. Necesítalos o no los has visitado aún, así que lo agregaremos más tarde. Simplemente mantenemos nuestro camino hacia la raíz (el camino gris).
La imagen es del libro de Inteligencia Artificial de Peter Norvig y Stuart Russel
el uso de la memoria es el número máximo de nodos que guarda en cualquier punto. No es el número de nodos visitados.
En cualquier momento, IDFS necesita almacenar solo los nodos en la rama en la que se está expandiendo. Sólo la A y la C si estamos expandiendo la C (en su ejemplo). BFS debe guardar todos los nodos de la profundidad que está buscando. para ver el efecto, tome un árbol con factor de ramificación 8 en lugar de 2. para buscar a una profundidad de 3, BFS necesita almacenar 64 nodos masivos. IDFS sólo necesita 3.