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 bidireccional

Fernando P.    19/01/2018

Temas:  Fundamentos

Como colofón a la descripción de algoritmos sistemáticos para atacar problemas mediante técnicas de búsqueda de soluciones, vamos a ver algo que no puede calificarse como un algoritmo propiamente dicho, sino como una forma distinta de usar el algoritmo para búsqueda en anchura en determinados problemas.

Vamos a describir una forma distinta de usar el algoritmo para búsqueda en anchura con idea de reducir su complejidad de almacenamiento, que es el principal inconveniente de este algoritmo.

Árbol de búsqueda y nodo destino
Naturalmente, asumimos que la secuencia de estados del problema a resolver puede representarse mediante un árbol de búsqueda, igual que sucede para el algoritmo de búsqueda en anchura. Pero, además, la estructura del problema debe ser tal que podamos conocer desde el comienzo cual es el nodo destino dentro del árbol de búsqueda.

Esto puede parecer un contrasentido porque puede dar la sensación de que el objetivo de resolver el problema consiste en localizar el nodo destino. Pero no lo es, porque una solución al problema es una secuencia de nodos en el árbol de búsqueda que conectan el nodo origen y el nodo destino.

Por ejemplo, si tenemos un problema del tipo de búsqueda de itinerarios (llegar desde un punto origen a un punto destino), conocemos el origen y el destino pero no sabemos qué acciones (rutas) debemos tomar en cada momento para llegar al destino partiendo del origen. La solución al problema es la secuencia de acciones a tomar en cada estado.

Dicho esto, no todos los problemas cuyo espacio de estados puede representarse mediante un árbol de búsqueda tienen un nodo destino bien definido. Puede ocurrir que existan muchos o incluso infinitos nodos destino. Un ejemplo de esto puede ser resolver un rompecabezas o realizar una tarea de montaje de algo que permita ser montado de muchas formas distintas.

Si en nuestro problema podemos identificar uno o algunos (pocos) nodos destino, será posible llevar a cabo la estrategia que vamos a describir a continuación y que denominamos búsqueda bidireccional.

En general, vamos a asumir que el nodo destino es único. Si hubiera más de uno (pero no muchos), podemos modificar artificialmente el árbol de búsqueda para crear un nuevo nodo destino virtual único, que tenga como predecesores sólo a los nodos destino reales.

Búsqueda bidireccional Algoritmo para búsqueda bidireccional
La idea básica de la búsqueda bidireccional consiste en ejecutar simultáneamente dos instancias del algoritmo para búsqueda en anchura. Una de ellas en la forma usual, comenzando en el nodo origen del árbol de búsqueda. La otra, en sentido contrario, usando un árbol de búsqueda invertido que parte del nodo destino.

Es necesario construir un nuevo árbol de búsqueda para la segunda instancia del algoritmo que tenga como nodo origen el verdadero nodo destino del problema. Los sucesores de este origen serán los nodos que son antecesores suyos en el árbol original y así sucesivamente hasta darle la vuelta al árbol de búqueda original.

Naturalmente, el objetivo de la segunda instancia del algoritmo es llegar al nodo origen en el árbol original del problema.

Frontera común
Una vez que pongamos a funcionar de forma simultánea ambas instancias del algoritmo para búsqueda en anchura, va a suceder que en determinada iteración las fronteras de ambas instancias van a colisionar, en el sentido de que ambas fronteras tendrán al menos un nodo en común.

Si la profundidad del nodo destino en el árbol de búsqueda original es  d, es de esperar que ambas instancias del algoritmo confluyan en una frontera común a profundidad  d/2.

Una vez que se haya localizado una frontera común (que puede ser un único nodo), tenemos una solución al problema, que resulta de unir las secuencias de nodos que han localizado ambos algoritmos para llegar a esa frontera. La primera instancia nos proporciona el camino hasta la frontera común y la segunda instancia nos descubre el resto del camino hasta el nodo destino.

Ventajas e inconvenientes de la búsqueda bidireccional
Básicamente, lo que tenemos es el algoritmo para búsqueda en anchura ejecutado de forma que el tamaño de la frontera no se dispara por tener que llegar a grandes profundidades. En este sentido, el algoritmo para búsqueda bidireccional es completo porque tarde o temprano ambas instancias de búsqueda van a coincidir en una frontera común.

No es óptimo, de la misma forma que no lo es el algoritmo para búsqueda en anchura. Es decir, sólo es óptimo si la función de coste es una función monótona respecto de la longitud de cada solución (medida en número de nodos que contiene).

Es posible hacer que la búsqueda bidireccional sea óptima, pero vamos a necesitar alguna modificación que permita a ambas instancias seguir funcionando hasta que la frontera de cada una esté por detrás de la frontera de la otra instancia y hayamos localizado todos los caminos que conectan el nodo origen con el nodo destino para ver cual es el de menor coste.

Aparte de estas cuestiones, como ya se ha comentado, es fundamental que la estructura del problema permita aislar el nodo destino. No hay problema con ramas infinitas mientras el destino pueda ser aislado. Lo que no puede ser, como no era posible en la búsqueda en anchura, es que un nodo tenga infinitos sucesores, tanto en la búsqueda directa como en la inversa (que serían los antecesores del árbol de búsqueda original)).

Rendimiento de la búsqueda bidireccional
Siendo  d  la profundidad del nodo destino en el árbol de búsqueda original y  h  el número promedio de descendientes de cada nodo en el árbol, la complejidad para almacenamiento de la búsqueda en anchura es del orden de  O(hd), que es bastante grande y es el mayor problema del algoritmo para búsqueda en anchura.

Pero en el caso de la búsqueda bidireccional, cada una de las instancias vendrá a explorar una profundidad del orden de  d/2, así que la complejidad de almacenamiento de la búsqueda bidireccional vendrá a ser el doble de lo que necesita la búsqueda en anchura para una profundidad  d/2.

En general, la complejidad de almacenamiento de la búsqueda bidireccional es del orden de  O(2hd/2), que es sustancialmente inferior a  O(hd), a pesar de seguir siendo una complejidad exponencial.

La complejidad en tiempo es igual a la complejidad de almacenamiento, como sucede con la búsqueda en anchura. Esto es, también del orden de  O(2hd/2).

La mejora en la complejidad de almacenamiento significa que esta forma de proceder puede aplicarse a algunos problemas que quedan fuera del alcance (por tamaño) de la búsqueda en anchura sencilla.

La búsqueda bidireccional sigue tenido complejidad exponencial y mejora a la búsqueda en anchura en el sentido de que se duplica la profundidad que podemos explorar, pero en problemas realmente grandes sigue siendo un algoritmo poco práctico por los requisitos de almacenamiento.



El algoritmo para búsqueda bidireccional es una forma inteligente de usar la búsqueda en anchura para poder atacar algunos problemas algo más grandes de la cuenta, pero sigue teniendo limitaciones respecto a la capacidad de almacenamiento.



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



 

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