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 iterativa en profundidad

Fernando P.    10/01/2018

Temas:  Fundamentos

Hemos visto dos aproximaciones básicas a la hora de construir algoritmos sistemáticos que se puedan usar para resolver problemas a resolver mediante técnicas de búsqueda de soluciones. Se trata de la búsqueda en anchura y la búsqueda en profundidad.

Ambas aproximaciones tienen sus ventajas e inconvenientes, pero desde el punto de vista práctico, sólo la búsqueda limitada en profundidad tiene alguna posibilidad de resolver problemas muy grandes debido a su moderada complejidad de almacenamiento. Lo que vamos a ver aquí es una especie de meta-algoritmo creado sobre la idea de búsqueda limitada en profundidad que consigue las ventajas de ambas aproximaciones.

Problemas con la búsqueda limitada en profundidad
El algoritmo para búsqueda limitada en profundidad es una buena opción para atacar problemas que tengan capacidad de generar árboles de búsqueda muy grandes, pero tiene dos inconvenientes importantes:

Respecto a la cuestión de elegir una profundidad máxima a explorar (diámetro del problema), ya habíamos sugerido que una posibilidad para problemas en los que no hubiera una cota clara, que consistía en probar diámetros en forma creciente.

Búsqueda iterativa en profundidad
El algoritmo para búsqueda iterativa en profundidad es una generalización del algoritmo para búsqueda limitada en profundidad, que se limita a ir iterando este con profundidad creciente.

En la primera iteración se parte de profundidad igual a 1 (en la que se explora sólo el nodo inicial). En la segunda iteración se exploran los nodos hijos del origen. En general, en la iteración  n  se explora, de nuevo, todo el árbol de búsqueda hasta profundidad máxima  n, usando el algoritmo para búsqueda limitada en profundidad.
Algoritmo para búsqueda iterativa en profundidad
En el momento en que se localice un nodo que cumple con los requisitos de solución al problema se detiene el proceso y esa es la solución al problema (la ruta más corta que conecta ese nodo con el origen).

De alguna forma, el algoritmo opera usando una mezcla de búsqueda en profundidad y búsqueda en anchura.

En la ilustración adjunta, se puede ver cómo el algoritmo va explorando de forma recurrente, con profundidad creciente, el árbol de búsqueda hasta explorarlo por completo.

Sumario del algoritmo para búsqueda iterativa en profundidad
A partir de las ideas vistas en el punto anterior, estamos en condiciones de dar un sumario completo del algoritmo, que viene a ser un meta-algoritmo construido sobre la base del algoritmo para búsqueda limitada en profundidad:

  1. Fijar a 1 el diámetro del problema  L
  2. Ejecutar el algoritmo para búsqueda limitada en profundidad usando un diámetro de problema igual a  L. Sea  r  el resultado del algoritmo
  3. Si  r = no solución, sumar  1  a  L  e ir a 2
  4. Si  r  es una solución válida, hemos terminado,  r  es la solución óptima al problema

Ventajas e inconvenientes del algoritmo
Puede parecer que el algoritmo para búsqueda iterativa en profundidad es poco eficiente porque realiza trabajo duplicado en la forma de expandir una y otra vez los nodos cerca del origen en cada iteración. Pero los niveles en los que más reitera este trabajo son los niveles que menos nodos suelen tener y el trabajo a realizar en el último nivel (que sólo se realiza una vez) es, en promedio para problemas grandes, mucho mayor que el trabajo reiterado en los niveles anteriores.

El algoritmo es completo si hay una solución a profundidad finita en el árbol de búsqueda, de la misma forma que sucede con el algoritmo para búsqueda en anchura.

Si la función de coste es una función creciente en la distancia del nodo al origen (medida como el mínimo número de arcos que conectan el nodo con el origen) este algoritmo es óptimo y va a localizar una solución óptima, porque su forma de operar implica que la primera solución localizada es la más cercana al origen. Se trata de la misma situación que teníamos en el algoritmo para búsqueda en anchura.

El algoritmo no puede quedar atrapado en ramas de longitud infinita, porque eso no puede suceder en el algoritmo para búsqueda limitada en profundidad, que es el bloque constructivo de este nuevo algoritmo.

Como ya hemos mencionado, el algoritmo para búsqueda iterativa en profundidad es una especie de mezcla entre los algoritmos para búsqueda en anchura y para búsqueda limitada en profundidad. Podríamos tener la tentación de pensar en incorporar las ideas del algoritmo para búsqueda con coste uniforme, pero ya adelantamos que no es fácil y resulta un algoritmo que pierde parte de las ventajas que ya tenemos.

Por lo demás, este algoritmo no se puede aplicar (como ninguno de los vistos) si la expansión de un nodo resulta en un número infinito de nodos.

Si el problema no tiene solución y hay ramas infinitas del árbol, este algoritmo no se detendrá nunca, de la misma forma que les ocurre a todos los algoritmos vistos. En este caso sería necesario añadir un mecanismo de parada por tiempo de ejecución excesivo (o diámetro excesivo).

Rendimiento del algoritmo
Este algoritmo tiene exactamente la misma complejidad que el algoritmo para búsqueda limitada 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 los algoritmos de los 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 una de las dos ventajas de este algoritmo, heradada del algoritmo para búsqueda limitada en profundidad. La otra ventaja es su optimalidad, heredada del algoritmo para búsqueda en anchura.

En general, este algoritmo va a ser el preferido para resolver problemas problemas que tengan capacidad de generar árboles de búsqueda muy grandes.



El algoritmo de búsqueda iterativa en profundidad combina las mejoras ventajas de todos los algoritmos de los que desciende. Se trata de la mejor opción para resolver problemas de gran tamaño y hay poco margen para mejorarlo en búsqueda sistemática.



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 iterativa 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