Algoritmo de Busqueda A estrella



Algoritmo de búsqueda A*

El algoritmo de búsqueda A* (pronunciado "A asterisco" o "A estrella") se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, el algoritmo A* encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo.Características Principales
Como todo algoritmo de búsqueda en anchura, A* es un algoritmo completo: en caso de existir una solución, siempre dará con ella.
Si para todo nodo n del grafo se cumple g(n) = 0, nos encontramos ante una búsqueda voraz. Si para todo nodo n del grafo se cumple h(n) = 0, A* pasa a ser una búsqueda de coste uniforme no informada.
Para garantizar la optimalidad delalgoritmo, la función h(n) debe ser admisible, o sea que no sobrestime el coste real de alcanzar el nodo objetivo.
De no cumplirse dicha condición, el algoritmo pasa a denominarse simplemente A, y a pesar de seguir siendo completo, no se asegura que el resultado obtenido sea el camino de coste mínimo. Asimismo, si garantizamos que h(n) es consistente (o monótona), es decir, que para cualquier nodo n ycualquiera de sus sucesores, el coste estimado de alcanzar el objetivo desde n no es mayor que el de alcanzar el sucesor más el coste de alcanzar el objetivo desde el sucesor.
La complejidad computacional está relacionada con la calidad de la heurística que se utilice en el problema. En el caso peor, con una heurística de pésima calidad, la complejidad será exponencial, mientras que en el caso mejor,con una buena h'(n), el algoritmo se ejecutará en tiempo lineal.
El espacio requerido por A* para ser ejecutado es su mayor problema. Dado que tiene que almacenar todos los posibles siguientes nodos de cada estado, la cantidad de memoria que requerirá será exponencial con respecto al tamaño del problema. Para solucionar este problema, se han propuesto diversas variaciones de este algoritmo, comopueden ser RTA*, IDA* o SMA*.
El rendimiento de los algoritmos de búsqueda heurística depende de la calidad de la función heurística.


¿Cómo funciona A*?
Este algoritmo utiliza una función de evaluación f(n) = g(n) + h'(n), donde h'(n) representa el valor heurístico del nodo a evaluar desde el actual, n, hasta el final, y g(n), el costo real del camino recorrido para llegar a dicho nodo, n. A*mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad ordenada por el valor f(n) de cada nodo, y cerrados, donde se guarda la información de los nodos que ya han sido visitados. En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en caso de que no sea un nodo objetivo, calcula la f(n) de todos sus hijos, losinserta en abiertos, y pasa el nodo evaluado a cerrados. El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad: mientras que h'(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que existen nodos más prometedores.
Función heurística de A*
f (n) = g(n) + h(n): Coste real delplan (camino) de mínimo coste que pasa por n.
f* (n) = g(n) + h*(n): estimación de f.
Estrategia de A*
Entre las hojas del árbol de búsqueda, elegir el nodo de valor f* mínimo.
Interpretación fuerte de A*
Una heurística suele facilitar la resolución de un problema, pero no garantiza que se resuelva.
Una heurística es una regla de tres para un problema.
Búsqueda: Optimalidad o incluso completitud nogarantizados.
Esquematización de A*
Se basa en la búsqueda general.
Almacenar el valor g de cada nodo expandido.
Mantener la estructura abierta ordenada por valores crecientes de f*.
Insertar nuevos nodos en la estructura abierta según sus valores de f*.






Pseudocódigo


Tratar Punto
// coste del camino hasta .

caso . = . perteneciente a ()
si g(.) < g(.) entonces // (-----)
// nos...