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 anchura

Fernando P.    13/12/2017

Temas:  Fundamentos

En el contexto de problemas que se pueden resolver usando técnicas de búsqueda de soluciones ya hemos visto que hay una clase de algoritmos que operan mediante búsqueda sistemática.

Vamos a describir con detalle aquí el primero de estos algoritmos, que es el algoritmo más sencillo y se denomina de búsqueda en anchura.

Construcción del árbol de búsqueda
La idea fundamental subyacente a los algoritmos que pueden usarse para búsqueda de soluciones es el concepto de árbol de búsqueda. En general, las diferencias entre unos y otros algoritmos van a estar en la forma en la que se construye este árbol de búsqueda.

Cuando vimos el concepto de árbol de búsqueda ya expusimos un algoritmo general que nos permitía construir el árbol en problemas que tuvieran la estructura que caracteriza a los problemas que se pueden resolver mediante técnicas de búsqueda de soluciones.

Una simple modificación de este algoritmo a la hora de decidir qué nodos se expanden primero es la que nos va a permitir tener el primer algoritmo para solucionar el tipo de problemas que nos ocupan.

Búsqueda en anchura
La idea fundamental del algoritmo que vamos a describir consiste en explorar siempre el nodo de la frontera que esté más cerca del origen del árbol.

Para aclarar el concepto de cercanía, usaremos la idea de distancia entre dos nodos, que consiste en la mínima cantidad de arcos que conectan ambos nodos (puede haber más de un camino entre ellos).

Si tenemos una lista de nodos en la frontera con igual distancia al origen, los exploramos según su antigüedad en la frontera.

Denominamos al algoritmo como de búsqueda en anchura porque la forma de explorar propuesta expande el arbol de forma uniforme en todas sus direcciones. Se puede decir que hace el árbol ancho a la vez que profundo.

Es fácil ver que la forma de explorar propuesta se puede implementar fácilmente haciendo que la frontera del árbol sea una lista FIFO (First In First Out, primero en entrar es primero en salir).

Es decir, por un lado vamos introduciendo nodos en la frontera a medida que los visitamos y por otro los vamos sacando para expandirlos en el mismo orden que entraron, con lo que en cada momento obtendremos el nodo que más tiempo lleva en la frontera y que tendrá que ser, necesariamente, el más cercano al origen.

En la ilustración adjunta hay un ejemplo de cómo se aplicaría el algoritmo a un caso sencillo de árbol de búsqueda.

Sumario del algoritmo para búsqueda en anchura
Con las ideas dadas en el punto anterior, estamos en condiciones de dar un sumario completo del algoritmo, que es una instancia ligeramente modificada del algoritmo general para construir árboles de búsqueda:

1. Crear la frontera como una lista FIFO vacía
2. Insertar el estado incial del problema en la frontera
3. Crear vacía la lista  V  de nodos ya visitados
4. Si la frontera está vacía el problema no tiene solución. Detenerse
5. Sacar el siguiente nodo de la frontera, sea  n  el nodo elegido
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. Sea  Y  la lista de nodos en  X  que no estén ya en  V  ni en la frontera
9. Para cada nodo  p  en  Y  repetir 10 a 11
10. Si  p  es el nodo destino hemos terminado. La solución es la secuencia de nodos/acciones en  V  que conectan el origen con  p
11. Insertar  p  en la frontera
12. Ir a 4

Ventajas del algoritmo
La principal ventaja del algoritmo para búsqueda en anchura es su sencillez de implementación dada la sencillez de su mecanismo de funcionamiento.

Por otro lado, el algoritmo es completo en el sentido de que siempre va a localizar el nodo destino y lo va a hacer usando el camimo más corto posible, por su propia dinámica interna que exige explorar en primer lugar siempre el nodo más cercano al origen.

Nótese que el algoritmo sólo puede funcionar si el número de nodos que resultan de expandir otro cualquiera es finito, que se trata de una restricción razonable para problemas reales.

Inconvenientes del algoritmo
Desde el punto de vista de optimalidad de la solución localizada, este algoritmo sólo funciona si la función de coste es no decreciente en la longitud de cada camino, siendo el caso de coste uniforme (todas las acciones o arcos del árbol tienen el mismo coste) el caso más sencillo de esta situación.

Para funciones de coste que no verifiquen esta propiedad, este algoritmo no garantiza obtener la solución óptima porque podrían existir soluciones (caminos) más largas pero de menor coste.

Rendimiento del algoritmo
Supongamos que, de media, cada nodo del arbol viene a tener  h  descendientes. Para el nivel 1 (hijos del nodo inicial) tendríamos que evaluar, de media, h  nodos, para el nivel 2 serían  h²  nodos.

En general, para una profundidad  d  la cantidad de nodos a evaluar sería:

h + h² + h³ + … + h^d

Si  d  es suficientemente grande, el último término es mucho mayor que el resto y por ello decimos que su complejidad es del orden de  h^d  o, equivalentemente, que es  O(h^d)

Respecto al espacio de almacenamiento, para el mismo caso anterior, almacenar los nodos visitados precisaría de algo proporcional a:

h + h² + h³ + … + h^d-1

Mientras que almacenar la frontera requeriría de algo porporcional a  h^d, por lo que el almacenamiento de la frontera domina al almacenamiento de los nodos visitados y podemos decir que la complejidad de almacenamiento es  O(h^d), igual que para el caso del tiempo.

Estas complejidades exponenciales no son viables para problemas complejos que puedan resultar en árboles muy grandes. Por ejemplo, si  h = 10, para una profundidad de árbol  d = 12  ya tenemos valores enormes del orden de 10 elevado a 12, tanto en tiempo como requisitos de almacenamiento. Incluso evaluando un millón de nodos por segundo ya necesitaríamos más de 10 días para ejecutar el algoritmo y los requisitos de memoria serían del orden de Terabytes.

Es más grave el tema del almacenamiento, porque es fijo y no es tan fácil dimensionarlo como puede ser el tiempo de ejecución. Así que tenemos que este algoritmo no va a ser viable para problemas de cierto tamaño.

El algoritmo de búsqueda en anchura es bastante sencillo y es completo con funciones de coste adecuadas, pero resulta inapropiado para problemas que tengan el potencial de generar árboles de búsqueda con muchos millones de nodos.

Para saber más:

• AI: A modern Approach

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