En informática , la búsqueda iterativa de profundización o, más específicamente, la búsqueda iterativa de profundización primero en profundidad [2] (IDS o IDDFS) es una estrategia de búsqueda de espacio / gráfico de estado en la que una versión de profundidad limitada de la búsqueda en profundidad primero se ejecuta repetidamente con una profundidad creciente límites hasta encontrar la meta. IDDFS es óptimo como la búsqueda en amplitud , pero usa mucha menos memoria; en cada iteración, visita los nodos en el árbol de búsqueda en el mismo orden que la búsqueda en profundidad, pero el orden acumulativo en el que los nodos se visitan por primera vez es efectivamente en amplitud. [1]
Clase | Algoritmo de búsqueda |
---|---|
Estructura de datos | Árbol , Gráfico |
Rendimiento en el peor de los casos | , dónde es el factor de ramificación y es la profundidad de la solución más superficial |
Complejidad espacial en el peor de los casos | [1] : 5 |
Algoritmo para gráficos dirigidos
El siguiente pseudocódigo muestra IDDFS implementado en términos de un DFS recursivo limitado en profundidad (llamado DLS) para gráficos dirigidos . Esta implementación de IDDFS no tiene en cuenta los nodos ya visitados y, por lo tanto, no funciona para gráficos no dirigidos .
la función IDDFS (raíz) es para la profundidad de 0 a ∞ do encontrado, restante ← DLS (raíz, profundidad) si se encuentra ≠ nulo , devuelve encontrado; de lo contrario, si no queda , devuelve nulola función DLS (nodo, profundidad) es si profundidad = 0, entonces si el nodo es un objetivo, entonces devuelve (nodo, verdadero ) de lo contrario, devuelve ( nulo , verdadero ) (No encontrado, pero puede tener hijos) else if profundidad> 0 entonces any_remaining ← falsa foreach hijo del nodo de tareas pendientes encontrado, restante ← DLS (hijo, profundidad − 1) si se encuentra ≠ nulo entonces devuelve (encontrado, verdadero ) si queda entonces any_remaining ← verdadero (Al menos un nodo encontrado en profundidad, deje que IDDFS profundice) retorno ( nulo , any_remaining)
Si se encuentra el nodo objetivo, DLS desenrolla la recursividad que regresa sin más iteraciones. De lo contrario, si existe al menos un nodo a ese nivel de profundidad, la bandera restante permitirá que IDDFS continúe.
Las 2 tuplas 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 membresía del objetivo sean desconocidas a priori . Otra solución podría utilizar valores centinela en su lugar para representar los resultados de nivel no encontrado o restante .
Propiedades
IDDFS combina la eficiencia espacial de la búsqueda en profundidad y la integridad de la búsqueda en amplitud (cuando el factor de ramificación es finito). Si existe una solución, encontrará una ruta de solución con la menor cantidad de arcos. [3]
Dado que las visitas de profundización iterativas indican varias veces, puede parecer un desperdicio, pero resulta no ser tan costoso, ya que en un árbol la mayoría de los nodos están en el nivel inferior, por lo que no importa mucho si los niveles superiores se visitan varias veces. veces. [4]
La principal ventaja de IDDFS en la búsqueda del árbol del juego es que las búsquedas anteriores tienden a mejorar las heurísticas comúnmente utilizadas, como la heurística asesina y la poda alfa-beta , de modo que una estimación más precisa de la puntuación de varios nodos en la búsqueda en profundidad final puede ocurrir, 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 eficaz si busca primero los mejores movimientos. [4]
Una segunda ventaja es la capacidad de respuesta del algoritmo. Debido a que las primeras iteraciones usan valores pequeños para, se ejecutan extremadamente rápido. Esto permite que el algoritmo proporcione indicaciones tempranas del resultado casi de inmediato, seguidas de refinamientos comoaumenta. Cuando se utiliza en un entorno interactivo, como en un programa de juego 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 el momento. Esto se puede expresar como cada profundidad de la búsqueda co recursiva producir una mejor aproximación de 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.
Análisis asintótico
Complejidad del tiempo
La complejidad temporal de IDDFS en un árbol (bien equilibrado) resulta ser la misma que la búsqueda en amplitud, es decir, [1] : 5 donde es el factor de ramificación y es la profundidad de la meta.
Prueba
En una búsqueda iterativa de profundización, los nodos en profundidad se expanden una vez, los de profundidad se expanden dos veces, y así sucesivamente hasta la raíz del árbol de búsqueda, que se expande veces. [1] : 5 Entonces, el número total de expansiones en una búsqueda iterativa de profundización es
dónde es el número de expansiones en profundidad , es el número de expansiones en profundidad , y así. Factorizar da
Ahora deja . Entonces nosotros tenemos
Esto es menos que la serie infinita.
que converge a
- , por
Es decir, tenemos
, por
Desde 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 primero en profundidad es .
Ejemplo
Para y El numero es
Todos juntos, una búsqueda iterativa cada vez más profunda todo el camino hasta la profundidad se expande solo sobre más nodos que una única búsqueda de profundidad limitada en profundidad o en amplitud , Cuándo . [5]
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 iterativa de profundización solo toma aproximadamente el doble de tiempo que una búsqueda completa primero en amplitud. Esto significa que la complejidad temporal de la profundización iterativa sigue siendo.
Complejidad espacial
La complejidad espacial de IDDFS es, [1] : 5 donde es la profundidad de la meta.
Prueba
Dado que IDDFS, en cualquier punto, está involucrado en una búsqueda en profundidad, solo necesita almacenar una pila de nodos que representa la rama del árbol que se 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 .
En general, la profundización iterativa es el método de búsqueda preferido cuando hay un gran espacio de búsqueda y se desconoce la profundidad de la solución. [4]
Ejemplo
Para el siguiente gráfico:
una búsqueda en profundidad que comienza en A, suponiendo 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 anteriormente y no los repetirá (ya que este es un gráfico pequeño), visitará el nodos en el siguiente orden: A, B, D, F, E, C, G. Las aristas atravesadas 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 anteriormente da como resultado la visita de nodos en el orden A, B, D, F, E, A, B, D, F, E, etc. para siempre, atrapados en A, B, D, F , Ciclo E y nunca llegar a C o G.
La profundización iterativa evita este bucle y llegará a los siguientes nodos en las siguientes profundidades, suponiendo que proceda de izquierda a derecha como se indicó anteriormente:
- 0: A
- 1: A, B, C, E
(La profundización iterativa ahora ha visto a C, cuando una búsqueda convencional en profundidad primero no lo hizo).
- 2: A, B, D, F, C, G, E, F
(Todavía ve a C, pero llegó más tarde. También ve a E por 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 alargarán antes de que el algoritmo se rinda e intente otra rama.
Algoritmos relacionados
Similar a la profundización iterativa es una estrategia de búsqueda 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 aumentar el costo de la ruta; por lo tanto, el primer objetivo que encuentra es el que tiene el costo de ruta más barato. Pero el alargamiento iterativo incurre en una sobrecarga sustancial que lo hace menos útil que la profundización iterativa. [4]
La profundización iterativa A * es una búsqueda del 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 en el nodo de origen y se mueve a lo largo de los arcos dirigidos, y otra que comienza en el nodo de destino y avanza a lo largo de los arcos dirigidos en dirección opuesta (desde el arco nodo de cabeza al 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, de ser así, devuelve la ruta trivial que consta de 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 comprueba si y intersecarse. Si es así, se encuentra un 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 no se detectará la ruta más corta que consta de un número impar de arcos. Supongamos que tenemos un camino más corto Cuando la profundidad alcance dos saltos a lo largo de los arcos, la búsqueda hacia adelante procederá a de , y la búsqueda hacia atrás procederá de a . Gráficamente, las fronteras de búsqueda se cruzará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 siguientes diagramas:
En lo que respecta a la complejidad del espacio, el algoritmo colorea los nodos más profundos en el proceso de búsqueda hacia adelante para detectar la existencia del nodo medio donde se encuentran los dos procesos de búsqueda.
La dificultad adicional de aplicar IDDFS bidireccional es que si los nodos de origen y de destino están en diferentes componentes fuertemente conectados, digamos, , si no hay arco saliendo y entrando , la búsqueda nunca terminará.
Complejidades temporales y espaciales
El tiempo de ejecución de IDDFS bidireccional viene dado por
y la complejidad del espacio viene dada por
dónde es el número de nodos en el más corto -camino. Dado que la complejidad del tiempo de ejecución de la búsqueda iterativa de profundización primero en profundidad es, la aceleración es aproximadamente
Pseudocódigo
La función Build-Path (s, μ, B) es π ← Find-Shortest-Path (s, μ) (Calcular recursivamente la ruta al nodo de retransmisión) eliminar el último nodo de π volver πB (Agregar la pila de búsqueda hacia atrás)
función Profundidad-Búsqueda-limitada-hacia adelante (u, Δ, F) es si Δ = 0 entonces F ← F{u} (marca el nodo) de retorno foreach niño de T hacen Búsqueda de profundidad limitada hacia adelante (secundaria, Δ - 1, F)
La función Profundidad-Búsqueda-Limitada-Atrás (u, Δ, B, F) es anteponer u a B si Δ = 0 entonces si u en F entonces devuelve u (Alcanzó el nodo marcado, úselo como un nodo de retransmisión) quitar el nodo principal de B devolver null foreach matriz de T hacen μ ← Búsqueda limitada en profundidad hacia atrás (padre, Δ - 1, B, F) si μ nulo luego devuelve μ quitar el nodo principal de B devolver nulo
la función Find-Shortest-Path (s, t) es si s = t entonces devuelveF, B, Δ ← ∅, ∅, 0 por siempre hacer Búsqueda de profundidad limitada hacia adelante (s, Δ, F) foreach δ = Δ, Δ + 1 hacer μ ← Búsqueda limitada en profundidad hacia atrás (t, δ, B, F) si μ null luego devuelve Build-Path (s, μ, B) (Encontré un nodo de retransmisión) F, Δ ← ∅, Δ + 1
Referencias
- ↑ a b c d e f g KORF, Richard E. (1985). "Profundización iterativa en profundidad primero" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Korf, Richard (1985). "Profundidad primero iterativo-profundización: una búsqueda óptima de árbol admisible". Inteligencia artificial . 27 : 97-109. doi : 10.1016 / 0004-3702 (85) 90084-0 .
- ^ 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 .
- ^ a b c d Russell, Stuart J .; Norvig, Peter (2003), Inteligencia artificial: un enfoque moderno (2a ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, ISBN 0-13-790395-2
- ^ Russell; Norvig (1994). Inteligencia artificial: un enfoque moderno .