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:
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 h2 nodos.
En general, para una profundidad d la cantidad de nodos a evaluar sería:
h + h2 + h3 + … + hd
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 hd o, equivalentemente, que es
O(hd)
Respecto al espacio de almacenamiento, para el mismo caso anterior, almacenar los nodos visitados
precisaría de algo proporcional a:
h + h2 + h3 + … + hd-1
Mientras que almacenar la frontera requeriría de algo porporcional a hd,
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(hd), 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:
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.
Inicio |
![]() ![]() |
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 |