title: Búsqueda en profundidad limitada
text: # 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 limitada
  ## 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.
  
  # Búsqueda en profundidad limitada
  ## Algoritmo (informal)
  
  * Determinar el vértice donde la búsqueda debe empezar y asignar la máxima profundidad
  * Comprobar si el vértice actual es el estado objetivo
  ** Si no: No hacer nada
  ** Si sí: devolver
  * Comprueba si el vértice actual está dentro de la profundidad máxima
  ** Si no: No hacer nada
  ** Si sí:
  *** Expandir el vértice y guardar todos sus sucesores en una pila
  *** Llamar a BPL recursivamente para todos los vértices de la pila y volver al paso 2
  
  # Búsqueda en profundidad limitada
  ## 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.
  
  # Búsqueda en profundidad limitada
  ## Propiedades
  ### 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.
  
  # Búsqueda en profundidad limitada
  ## Propiedades
  ### 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.
  
  # Búsqueda en profundidad limitada
  ## Propiedades
  ### 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.