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 A*
Fernando P. 23/02/2018
Temas: Fundamentos
En un artículo anterior habíamos introducido la idea de
búsqueda heurística como
remedio con idea de tratar de mejorar los algoritmos para
búsqueda sistemática usando
información adicional que podamos tener sobre el problema.
En una primera aproximación, vimos los algoritmos para
búsqueda ávida, que realmente sólo
usan información heurística para resolver el problema, pero resultan sencillos. Aquí vamos a ver la forma
más refinada de algoritmos para búsqueda heurística, que son los que combinan información cierta
sobre costes (como hacen los algoritmos para búsqueda sistemática) con información de orden heurístico.
Búsqueda A*
La búsqueda A* no es ningún algoritmo concreto, es más bien una familia de algoritmos, igual que sucedía
con la búsqueda ávida. También, de la misma forma que para la búsqueda ávida, vamos a partir de la idea
general del algoritmo para
búsqueda por lo mejor.
En el caso de la búsqueda ávida, la función de evaluación para el algoritmo de búsqueda por lo mejor
se reducía exclusivamente a una función heurística. En el caso de la búsqueda A* la función de evaluación
es más elaborada:
Sea f() la función de evaluación para un algoritmo de búsqueda A*
Se va a verificar que f(n) = g(n) + h(n), siendo
n un nodo del árbol de búsqueda
g(n) es el mínimo coste (real) hasta el nodo n
h(n) es el coste estimado de llegar desde el nodo n hasta un nodo destino
La búsqueda A* opera expandiendo el
árbol de búsqueda del problema de forma que en
cada momento expande el nodo con menor valor de la función de evaluación.
Se trata del mismo funcionamiento que vimos en el algoritmo para
búsqueda con coste uniforme,
usando la función de evaluación como medida de coste. De alguna forma, la búsqueda A* es una mejora del
algoritmo para búsqueda con coste uniforme, que tiene buenas propiedades para búsqueda sistemática.
Con la construcción que hemos hecho de la función de evaluación, cada nodo del árbol va a tener asociado
el coste del mejor camino que empieza en el nodo origen y llega hasta un nodo destino.
Heurísticas admisibles
Naturalmente, el comportamiento de un algoritmo basado en búsqueda A* va a depender de la definición
de la función heurística h(). Elecciones acertadas de h() darán
lugar a un algoritmo muy eficiente y elecciones malas darán lugar a un mal algoritmo.
El límite entre lo que podemos considerar una función heurística razonable y otra que no lo
es va a venir dado por lo que denominamos admisibilidad de h()
Decimos que una función heurística es admisible si nunca sobreestima el verdadero coste de
llegar hasta un nodo destino. Es decir, una heurística es admisible si viene a ser optimista y en
ningún caso nos proporciona un coste superior al real.
El ejemplo de la distancia en línea recta que vimos para la búsqueda ávida es un ejemplo de heurística
admisible, ya que la distancia en línea recta siempre es inferior a cualquier otra distancia que
vayamos a tener que recorrer para llegar a cierto destino.
El concepto de heurística admisible es importante porque sucede que si, efectivamente, tenemos
planteado un problema de búsqueda A* con una heurística admisible, el algoritmo es óptimo y va a
encontrar la solución de menor coste.
Para ver que, efectivamente, la búsqueda A* es óptima con una heurística admisible podemos fijarnos en
que al principio del algoritmo la función de evaluación estará dominada por el coste de la
función heurística y es posible que el algoritmo investige ramas alejadas del óptimo. Pero a medida que el algoritmo
profundiza en el árbol de búsqueda, el valor de la función de evaluación estará dominado por el
coste real, como en la búsqueda con coste uniforme.
Si la heurística es admisible, no va a suceder que pueda enmascarar una solución óptima con un
coste estimado muy alto. Lo más que puede suceder es que proporcione costes muy bajos a ramas que realmente
no tienen coste óptimo, pero este efecto será menor en cada iteración a medida que el coste real domine la
función de evaluación y desaparezca el efecto de la heurística. Llegará un punto
en que el algoritmo se verá forzado a investigar la rama óptima y ya no volverá a ninguna otra, localizando
de esta forma la solución óptima.
Completitud de la búsqueda A*
De la misma forma que sucede en la búsqueda con coste uniforme, si sucede que todos los arcos
del árbol de búsqueda tienen cierto coste mínimo ε > 0 y también sucede que un nodo
no pueda tener infinitos descendientes la búsqueda A* es completa. Es decir, un algoritmo
basado en búsqueda A* que cumpla estas propiedades siempre va a localizar una solución, en forma de
camino desde el nodo origen a un nodo destino.
Básicamente, la completitud de la búsqueda A* está derivada directamente de la completitud en la
búsqueda con coste uniforme y por eso requerimos las mismas hipótesis en una y otra.
Ventajas adicionales de la búsqueda A*
Dada cierta función heurística admisible h(), se verifica que la búsqueda A* tiene eficiencia
óptima. Esto significa que no vamos a poder encontrar otro algoritmo para búsqueda heurística que nos garantice la optimalidad
y que lo haga expandiendo menos nodos que la búsqueda A*.
Esto es así porque un algoritmo que expanda menos nodos que la búsqueda A* corre el riesgo de
no localizar la solución óptima. Si la búsqueda A* expande un nodo es porque, con la información
disponible, hay posibilidades de que ese nodo conduzca al destino de forma óptima.
En general, la búsqueda A* tiene buenas propiedades en cuanto que garantiza resolver el problema
y lo hace de una forma eficiente. Pero, al igual que sucede con la búsqueda con coste uniforme,
su rendimiento puede resultar muy malo debido a su complejidad exponencial en tiempo y espacio.
Rendimiento de la búsqueda A*
El rendimiento de un algoritmo basado en búsqueda A* es básicamente el mismo que tiene el algoritmo
de búsqueda con coste uniforme, modificado en el sentido de lo acertada que sea la heurística
que usemos.
Sea la función h*(n) el coste mínimo real de una solución que pase por
el nodo n
Sea la función δ = (h* - h) / h*
La función δ será el error relativo de h()
respecto a h*()
Si δ = 0 entonces la función heurística es perfecta
En estas condiciones, el número de nodos que expandirá el algoritmo dependerá del error relativo
de la función heurística. Si tenemos error cero el algoritmo localizará la solución de
forma inmediata y si el error es 1 (función heurística nula) entonces el algoritmo estará
en las mismas condiciones que en una búsqueda ciega con coste uniforme.
La complejidad del algoritmo en tiempo y espacio será del orden de O(jδd),
donde j es el número promedio de descendientes en cada nodo y
d es la profundidad necesaria para llegar al destino en la solución
óptima.
Estas complejidades exponenciales significan que, a pesar de las bondades descritas, la búsqueda
A* no va a funcionar en problemas que desarrollen árboles de búsqueda muy grandes. Puede mejorar
enormemente respecto a la búsqueda con coste uniforme si tenemos una buena heurística, pero la complejidad
exponencial se mantiene y tampoco es razonable pensar que siempre vamos a conseguir definir
una buena heurística.
En problemas que tienen muchos nodos destino con múltiples soluciones de coste muy parecido
a la solución óptima, la búsqueda A* va a expandir secciones inmensas del árbol de búsqueda porque sólo es capaz de
averiguar cual es la solución óptima cuando la heurística es realmente buena o cuando está
cerca del destino. En problemas de este tipo el algoritmo fallará antes por exceso de
espacio que por exceso de tiempo y no va a haber ninguna ventaja respecto a la
búsqueda con coste uniforme, que también fallará por exceso de espacio.
La cuestión fundamental consiste en definir una heurística admisible que sea capaz de
guiar bien al algoritmo en las primeras iteraciones de forma que no expanda secciones
inmensas del árbol de búsqueda.
La búqueda A* es una mejora sobre la búsqueda con coste uniforme en la que la calidad
de la heurística definida juega un papel esencial. Con buenas heurísticas la búsqueda A*
puede resultar en algoritmos mejores que cualquier búsqueda sistemática.
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 A*.
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 |