Búsqueda en profundidad iterativa

En informática , la búsqueda iterativa en profundidad o, más específicamente, la búsqueda iterativa en profundidad ^{[ 1 ]} (IDS o IDDFS) es una estrategia de búsqueda en espacio de estados /grafo en la que se ejecuta repetidamente una versión con profundidad limitada de la búsqueda en profundidad con límites de profundidad crecientes hasta que se encuentra el objetivo. IDDFS es óptima, lo que significa que encuentra el objetivo menos profundo. ^{[ 2 ]} Dado que visita todos los nodos en el árbol de búsqueda hasta la profundidad${\displaystyle d}$antes de visitar cualquier nodo en profundidad${\displaystyle d+1}$El orden acumulativo en el que se visitan los nodos por primera vez es prácticamente el mismo que en la búsqueda en anchura . Sin embargo, IDDFS utiliza mucha menos memoria. ^{[ 1 ]}

El siguiente pseudocódigo muestra la implementación de IDDFS en términos de un DFS recursivo con limitación de profundidad (denominado DLS) para grafos dirigidos . Esta implementación de IDDFS no tiene en cuenta los nodos ya visitados.

La función IDDFS(root) es para profundidad de 0 a ∞ . encontrado, restante ← DLS(raíz, profundidad) Si encontrado ≠ null, entonces devuelve encontrado; de lo contrario, si no queda ninguno, entonces devuelve null.La función DLS(nodo, profundidad) es: si profundidad = 0 , entonces si nodo es un objetivo , entonces devuelve (nodo, verdadero ) ; de lo contrario, devuelve ( null , verdadero ). (No encontrado, pero puede tener hijos).else if depth > 0 then any_remaining ← false foreach child of node do encontrado, restante ← DLS(hijo, profundidad−1) Si found ≠ null, entonces devuelve (found, true ). Si remaining, entonces any_remaining ← true (Se encontró al menos un nodo en la profundidad, deja que IDDFS profundice). Devuelve ( null , any_remaining).

Si DLS encuentra el nodo objetivo , IDDFS lo devolverá sin profundizar más. De lo contrario, si existe al menos un nodo en ese nivel de profundidad, el indicador restante permitirá que IDDFS continúe.

Las tuplas de 2 elementos son útiles como valor de retorno para indicar a IDDFS que continúe profundizando o se detenga, en caso de que la profundidad del árbol y la pertenencia al objetivo se desconozcan a priori . Otra solución podría utilizar valores centinela para representar los resultados de niveles no encontrados o restantes .

IDDFS logra la completitud de la búsqueda en amplitud (cuando el factor de ramificación es finito) utilizando la eficiencia espacial de la búsqueda en profundidad. Si existe una solución, encontrará una ruta de solución con el menor número de arcos. ^{[ 2 ]}

La profundización iterativa visita los estados varias veces y puede parecer un desperdicio. Sin embargo, si IDDFS explora un árbol de búsqueda hasta la profundidad${\displaystyle d}$La mayor parte del esfuerzo total se centra en explorar los estados en profundidad.${\displaystyle d}$. En relación con el número de estados en profundidad${\displaystyle d}$, el costo de visitar repetidamente los estados por encima de esta profundidad siempre es pequeño. ^{[ 3 ]}

La principal ventaja de IDDFS en la búsqueda de árboles de juego es que las búsquedas iniciales tienden a mejorar las heurísticas comúnmente utilizadas, como la heurística del asesino y la poda alfa-beta , de modo que se puede obtener una estimación más precisa de la puntuación de los distintos nodos en la búsqueda de profundidad final, y la búsqueda se completa más rápidamente al realizarse en un mejor orden. Por ejemplo, la poda alfa-beta es más eficiente si busca primero los mejores movimientos. ^{[ 3 ]}

Una segunda ventaja es la capacidad de respuesta del algoritmo. Debido a que las primeras iteraciones utilizan valores pequeños para${\displaystyle d}$, se ejecutan con extrema rapidez. Esto permite que el algoritmo proporcione indicaciones tempranas del resultado casi de inmediato, seguidas de refinamientos a medida que${\displaystyle d}$aumenta. Cuando se utiliza en un entorno interactivo, como en un programa de ajedrez , esta función permite que el programa juegue en cualquier momento con el mejor movimiento actual encontrado en la búsqueda realizada hasta el momento. Esto se puede expresar como que cada nivel de profundidad de la búsqueda produce recursivamente una mejor aproximación de la solución, aunque el trabajo realizado en cada paso sea recursivo. Esto no es posible con una búsqueda en profundidad tradicional, que no produce resultados intermedios.

Para el siguiente gráfico:

Una búsqueda en profundidad que comienza en A, asumiendo que las aristas izquierdas en el grafo mostrado se eligen antes que las derechas, y asumiendo que la búsqueda recuerda los nodos visitados previamente y no los repetirá (ya que este es un grafo pequeño), visitará los nodos en el siguiente orden: A, B, D, F, E, C, G. Las aristas recorridas en esta búsqueda forman un árbol de Trémaux , una estructura con importantes aplicaciones en la teoría de grafos .

Realizar la misma búsqueda sin recordar los nodos visitados previamente da como resultado visitar nodos en el orden A, B, D, F, E, A, B, D, F, E, etc. para siempre, atrapado en el ciclo A, B, D, F, E y sin llegar nunca a C o G.

La profundización iterativa evita este bucle y alcanzará los siguientes nodos en las siguientes profundidades, suponiendo que procede de izquierda a derecha como se indicó anteriormente:

• Profundidad 0: A
• Profundidad 1: A, B, C, E

(La búsqueda iterativa en profundidad ha dado con la clasificación C, mientras que la búsqueda convencional en profundidad no lo ha hecho).

• Profundidad 2: A, B, D, F, C, G, E, F

(Sigue viendo C, pero que llegó más tarde. Además, ve E a través de una ruta diferente y vuelve a F dos veces).

• Profundidad 3: A, B, D, F, E, C, G, E, F, B

En este gráfico, a medida que se añade más profundidad, los dos ciclos "ABFE" y "AEFB" simplemente se irán alargando antes de que el algoritmo se rinda e intente otra rama.

Similar a la búsqueda en profundidad iterativa, existe una estrategia de búsqueda llamada búsqueda en longitud iterativa que trabaja con límites de costo de ruta crecientes en lugar de límites de profundidad. Expande los nodos en orden de costo de ruta creciente; por lo tanto, el primer objetivo que encuentra es el que tiene el costo de ruta más bajo. Sin embargo, la búsqueda en longitud iterativa genera una sobrecarga considerable que la hace menos útil que la búsqueda en profundidad iterativa. ^{[ 3 ]}

El A* de profundización iterativa es una búsqueda primero en amplitud que realiza una profundización iterativa basada en valores " f " similares a los calculados en el algoritmo A* .

IDDFS bidireccional

IDDFS tiene una contraparte bidireccional, ^{[ 1 ] : 6} que alterna dos búsquedas: una que comienza desde el nodo de origen y se mueve a lo largo de los arcos dirigidos, y otra que comienza desde el nodo de destino y procede a lo largo de los arcos dirigidos en dirección opuesta (desde el nodo de cabeza del arco hasta el nodo de cola del arco). El proceso de búsqueda primero verifica que el nodo de origen y el nodo de destino sean iguales, y si es así, devuelve la ruta trivial que consiste en un solo nodo de origen/destino. De lo contrario, el proceso de búsqueda hacia adelante expande los nodos hijos del nodo de origen (conjunto${\displaystyle A}$), el proceso de búsqueda hacia atrás expande los nodos padres del nodo objetivo (conjunto${\displaystyle B}$), y se comprueba si${\displaystyle A}$y${\displaystyle B}$Se produce una intersección. Si es así, se encuentra el camino más corto. De lo contrario, se incrementa la profundidad de búsqueda y se realiza el mismo cálculo.

Una limitación del algoritmo es que el camino más corto que consta de un número impar de arcos no será detectado. Supongamos que tenemos un camino más corto${\displaystyle \langle s,u,v,t\rangle .}$Cuando la profundidad alcance dos saltos a lo largo de los arcos, la búsqueda hacia adelante procederá desde${\displaystyle u}$a${\displaystyle v}$y la búsqueda hacia atrás procederá desde${\displaystyle v}$a${\displaystyle u}$Gráficamente, las fronteras de búsqueda se cruzarán, y en su lugar se devolverá una ruta subóptima compuesta por un número par de arcos. Esto se ilustra en los diagramas siguientes:

En lo que respecta a la complejidad espacial, el algoritmo colorea los nodos más profundos en el proceso de búsqueda hacia adelante para detectar la existencia del nodo intermedio donde se encuentran los dos procesos de búsqueda.

La dificultad adicional de aplicar IDDFS bidireccional es que si los nodos de origen y destino están en componentes fuertemente conectados diferentes, por ejemplo,${\displaystyle s\in S,t\in T}$, si no hay ningún arco que salga${\displaystyle S}$y entrando${\displaystyle T}$La búsqueda nunca terminará.

Complejidades de tiempo y espacio

El tiempo de ejecución de IDDFS bidireccional viene dado por

${\displaystyle 2\sum _{k=0}^{n/2}b^{k}}$

y la complejidad espacial viene dada por

${\displaystyle b^{n/2},}$

dónde${\displaystyle n}$es el número de nodos en el más corto${\displaystyle s,t}$-ruta. Dado que la complejidad temporal de ejecución de la búsqueda en profundidad iterativa es${\displaystyle \sum _{k=0}^{n}b^{k}}$, la aceleración es aproximadamente

${\displaystyle {\frac {\sum _{k=0}^{n}b^{k}}{2\sum _{k=0}^{n/2}b^{k}}}={\frac {\frac {1-b^{n+1}}{1-b}}{2{\frac {1-b^{n/2+1}}{1-b}}}}={\frac {1-b^{n+1}}{2(1-b^{n/2+1})}}={\frac {b^{n+1}-1}{2(b^{n/2+1}-1)}}\approx {\frac {b^{n+1}}{2b^{n/2+1}}}=\Theta (b^{n/2}).}$

Pseudocódigo

La función Find-Shortest-Path(s, t) es si s = t entonces devuelve < s > (B, F, V f , V b ) := (pila vacía, ∅ , ∅ , ∅ ) ( Δ , l f , l b ) := (0, 0, 0) para siempre hacer (F, V f ) := ( ∅ , ∅ ) Búsqueda-hacia-adelante-con-profundidad-limitada(s, Δ , F, V f ) si |V f | = l f entonces devolver nil (l f , V b ) := (|V f |, ∅ ) μ := Búsqueda-hacia-atrás-con-profundidad-limitada(t, Δ , B, F, V b ) si μ${\displaystyle \neq }$nil entonces devolver Build-Path(s, μ , B, G) V b := ∅ μ := Búsqueda-hacia-atrás-con-profundidad-limitada(t, Δ + 1, B, F, V b ) si μ${\displaystyle \neq }$nil luego devuelve Build-Path(s, μ , B, G) si |B b | = l b luego devuelve nil (l b , Δ ) := (|V b |, Δ + 1)

La función Build-Path(s, μ , B) es π := Find-Shortest-Path(s, μ ) (Calcula recursivamente la ruta al nodo de retransmisión) Pop(B) devolver π${\displaystyle \circ }$B (Añade los elementos a la pila comenzando desde la parte superior).

La función Búsqueda-Limitada-en-Profundidad-Hacia-Adelante(u, Δ , F, V) es si u ∈ V entonces devolver V := V ∪ {u} si Δ = 0 entonces F := F ∪ {u} (Marcar u como un nodo frontera.) devolver para cada hijo de u hacer Búsqueda-Limitada-en-Profundidad-Hacia-Adelante(hijo, Δ − 1, F, V)

La función Búsqueda-Retroceso-Limitada-EnProfundidad(u, Δ , B, F, V) es si u ∈ V entonces devuelve nil Empujar(B, u) Si Δ = 0 , entonces si u ∈ F , entonces devolver u (Se ha alcanzado el nodo marcado, utilizarlo como nodo de retransmisión). Pop(B) return nil V := V ∪ {u} para cada padre de u hacer μ := Búsqueda-Retroceso-Limitada-EnProfundidad(padre, Δ − 1, B, F, V) si μ${\displaystyle \neq }$Si es nulo, entonces devuelve μ. Pop(B) devolver cero