Búsqueda en profundidad iterativa y de profundización

Estrategia de búsqueda

En informática , la búsqueda iterativa de profundización o, más específicamente, la búsqueda iterativa de profundización en profundidad ^[1] (IDS o IDDFS) es una estrategia de búsqueda en el espacio de estados /grafo en la que se ejecuta repetidamente una versión limitada en profundidad 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 más superficial. ^[2] Dado que visita todos los nodos en el árbol de búsqueda hasta la profundidad antes de visitar cualquier nodo en profundidad , el orden acumulativo en el que se visitan los nodos por primera vez es efectivamente el mismo que en la búsqueda en amplitud . Sin embargo, IDDFS usa mucha menos memoria. ^[1] ${\displaystyle d}$ ${\displaystyle d+1}$

Algoritmo para grafos dirigidos

El siguiente pseudocódigo muestra el IDDFS implementado en términos de un DFS recursivo de profundidad limitada (llamado DLS) para gráficos dirigidos . Esta implementación del 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 se encuentra ≠ nulo  , entonces  se devuelve encontrado ; de lo contrario, si no queda nada ,  se devuelve  nulo.La función DLS(nodo, profundidad) es  si profundidad = 0 entonces  si el nodo es un objetivo entonces  retorna (nodo, verdadero ) de lo contrario  retorna ( nulo , verdadero ) (No encontrado, pero puede tener hijos) de lo contrario, si profundidad > 0 entonces any_remaining ← falso  para cada hijo del nodo hacer encontrado, restante ← DLS(hijo, profundidad−1) si se encuentra ≠ nulo entonces  retorna (encontrado, verdadero ) si queda entonces cualquier_restante ← verdadero (al menos un nodo encontrado en profundidad, deje que IDDFS profundice)  retorna ( nulo , cualquier_restante)

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

Las tuplas de 2 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 a la meta sean desconocidas a priori . Otra solución podría utilizar valores centinela en su lugar para representar resultados no encontrados o de nivel restante .

Propiedades

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 la menor cantidad 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 , la mayor parte del esfuerzo total se destina a explorar los estados en profundidad . En relación con la cantidad de estados en profundidad , el costo de visitar repetidamente los estados por encima de esta profundidad siempre es pequeño. ^[3] ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$

La principal ventaja de IDDFS en la búsqueda de árboles de juego es que las búsquedas más tempranas tienden a mejorar las heurísticas comúnmente utilizadas, como la heurística asesina y la poda alfa-beta , de modo que se puede producir una estimación más precisa de la puntuación de varios nodos en la búsqueda de profundidad final, y la búsqueda se completa más rápidamente ya que se realiza 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 iteraciones tempranas utilizan valores pequeños para , se ejecutan extremadamente rápido. Esto permite que el algoritmo proporcione indicaciones tempranas del resultado casi inmediatamente, seguidas de refinamientos a medida que 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 que ha completado hasta ahora. Esto se puede expresar como que cada profundidad de la búsqueda produce recursivamente una mejor aproximación a la solución, aunque el trabajo realizado en cada paso es recursivo. Esto no es posible con una búsqueda tradicional en profundidad, que no produce resultados intermedios. ${\displaystyle d}$ ${\displaystyle d}$

Análisis asintótico

Complejidad temporal

La complejidad temporal de IDDFS en un árbol (bien equilibrado) resulta ser la misma que la de la búsqueda en amplitud, es decir , ^{[1] : 5} donde es el factor de ramificación y es la profundidad del objetivo. ${\displaystyle O(b^{d})}$ ${\displaystyle b}$ ${\displaystyle d}$

Prueba

En una búsqueda de profundización iterativa, los nodos en profundidad se expanden una vez, los que están en profundidad se expanden dos veces, y así sucesivamente hasta la raíz del árbol de búsqueda, que se expande veces. ^{[1] : 5} Por lo tanto, el número total de expansiones en una búsqueda de profundización iterativa es ${\displaystyle d}$ ${\displaystyle d-1}$ ${\displaystyle d+1}$

${\displaystyle b^{d}+2b^{d-1}+3b^{d-2}+\cdots +(d-1)b^{2}+db+(d+1)=\sum _{i=0}^{d}(d+1-i)b^{i}}$

donde es el número de expansiones en profundidad , es el número de expansiones en profundidad , y así sucesivamente. Al factorizar obtenemos ${\displaystyle b^{d}}$ ${\displaystyle d}$ ${\displaystyle 2b^{d-1}}$ ${\displaystyle d-1}$ ${\displaystyle b^{d}}$

${\displaystyle b^{d}(1+2b^{-1}+3b^{-2}+\cdots +(d-1)b^{2-d}+db^{1-d}+(d+1)b^{-d})}$

Ahora dejemos . Entonces tenemos ${\displaystyle x={\frac {1}{b}}=b^{-1}}$

${\displaystyle b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})}$

Esto es menor que la serie infinita.

${\displaystyle b^{d}(1+2x+3x^{2}+4x^{3}+\cdots )=b^{d}\left(\sum _{n=1}^{\infty }nx^{n-1}\right)}$

que converge a

${\displaystyle b^{d}(1-x)^{-2}=b^{d}{\frac {1}{(1-x)^{2}}}}$, para ${\displaystyle abs(x)<1}$

Es decir, tenemos

${\displaystyle b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})\leq b^{d}(1-x)^{-2}}$, para ${\displaystyle abs(x)<1}$

Dado que o es una constante independiente de (la profundidad), si (es decir, si el factor de ramificación es mayor que 1), el tiempo de ejecución de la búsqueda de profundización iterativa en profundidad es . ${\displaystyle (1-x)^{-2}}$ ${\displaystyle \left(1-{\frac {1}{b}}\right)^{-2}}$ ${\displaystyle d}$ ${\displaystyle b>1}$ ${\displaystyle O(b^{d})}$

Ejemplo

Para y el numero es ${\displaystyle b=10}$ ${\displaystyle d=5}$

${\displaystyle \sum _{i=0}^{5}(5+1-i)10^{i}=6+50+400+3000+20000+100000=123456}$

En conjunto, una búsqueda iterativa de profundización desde la profundidad hasta la profundidad se expande solo alrededor de más nodos que una única búsqueda en amplitud o limitada en profundidad hasta la profundidad , cuando . ^[4] ${\displaystyle 1}$ ${\displaystyle d}$ ${\displaystyle 11\%}$ ${\displaystyle d}$ ${\displaystyle b=10}$

Cuanto mayor sea el factor de ramificación, menor será la sobrecarga de los estados expandidos repetidamente, ^{[1] : 6} pero incluso cuando el factor de ramificación es 2, la búsqueda de profundización iterativa solo toma aproximadamente el doble de tiempo que una búsqueda completa en amplitud. Esto significa que la complejidad temporal de la profundización iterativa sigue siendo . ${\displaystyle O(b^{d})}$

Complejidad espacial

La complejidad espacial de IDDFS es , ^{[1] : 5} donde es la profundidad del objetivo. ${\displaystyle O(d)}$ ${\displaystyle d}$

Prueba

Dado que IDDFS, en cualquier punto, realiza una búsqueda en profundidad, solo necesita almacenar una pila de nodos que representa la rama del árbol que está expandiendo. Dado que encuentra una solución de longitud óptima, la profundidad máxima de esta pila es y, por lo tanto, la cantidad máxima de espacio es . ${\displaystyle d}$ ${\displaystyle O(d)}$

En general, la profundización iterativa es el método de búsqueda preferido cuando hay un espacio de búsqueda grande y no se conoce la profundidad de la solución. ^[3]

Ejemplo

Para el siguiente gráfico:

una búsqueda en profundidad que comienza en A, asumiendo que los bordes izquierdos en el gráfico mostrado se eligen antes que los bordes derechos, y asumiendo que la búsqueda recuerda los nodos visitados previamente y no los repetirá (ya que este es un gráfico pequeño), visitará los nodos en el siguiente orden: A, B, D, F, E, C, G. Los bordes recorridos en esta búsqueda forman un árbol 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. eternamente, atrapados en el ciclo A, B, D, F, E y nunca llegando 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 indica anteriormente:

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

(La profundización iterativa ahora ha permitido alcanzar C, mientras que una búsqueda en profundidad convencional no lo hizo).

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

(Aún ve C, pero llegó más tarde. También ve E a través de un camino diferente y vuelve a F dos veces.)

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

Para este gráfico, a medida que se agrega más profundidad, los dos ciclos "ABFE" y "AEFB" simplemente se harán más largos antes de que el algoritmo se dé por vencido y pruebe otra rama.

Algoritmos relacionados

Una estrategia de búsqueda similar a la profundización iterativa es la llamada búsqueda de alargamiento iterativo, que funciona con límites de costo de ruta crecientes en lugar de límites de profundidad. Expande los nodos en el 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. Pero el alargamiento iterativo implica una sobrecarga sustancial que lo hace menos útil que la profundización iterativa. ^[3]

Profundización iterativa A* es una búsqueda de mejor primero 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 avanza 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 secundarios del nodo de origen (conjunto ), el proceso de búsqueda hacia atrás expande los nodos principales del nodo de destino (conjunto ) y se verifica si y se cruzan. Si es así, se encuentra una ruta más corta. De lo contrario, se incrementa la profundidad de búsqueda y se lleva a cabo el mismo cálculo. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

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

IDDFS bidireccional

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.

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

Complejidades de tiempo y espacio

El tiempo de ejecución del 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},}$

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

${\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 Build-Path(s, μ, B) es π ← Find-Shortest-Path(s, μ) (calcula recursivamente la ruta al nodo de retransmisión) eliminar el último nodo de π devuelve π B (Agrega la pila de búsqueda hacia atrás) ${\displaystyle \circ }$

función Búsqueda-de-Profundidad-Limitada-Adelante(u, Δ, F) es  si Δ = 0 entonces F ← F {u} (Marca el nodo) retorna para cada hijo de u ${\displaystyle \cup }$   Búsqueda avanzada con limitación de profundidad (hijo, Δ − 1, F)

La función Búsqueda limitada en profundidad hacia atrás (u, Δ, B, F) es anteponer u a B si Δ = 0 entonces  si u está en F entonces  devuelve u (Llegó al nodo marcado, úselo como nodo de retransmisión) Quitar el nodo de cabeza de B devuelve nulo  para cada padre de u μ ← Búsqueda de profundidad limitada hacia atrás (padre, Δ − 1, B, F) Si μ es nulo , entonces devuelve μ ${\displaystyle \neq }$    Quitar el nodo de cabeza de B devuelve nulo

La función Find-Shortest-Path(s, t) es  si s = t entonces  devuelve <s> F, B, Δ ← ∅, ∅, 0 por siempre hacer Búsqueda de profundidad limitada hacia adelante (s, Δ, F) para cada δ = Δ, Δ + 1 hacer μ ← Búsqueda con profundidad limitada hacia atrás (t, δ, B, F) Si μ es nulo, entonces devuelve Build-Path(s, μ, B) (se encontró un nodo de retransmisión) ${\displaystyle \neq }$   F, Δ ← ∅, Δ + 1

Referencias

1. Korf, Richard (1985). "Profundización iterativa en profundidad: una búsqueda de árbol admisible óptima". Inteligencia artificial . 27 : 97–109. doi :10.1016/0004-3702(85)90084-0. S2CID  10956233.
2. David Poole; Alan Mackworth. "3.5.3 Profundización iterativa ‣ Capítulo 3 Búsqueda de soluciones ‣ Inteligencia artificial: Fundamentos de los agentes computacionales, 2.ª edición". artint.info . Consultado el 29 de noviembre de 2018 .
3. Russell, Stuart J. ; Norvig, Peter (2003), Inteligencia artificial: un enfoque moderno (2.ª ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, ISBN 0-13-790395-2
4. Russell; Norvig (1994). Inteligencia artificial: un enfoque moderno .