Algoritmo de búsqueda A*

La heurística de búsqueda A* (pronunciado "A asterisco", "A estrella" o "A star" en inglés) se clasifica dentro de los algoritmos de búsqueda en grafos de tipo heurístico o informado.

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.

Es por ello bastante intuitivo el hecho de que un buen algoritmo de búsqueda informada debería tener en cuenta ambos factores, el valor heurístico de los nodos y el coste real del recorrido.

Así, el algoritmo A* utiliza una función de evaluación

representa el valor heurístico del nodo a evaluar desde el actual, n, hasta el final, y

A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad (ordenada por el valor

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

de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados.

Como todo algoritmo de búsqueda en amplitud, 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

debe ser heurística admisible, esto es, 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.

es consistente (o monótona), es decir, que para cualquier nodo

La complejidad computacional del algoritmo está íntimamente 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

Para que esto último suceda, se debe cumplir que donde h' es una heurística óptima para el problema, como por ejemplo, el coste real de alcanzar el objetivo.

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, como pueden ser RTA*, IDA* o SMA*.

que informa la distancia al nodo objetivo, entonces Si

=1 o constante la búsqueda será Primero en Anchura.

(o subestima), se garantiza encontrar el camino óptimo, pero se desperdicia esfuerzo explorando otras rutas que parecieron buenas.