Revolución IA

La Inteligencia Artificial está llamada a protagonizar la próxima Revolución tecnológica

Inicio Sobre Revolucionia Temas Para saber más Contacto

Algoritmo para búsqueda limitada en profundidad

Fernando P.    03/01/2018

Temas:  Fundamentos

El algoritmo para búsqueda en profundidad es una opción razonable para resolver problemas grandes, dentro de la clase de problemas que se pueden resolver mediante técnicas de búsqueda de soluciones. Su mayor ventaja reside en una moderada complejidad de almacenamiento, pero tiene inconvenientes en forma de posibilidad de generar ramas de longitud infinita que hacen que el algoritmo no sea completo.

En esta ocasión, vamos a describir una modificación sencilla al algoritmo general para búsqueda en profundidad que trata de evitar el inconveniente de las ramas de longitud infinita.

Construcción del árbol de búsqueda
Básicamente, vamos a proceder de la misma forma que para los algoritmos anteriores. El concepto fundamental para definir el algoritmo sigue siendo el árbol de búsqueda para el problema.

De nuevo, la característica distintiva del algoritmo que vamos a describir consiste en la forma en la que construye el árbol de búsqueda, para tratar de localizar el nodo destino que nos proporcionará la solución al problema.

Búsqueda limitada en profundidad
Este algoritmo usa exactamente la misma idea que ya vimos en el algoritmo para búsqueda en profundidad. La novedad consiste en tratar de estimar a priori cual es la máxima profundidad  L  (medida en arcos desde el origen hasta el nodo que se está explorando) que el algoritmo va a permitir.
Algoritmo para búsqueda limitada en profundidad
Cuando el algoritmo alcance nodos a profundidad  L, no los expandirá para seguir a sus sucesores y operará como si no tuvieran sucesores, es como si esos posibles sucesores no existieran.

De esta forma, se evita la posibilidad de que el algoritmo genere ramas de longitud infinita, ya sea porque hay posibilidad de que se generen bucles en el grafo de estados del problema o porque, efectivamente, hay muchos estados posibles para el problema y pueden aparecer ramas demasiado largas en el árbol de búsqueda.

La cuestión de los bucles en el grafo de estados del problema se podía salvar con la variante denominada búsqueda con traza en profundidad, que ya comentamos cuando describimos el algoritmo para búsqueda en profundidad. Esta variante es más eficiente que la búsqueda limitada en profundidad para detectar bucles.

Pero la cuestión de aparición de ramas infinitas por existir demasiados estados en el problema no podíamos salvarla y exigíamos problemas que no fueran capaces de generar ramas infinitas en el árbol de búsqueda. Con el algoritmo para búsqueda limitada en profundidad podemos eliminar esta restricción sobre los problemas, pero debemos fijar una profundidad máxima  L.

En general, vamos a denominar diámetro del problema a la mayor profundidad  L  a la que puede hallarse una soluciónal mismo. De esta forma, podemos describir el algoritmo para búsqueda limitada en profundidad como una variante del algoritmo para búsqueda en profundidad que se limita a explorar sólo el diámetro del problema.

Lo que no cambia respecto al algoritmo para búsqueda en profundidad es la exigencia de que no pueda resultar un número infinito de descendientes al expandir un nodo, porque el algoritmo podría quedar fácilmente atrapado en uno de estos nodos.

Sumario del algoritmo para búsqueda en profundidad
A partir de las ideas vistas en el punto anterior, estamos en condiciones de dar un sumario completo del algoritmo, que no es más que una variante del algoritmo para búsqueda en profundidad:

  1. Elegir el diámetro del problema  L
  2. Fijar a 0 la variable  maxima_profundidad
  3. Crear la frontera como una lista LIFO vacía
  4. Insertar el estado incial del problema en la frontera
  5. Si la frontera está vacía el problema no tiene solución. Detenerse con error y devolver  maxima_profundidad
  6. Sacar el siguiente nodo de la frontera, sea  n  el nodo elegido
  7. Sea  R  la lista (finita) de nodos que conectan  n  con el origen, incluyendo a  n
  8. Sea  nr  el número de nodos en  R
  9. Hacer maxima_profundidad = max(maxima_profundidad, nr)
  10. Si  nr = L + 1  ir a 5
  11. Ampliar el árbol expandiendo el nodo  n. Sea  X  el conjunto de nodos que resultan de expandir  n
  12. Sea  Y  la lista de nodos en  X  que no estén ya en  R  ni en la frontera
  13. Para cada nodo  p  en  Y, repetir 14 a 15
  14. Si  p  es el nodo destino hemos terminado. La solución es la secuencia de nodos/acciones en  R  que conectan el origen con  p
  15. Insertar  p  en la frontera
  16. Ir a 5

El paso 7 tiene como objeto controlar que el algoritmo no genere ramas de profundidad infinita debido a bucles en el grafo que define los estados y posibles acciones desde los mismos para el problema en cuestión. También nos sirve para conocer la profundidad del nodo que estamos explorando.

Si el algoritmo se detiene con error y nos devuelve un valor de  L + 1, entonces sabemos que han quedado nodos por explorar más allá del diámetro del problema y que quizá haya una solución en ellos que podemos localizar volviendo a ejecutar el algoritmo con un mayor diámetro.

Ventajas e inconvenientes del algoritmo
El algoritmo para búsqueda limitada en profundidad hereda la sencillez del algoritmo para búsqueda en en profundidad y es completo si hay una solución que se encuentra a una profundidad menor o igual al diámetro del problema. No es completo si no hay solución dentro del diámetro del problema, pero podemos conocer si el algoritmo se ha dejado nodos por explorar debido a su profundidad para volver a ejecutarlo con un mayor diámetro.

Así que la elección de  L  es clave en relación a la completitud del algoritmo.

La propiedad que no tiene este algoritmo es la optimalidad, igual que sucede con el algoritmo para búsqueda en profundidad. No localiza solución óptima a no ser que sólo exista una solución posible. En el caso de búsqueda de solución de mínimo coste no hay garantía de que la solución hallada sea de mínimo coste, ni siquiera que sea relativamente buena.

Rendimiento del algoritmo
Este algoritmo tiene exactamente la misma complejidad que el algoritmo para búsqueda en profundidad. Es decir, complejidad polinomial para almacenamiento y complejidad exponencial para tiempo de ejecución.

La complejidad para almacenamiento viene a ser  O((h+1)⋅d), donde  h  es el número promedio de descendientes por nodo y  d  es la profundidad a evaluar.

La complejidad en tiempo del algoritmo es  O(hd). Se trata de un algoritmo de búsqueda sistemática, igual que el algoritmo del que deriva, y eso impone una cota superior al tiempo de ejecución que viene a equivaler a tener que expandir completamente el árbol de búsqueda.

La complejidad polinomial para almacenamiento es la gran ventaja de este algoritmo, mucho más manejable para problemas de gran tamaño. El motivo de esta reducida complejidad es que el algoritmo está siempre centrado en una rama del árbol, tratando de llegar al final (que tiene acotado) y no necesita saber nada del resto del árbol.

Por último, notar que la variante del algoritmo original denominada búsqueda con traza en profundidad también puede implementarse en el caso de búsqueda limitada en profundidad y también tiene una complejidad de almacenamiento menor a la del algoritmo general. La complejidad de esta variante viene a ser  O(d) y puede ser interesante en problemas realmente grandes.



El algoritmo de búsqueda limitada en profundidad es la alternativa natural al algoritmo general para búsqueda en profundidad si tenemos un problema susceptible de generar ramas infinitas y hereda tanto ventajas como inconvenientes de este.



Para saber más:

Libro de Stuart Russell y Peter Norvig que trata todas las técnicas de Inteligencia Artificial. No hace demasiado énfasis en cuestiones conectivistas (redes neuronales artificiales) y contiene abundante material del resto de técnicas. El capítulo 3 contiene una discusión detallada del algoritmo para búsqueda limitada en profundidad.



 

Inicio Powered by NetBSD
 
HTML5
 
En general, todo el contenido de este sitio web es original, salvo referencias o enlaces a otros sitios web y citas o reproducciones expresamente presentadas como tales.

No está permitida la reproducción ni la copia del contenido de este sitio web sin el permiso expreso de la propiedad del mismo.

Este sitio web no utiliza cookies ni ningún otro mecanismo para almacenar información en los navegadores de los visitantes ni para realizar seguimiento de los mismos.

2017,2018 Revolucionia.net
Sobre Revolucionia
Temas
Para saber más
Contacto