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

Fernando P.    27/12/2017

Temas:  Fundamentos

En dos artículos anteriores, hemos visto sendos algoritmos que pueden ser usados para resolver problemas mediante técnicas de búsqueda de soluciones. Se trataba del algoritmo para búsqueda en anchura y del algoritmo para búsqueda con coste uniforme.

Ambos algoritmos son bastante capaces en cuanto que se pueden considerar completos y pueden encontrar la solución óptima (el de búsqueda en anchura sólo en determinadas circunstancias). Pero ambos algoritmos tienen mal rendimiento en problemas muy grandes y no resultan prácticos. En este artículo vamos a ver un nuevo algoritmo que no tiene tantos problemas de rendimiento.

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.

Los dos algoritmos anteriores procedían construyendo el árbol de búsqueda de una forma más o menos uniforme a partir del origen, no se ponía especial énfasis en ninguna zona del árbol. El algoritmo de búsqueda en profundidad usa una política complétamente distinta.

Búsqueda en profundidad Algoritmo para búsqueda en profundidad
Este algoritmo opera usando la política según la cual, una vez seleccionado un nodo, vamos a explorar por debajo suyo en profundidad, seleccionando siempre un nuevo nodo que tenga la mayor profundidad (distancia medida en número de arcos del camino hasta el origen).

De alguna forma, viene a ser una versión del algoritmo para búsqueda en anchura en el que sustituimos la lista FIFO de nodos que representa la frontera por una lista LIFO (último en entrar es el primero en salir).

En general, si el nodo que estamos examinando en un momento dado tiene descendientes, el siguiente nodo a examinar será uno de esos descendientes para poder avanzar en profundidad.

Sólo cuando lleguemos a un nodo sin descendientes deberemos ir hacia atrás para localizar otro nodo a expandir, que deberá ser el de mayor profundidad de entre todos los que conforman la frontera.

En la ilustración adjunta se muestra un ejemplo de como procedería el algoritmo en un árbol de ejemplo. Nótese que en este ejemplo no se desarrolla la frontera complétamente, pero se marcan los nodos que tienen descendendientes pendientes de explorar (y que constituirían la frontera). Se ha hecho así para mayor claridad de la evolución del algoritmo. Se trata de una variante del algoritmo denominada búsqueda con traza en profundidad.

Obviamente, la búsqueda en profundidad no va a funcionar si nuestro árbol de búsqueda puede tener ramas de profundidad infinita, dado que el algoritmo no se detendría nunca si localiza una de esas ramas. En este caso habría que hacer una provisión para detener el algoritmo (y considerar la búsqueda fallida) si se sobrepasa una determinada profundidad que se considere excesiva.

En general, vamos a considerar problemas que no desarrollan árboles de búsqueda con ramas de profundidad infinita (salvo bucles detectables) y tampoco vamos a consideraran problemas que puedan resultar en un número infinito de descendientes para un nodo (esto ya se consideraba en los dos algoritmos anteriores).

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 también se puede considerar una modificación del algoritmo para búsqueda en anchura:

  1. Crear la frontera como una lista LIFO vacía
  2. Insertar el estado incial del problema en la frontera
  3. Si la frontera está vacía el problema no tiene solución. Detenerse
  4. Sacar el siguiente nodo de la frontera, sea  n  el nodo elegido
  5. Sea  R  la lista (finita) de nodos que conectan  n  con el origen, incluyendo a  n
  6. Ampliar el árbol expandiendo el nodo  n. Sea  X  el conjunto de nodos que resultan de expandir  n
  7. Sea  Y  la lista de nodos en  X  que no estén ya en  R  ni en la frontera
  8. Para cada nodo  p  en  Y  repetir 9 a 10
  9. 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
  10. Insertar  p  en la frontera
  11. Ir a 3

El paso 5 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.

Ventajas e inconvenientes del algoritmo
El algoritmo para búsqueda en profundidad hereda la sencillez del algoritmo para búsqueda en anchura y es completo, siempre localiza una solución para árboles finitos (tanto en número de descendientes por nodo como en profundidad máxima de un nodo).

La propiedad que no tiene es la optimalidad. 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.

Evidentemente, este algoritmo está en clara desventaja frente a los algoritmos de búsqueda en anchura y de búsqueda con coste uniforme en lo que a completitud se refiere.

Rendimiento del algoritmo
El principal inconveniente que existe con los algoritmos de búsqueda en anchura y de búsqueda con coste uniforme es su complejidad. Sobre todo con la complejidad relativa al almacenamiento necesario. Se trata de complejidades exponenciales sobre la profundidad a evaluar en el árbol de búsqueda.

Esta complejidad exponencial hace inviable el uso de estos algoritmos en problemas relativamente grandes porque el espacio de almacenamiento no es algo que se pueda dimensionar fácilmente a la hora de ejecutar un algoritmo.

Sin embargo, el algoritmo de búsqueda en profundidad tiene una complejidad para almacenamiento que 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.

Se trata de una complejidad polinomial 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 y no necesita saber nada del resto del árbol.

Esta forma de proceder que le otorga una complejidad tan reducida es la que también le limita en cuanto a la posibilidad de localizar una solución óptima. De alguna forma, se hacen concesiones en la optimalidad a cambio de tener un algoritmo que puede encontrar una solución para problemas muy grandes. Cosa que los otros dos algoritmos vistos no tienen nada fácil.

La complejidad en tiempo del algoritmo es similar a la de los algoritmos anteriores, es  O(hd). Se trata de un algoritmo de búsqueda sistemática, igualmente que sucede con los otros dos visto 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.

Por último, notar que la variante del algoritmo en el ejemplo de la ilustración, mucho más ilustrativa que el algoritmo general, denominada búsqueda con traza en profundidad, tiene una complejidad de almacenamiento menor a la del algoritmo general. La complejidad de esta variante viene a ser  O(2d) y puede ser interesante en problemas realmente grandes.



El algoritmo de búsqueda en profundidad no es completo pero su reducida complejidad en términos de almacenamiento lo hace una opción viable en problemas con espacios de estados inmensos que tienden a generar árboles de búsqueda muy grandes.



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