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:

• 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 sobre la búsqueda heurística y la búsqueda A*.