Búsqueda en profundidad limitada

En ciencias de la computación, la búsqueda en profundidad limitada es un algoritmo para explorar los vértices de un grafo. Es una modificación de la búsqueda en profundidad y se usa, por ejemplo, en el algoritmo de búsqueda en profundidad iterativa.

Búsqueda en profundidad
Estructura de datos	Grafo
Clase de complejidad	Algoritmo de búsqueda
Tiempo de ejecución
Peor caso	$O(|V|+|E|)$
No es óptimo ni completo

General

Como la búsqueda en profundidad normal, la búsqueda en profundidad limitada es una búsqueda sin información. Funciona igual que la búsqueda en profundidad simple, pero evita los inconvenientes respecto a la completitud, imponiendo un límite máximo de profundidad de búsqueda. Incluso aunque la búsqueda pudiese expandir un vértice más allá de esa profundidad, no lo hará, por lo que no continuará por caminos de profundidad infinita ni se atascará en ciclos. Por lo tanto, la búsqueda en profundidad limitada encontrará una solución si esta se encuentra dentro del límite de profundidad, lo que garantiza completitud en todos los grafos.​

Algoritmo (informal)

1. Determinar el vértice donde la búsqueda debe empezar y asignar la máxima profundidad
2. Comprobar si el vértice actual es el estado objetivo
   • Si no: No hacer nada
   • Si sí: devolver
3. Comprueba si el vértice actual está dentro de la profundidad máxima
   • Si no: No hacer nada
   • Si sí:
     1. Expandir el vértice y guardar todos sus sucesores en una pila
     2. Llamar a BPL recursivamente para todos los vértices de la pila y volver al paso 2

Pseudocódigo​

BPL(nodo, objetivo, profundidad) {
  si ( profundidad >= 0 ) {
    si ( nodo == objetivo )
      devolver nodo

    para cada hijo en expandir(nodo)
      BPL(hijo, objetivo, profundidad-1)
  }
}

Propiedades

Complejidad en espacio

Como, internamente, BPL usa una búsqueda en profundidad, la complejidad en espacio es equivalente a la búsqueda en profundidad simple.​

Complejidad en tiempo

Como, internamente, BPL usa una búsqueda en profundidad, la complejidad en tiempo es equivalente a la búsqueda en profundidad simple y es O($\vert V\vert +\vert E\vert$) donde $\vert V\vert$ es el número de vértices y $\vert E\vert$ el número de lados en el grafo explorado. Nótese que la BPL no explora el grafo completo, sólo la parte que hay antes del límite de profundidad.​

Completitud

Aunque BPL no puede seguir caminos de longitud infinita, ni puede atascarse en ciclos, en general el algoritmo no es completo ya que no puede encontrar una solución más allá del límite de profundidad. Pero si la profundidad máxima elegida es mayor a la profundidad de alguna solución, el algoritmo pasa a ser completo.​

Optimalidad

BPL no es óptima.​ Aún tiene el problema de la búsqueda en profundidad simple de que primero explora un camino hasta su fin, en el cual puede encontrar una solución que es más cara que alguna otra solución en otro camino.

Referencias

• Datos: Q829647