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

Árboles de búsqueda

Fernando P.    06/11/2017

Temas:  Fundamentos

En artículos anteriores hemos introducido los problemas que se pueden resolver usando búsqueda de soluciones y hemos visto que tienen una estructura bien definida. También hemos visto algunos ejemplos de este tipo de problemas.

Existen muchos algoritmos para tratar de solucionar este tipo de problemas, pero todos suelen usar un concepto muy útil para representar el proceso de búsqueda de soluciones, denominado árbol de búsqueda.

Árboles de búsqueda de soluciones
Un árbol de búsqueda de soluciones es un grafo que vamos construyendo a medida que trabajamos en el proceso de búsqueda de la solución.

El grafo está compuesto de nodos que son estados posibles del problema (estados del entorno) y de arcos que conectan los nodos y que indican las posibles acciones que podemos tomar en cada estado.

Un arco que conecte dos nodos significa que podemos pasar de un estado a otro con una única acción. Pueden ser arcos dirigidos (sólo es posible un sentido) o libres (podemos ir en los dos sentidos, de un estado a otro sin problema).

Inicialmente, el árbol sólo tiene un nodo, que es el estado inicial del problema. En cada iteración del algoritmo que estemos siguiendo, lo que hacemos es expandir uno o varios nodos, añadiendo los arcos y los nuevos estados que son alcanzables mediante acciones únicas desde esos nodos que hemos expandido.

Naturalmente, nuestro objetivo es llegar a un nodo destino, que representa el estado del entorno en el que consideramos que el problema está resuelto. En general, nos detendremos cuando la expansión de uno nodo resulte en el nodo destino.

Ejemplo de problema para resolver usando un árbol de búsqueda Problema itinerario Madrid-Valencia
Consideremos un problema de itinerarios como aparece en la figura adjunta. En este problema tenemos un mapa de trayectos entre determinadas capitales de provincia. El objetivo del problema es encontrar un itinerario corto desde Madrid (M) hasta Valencia (V).

Por simplicidad, no vamos a considerar en este ejemplo distancias o costes, porque sólo nos interesa ver cómo se desarrolla el proceso de construccción del árbol de búsqueda.

Nótese que no hay sentidos establecidos de movimiento, podemos ir a una capital y acto seguido dar marcha atrás y volver al origen.

También hay posibilidad de hacer bucles, es decir, de moverse entre una serie de capitales de forma indefinida.

Nodos visitados y frontera
Un par de ideas que nos serán de utilidad a la hora de desarrollar un árbol de búsqueda son la lista de nodos ya visitados y la frontera.

En cada iteración, nuestro árbol de búsqueda tendrá una serie de nodos que están pendientes de expandir. Los nodos pendientes de expandir que ya se han visitado (y expandido) anteriormente se incluyen en la lista de nodos ya visitados. Estos nodos no se van a expandir porque podríamos meternos en un bucle. El árbol no sigue creciendo por ellos.

El resto de nodos pendientes de expandir que no se hayan visitado (ni expandido) anteriormente, constituyen lo que denominamos frontera del árbol. Se trata de los lugares por los que el árbol se va a ampliar.

Algoritmo genérico para construir un árbol de búsqueda
Vamos a detallar un algoritmo muy sencillo que nos va a permitir resolver el problema de itinerario que hemos planteado:

  1. Crear la frontera con el estado inicial del problema
  2. Crear vacía la lista de nodos ya visitados
  3. Si la frontera está vacía el problema no tiene solución. Detenerse
  4. Elegir un nodo de la frontera, sea  n  el nodo elegido
  5. Eliminar  n  de la frontera
  6. Añadir  n  a la lista de nodos ya explorados
  7. Ampliar el árbol expandiendo el nodo  n, sea  X  el conjunto de nodos que resultan de expandir  n
  8. Si el nodo destino está contenido en  X  hemos terminado, tenemos una solución
  9. Añadir a la frontera los nodos en  X  que no estén en la lista de nodos ya visitados
  10. Ir a 3

Árbol búsqueda itinerario Madrid-Valencia Si aplicamos este algoritmo a nuestro problema de ejemplo, resulta un proceso de construcción del árbol de búsqueda que se puede ver bien en la animación adjunta.

Nótese que en cada paso de la animación se han expandido todos los nodos existentes en la frontera en ese momento, no se ha ido nodo a nodo, para hacerlo más sencillo.

Una vez que llegamos al nodo destino, la solución que hemos encontrado para el problema consiste en la sucesión de acciones que determinan los arcos que conectan el nodo origen y el nodo destino. En el ejemplo que nos ocupa, la solución encontrada es  M→GU→CU→V.

Consideraciones sobre el algoritmo genérico
El algoritmo descrito sirve para expandir árboles de búsqueda en problemas que se puedan resolver usando búsqueda de soluciones, pero tiene varios problemas y seguramente no es un algoritmo que deseemos usar, aunque sí que es la base de algoritmos más eficientes.

El primer problema que tiene nuestro algoritmo genérico consiste en que no considera cuestiones de coste. Para el ejemplo que hemos puesto, puede suceder que algunos trayectos entre capitales de provincia sean muy cortos y otros muy largos. El algoritmo localiza el itinerario con menos trayectos entre capitales de provincia, pero no el más corto, aunque tuviéramos datos de longitudes de trayectos.

El problema de coste se puede solucionar modificando nuestro algoritmo básico para localizar todas las soluciones posibles (no deteniéndose al llegar al destino) y luego evaluarlas para ver cual es la de menor coste, pero no es la forma más eficiente de resolver uno de estos problemas.

El problema más importante consiste en cómo elegir qué nodos vamos a expandir en cada iteración. El problema de ejemplo es muy sencillo, pero problemas reales pueden tener millones de estados posibles del problema y no conviene expandir nodos que no sean prometedores, porque los árboles se pueden complicar espectacularmente con mucha facilidad, mucho más allá de lo que un computador puede representar.

Naturalmente, la gracia de los algoritmos eficientes es que crean árboles de tamaño limitado, pero son capaces de llegar al nodo destino en un tiempo de cómputo razonable. Estos algoritmos se irán viendo en sucesivos artículos, pero suelen partir del algoritmo base visto aquí.



El concepto de árbol de búsqueda es importante a la hora de resolver problemas de búsqueda. Permite diseñar algoritmos sencillos, como el visto aquí, y permite mejorar esos algoritmos para llegar a algoritmos mucho más elaborados y eficientes.



Para saber más:

Este libro tiene varios capítulos dedicados a agentes inteligentes así como resolución de problemas mediante búsqueda y seguramente sea el mejor recurso que se puede encontrar para profundizar en este tema.



 

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