Búsqueda en profundidad iterativa

Una búsqueda en Profundidad Iterativa (BPI) es un algoritmo de búsqueda no informada utilizado para una estrategia de búsqueda en el espacio de estados en la que se realizan sucesivas búsquedas en profundidad limitada incrementando el límite de profundidad en cada iteración hasta alcanzar $d$ , la profundidad del estado objetivo de menor profundidad. BPI es equivalente a la búsqueda en anchura, pero usa mucha menos memoria; en cada iteración, visita los nodos del árbol de búsqueda en el mismo orden que una búsqueda en profundidad, pero el orden en el que los nodos son visitados finalmente se corresponde con la búsqueda en anchura.

Propiedades

BPI combina la eficiencia del espacio de estados de la búsqueda en profundidad y la completitud de la búsqueda en anchura (cuando el factor de ramificación es finito). Es óptima cuando el costo del camino es una función no decreciente de la profundidad del nodo.

La complejidad en espacio de la BPI es $O(bd)$ , donde $b$ es el factor de ramificación y $d$ es la profundidad de la solución más superficial. Dado que BPI visita los estados múltiples veces, puede parecer extremadamente costoso, pero no lo es, dado que la mayor parte de los nodos se encuentran en el nivel más profundo del árbol, por lo tanto no tiene mucha importancia que se visiten los niveles superiores varias veces.^[1]

La principal ventaja de BPI en búsquedas en árboles de juegos es que las búsquedas anteriores tienen a mejorar la heurística usada, como heurística asesina o la poda alfa-beta, de forma que se puede obtener una estimación más precisa de la puntuación de varios nodos en la última búsqueda y la búsqueda se completa más rápidamente ya que se hace en un orden mejor. Por ejemplo, la poda alfa-beta es más eficiente si se busca el primer movimiento mejor.^[1]

Una segunda ventaja es la complejidad en tiempo del algoritmo. Porque las primeras iteraciones usa valores pequeños para $d$ , es decir, se ejecutan extremadamente rápido. Esto permite al algoritmo proporcionar indicaciones sobre el resultado casi inmediatamente, refinándolas según $d$ aumenta. Cuando se utiliza en un entorno interactivo, como en un programa para jugar al ajedrez, esta facilidad permite al programa jugar en cualquier momento con la mejor solución encontrada hasta el momento en la búsqueda realizada.

La complejidad en tiempo en un árbol equilibrado es la misma en con búsqueda en profundidad: $O(b^{d})$ .

En una búsqueda en profundidad iterativa, los nodos en el nivel más inferior se expanden una sola vez, los del nivel anterior dos veces y así hasta la raíz del árbol, que se expande $d+1$ veces.^[1] Por lo tanto, el número total de expansiones es

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

\sum _{i=0}^{d}(d+1-i)b^{i}

Para $b=10$ y $d=5$ el número de expansiones es

6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

En resumen, una BPI de profundidad 1 a profundidad $d$ expande, aproximadamente, un 11% más de nodos que una búsqueda en anchura simple o una búsqueda con profundidad limitada de profundidad $d$ , cuando $b=10$ . Cuanto mayor es el factor de ramificación, menor es la sobrecarga de estados expandidos múltiples veces, pero incluso para un factor de ramificación 2, la BPI solo necesita el doble que una búsqueda en anchura. Esto significa que la complejidad de la BPI es aún $O(b^{d})$ , y la complejidad en espacio es $O(d)$ como una búsqueda en profundidad simple. En general, BPI es el método de búsqueda principal cuando hay un espacio de estados grande y la profundidad de la solución es desconocida.^[1]

Ejemplo

Una búsqueda en profundidad empezando en A, asumiendo que los lados izquierdos del gráfico se toman antes que los derechos y asumiendo que la búsqueda recuerda los nodos visitados previamente y no los repite (dado que esto es un pequeño grafo), visitará los nodos en el siguiente orden: A, B, D, F, E, C, G.

Realizando la misma búsqueda sin recordar los nodos previamente visitados, el resultado no tendrá fin: A, B, D, F, E, A, B, D, F, E, etc., esto ocurre por el ciclo entre A, B, D, F y E, lo que no permite alcanzar C o G.

La búsqueda en profundidad iterativa nos soluciona estos bucles y alcanzará los nodos de los siguientes niveles. Asumiendo que procede de izquierda a derecha como antes:

0: A
1: A (repetido), B, C, E

(Nótese que BPI ha visitado C, lo que no ocurre con la búsqueda en profundidad.)

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

(Nótese que aún visita C, pero aparece más tarde. También visita E por un camino distinto, pero vuelve a F dos veces.)

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

Para este grafo, cuanta más profundidad se añade, los ciclos "ABFE" y "AEFB" simplemente se alargan antes de que el algoritmo abandone e intente otra rama. Puede recorrer varias veces al mismo nodo siempre y cuando no sea la solución

Algoritmo

El siguiente pseudocódigo muestra una BPI implementada en términos de una búsqueda en profundidad limitada recursiva. (LLamada BP).

BPI(raíz, objetivo)
{
  profundidad = 0
  repetir
  {
    resultado = BPL(raíz, objetivo, profundidad)
    Si (resultado es una solución)
      devolver resultado
    profundidad = profundidad + 1
  }
}

Una búsqueda en profundidad limitada se puede implementar de forma recursiva como sigue. Nótese que solo tiene que comprobar los nodos objetivos cuando profundidad == 0, porque cuando profundidad > 0, BPL expande nodos que han sido visitados en iteraciones previas de BPI.

BPL(nodo, objetivo, profundidad)
{
  Si (profundidad == 0 y nodo == objetivo)
    devolver nodo
  sino si (profundidad > 0)
    para cada hijo en expandir(nodo)
      resultado = BPL(hijo, objetivo, profundidad-1)
      si resultado distinto de null
         devolver resultado
  sino
    devolver null
}

Notas

↑ ^a ^b ^c ^d Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2ª edición), Upper Saddle River, New Jersey: Prentice Hall, p. 1080, ISBN 0-13-790395-2 .

Datos: Q1675274

[rn3-1] Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2ª edición), Upper Saddle River, New Jersey: Prentice Hall, p. 1080, ISBN 0-13-790395-2 .

[1]