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

Fernando P.    05/02/2018

Temas:  Fundamentos

Cuando introdujimos la idea de algoritmos para búsqueda heurística ya avanzamos que no habría grandes novedades en la forma de algoritmos completamente nuevos, sino más bien cambios o refinamientos en los algoritmos ya conocidos para búsqueda sistemática que abrieran la vía para añadir información adicional y poder así mejorar la eficiencia de los algoritmos conocidos.

En este sentido, vamos a ver aquí una versión muy sencilla del algoritmo genérico para búsqueda por lo mejor que puede llegar a ser muy rápido localizando soluciones, pero que también tiene sus inconvenientes.

Función de evaluación y función heurística
El algoritmo genérico para búsqueda por lo mejor se caracteriza por lo que vinimos en llamar función de evaluación. También vimos que la función de evaluación es una idea muy genérica y que se suele implementar usando un término más concreto que denominábamos función heurística.

Una función heurística codifica la información extra que tenemos sobre el problema por medio de una estimación del coste en el que se incurre en llegar desde el nodo actual en el árbol de búsqueda hasta un nodo destino.

A la hora de definir una instancia precisa del algoritmo genérico para búsqueda por lo mejor basta con especificar la forma de la función heurística y cómo se construye la función de evaluación a partir de ella. Y eso es lo que vamos a hacer aquí.

Búsqueda ávida
Puede suceder perfectamente que la función de evaluación consista únicamente en la función heurística, es decir, que ambas funciones sean iguales y toda la información extra que tenemos sobre el problema se limite a la estimación de coste desde cada nodo del árbol de búsqueda a un nodo destino.

En estas condiciones, el algoritmo para búsqueda por lo mejor que nos resulta pasará a denominarse algoritmo para búsqueda ávida.

La motivación de esta denominación viene del hecho de que el algoritmo siempre va querer expandir los nodos que estime que están más cerca de un nodo destino, va a intentar acercarse a un nodo destino por encima de cualquier otra consideración.

Esto es así porque seleccionará para expansión el nodo con menor valor de la función de evaluación, que, al ser igual a la función heurística, resultará en el nodo cuya estimación de coste para llegar a un nodo destino sea menor.

Distancia en línea recta Algoritmo para búsqueda ávida
En problemas de itinerarios, es habitual modelizar el problema usando lugares como nodos y trayectos como arcos entre nodos. Los lugares pueden ser pueblos, estaciones de tren, manzanas de una ciudad ... y los trayectos pueden ser carreteras, vías de tren, calles de una ciudad ...

Naturalmente, la cuestión fundamental en los problemas de itinerarios consiste en obtener una solución que use los trayectos disponibles. Si queremos ir de una ciudad a otra habrá que hacerlo por las vías disponibles, no a través del campo o de cualquier manera.

En este tipo de problemas el coste de cada acción suele ser la distancia o coste del itinerario asociado. Pero esas distancias o costes no tienen porqué reflejar bien las distancias físicas (en línea recta) que hay entre los nodos del problema. Las redes de comunicaciones son caprichosas y a veces trayectos que deberían ser cortos se convierten en largos por la enrevesada disposición de las vías disponibles.

Podemos pensar entonces en considerar las distancias físicas en línea recta que hay entre los lugares que caracterizan nuestro problema y usar esta información extra para tratar de obtener una solución rápida sin tener que andar explorando completamente un árbol de búsqueda.

Para uno de estos problemas, un ejemplo de búsqueda ávida consiste en hacer que la función heurística (y la función de evaluación) mida la distancia en línea recta desde el nodo actual hasta un nodo destino. En este caso, diremos que la función heurística codifica la distancia en línea recta.

Inconvenientes de la búsqueda ávida
Usando el ejempo de la distancia en línea recta, es fácil ver que la búsqueda ávida tiene algunos inconvenientes. No por acercarnos lo más posible a un nodo destino vamos a llegar con mínimo coste a él. Puede suceder que un nodo esté muy cerca en línea recta del destino pero que no haya ninguna vía para ir desde ese nodo al destino.

Si el algoritmo para búsqueda ávida localiza uno de estos nodos prometedores pero que no tienen salida, el algoritmo entrará en un bucle sin final. En la ilustración adjunta hay uno de estos nodos que están muy cerca del destino pero que no tienen salida, en este ejemplo concreto el algoritmo no llega a seleccionarlo, pero no sería complicado modificar el ejemplo para que el algoritmo quedara atrapado en un bucle.

Podemos decir que la búsqueda ávida no es un algoritmo completo ya que no garantiza poder localizar siempre una solución.

Y tampoco es óptimo, porque su avidez no tiene en cuenta el coste real de cada acción (coste de los arcos en el árbol de búsqueda) y es fácil que elija acciones prometedoras pero que son de alto coste real. Por ejemplo, a veces compensa hacer más kilómetros por autopista a hacer bastante menos por carreteras convencionales.

Motivación de la búsqueda ávida
A pesar de los problemas expuestos, la búsqueda ávida puede ser realmente rápida localizando soluciones y no tienen porqué ser malas soluciones.

En general, si la estructura de costes de nuestro problema se puede representar bien con la información que podemos añadir vía función heurística, el algoritmo de búqueda ávida funcionará bien.

Si tenemos un problema tal que su estructura de costes no se parece a la información que podemos codificar con la función heurística, el algoritmo de búsqueda ávida no va a ser una buena elección.

Por ejemplo, si tenemos un problema de itinerarios y usamos la distancia en línea recta como función heurística pero luego resulta que el coste de cada itinerario está afectado por factores externos, como puede ser calidad de la vía, antigüedad de los medios, peajes, congestión ... pues va a resultar que la estructura de nuestro problema no está bien representada por la distancia en línea recta, porque depende más de esos factores externos.

Siempre queda la solución de refinar la función heurística para tratar de que represente lo mejor posible la estructura de costes del problema y puede que entonces el algoritmo para búsqueda ávida sea una buena elección para resolverlo. Pero tampoco hay que perder de vista el hecho de que una función heurística muy complicada será un lastre para el algoritmo, porque se evalúa constantemente y puede que no merezca la pena.



El algoritmo para búsqueda ávida es una herramienta que puede funcionar bien en ciertos problemas siempre que tengamos una función heurística simple que represente razonablemente bien la estructura de coste del problema.



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 sobre la búsqueda heurística y la búsqueda ávida.



 

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