algoritmo 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.
Índice  [ocultar] 
1 Motivación y descripción
2 Propiedades
3 Complejidad computacional
4 Complejidad en memoria
5 Implementación en pseudocódigo
5.1 Tratar punto
5.2 Implementación en pseudocódigo
5.3 TRATAR_SUCESOR
6 Observaciones
7 Enlaces externos
Motivación y descripción[editar · editar código]
El problema de algunos algoritmos de búsqueda en grafos informados, como puede ser el algoritmo voraz, esque se guían en exclusiva por la función heurística, la cual puede no indicar el camino de coste más bajo, o por el coste real de desplazarse de un nodo a otro (como los algoritmos de escalada), pudiéndose dar el caso de que sea necesario realizar un movimiento de coste mayor para alcanzar la solución. Es por ello bastante intuitivo el hecho de que un buen algoritmo de búsqueda informada deberíatener 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 , donde  representa el valor heurístico del nodo a evaluar desde el actual, n, hasta el final, y , el coste real del camino recorrido para llegar a dicho nodo, n, desde el nodo inicial. A* mantiene dos estructuras de datos auxiliares, que podemosdenominar 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.
Elalgoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad: mientras que  tiende a primero en profundidad,  tiende a primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que existen nodos más prometedores.
Propiedades[editar · editar código]
Como todo algoritmo de búsqueda en amplitud, A* es un algoritmo completo: en caso de existir unasolución, siempre dará con ella.
Si para todo nodo n del grafo se cumple , nos encontramos ante una búsqueda voraz. Si para todo nodo n del grafo se cumple , A* pasa a ser una búsqueda de coste uniforme no informada.
Para garantizar la optimalidad del algoritmo, la función  debe ser heurística admisible, esto es, que no sobrestime el coste real de alcanzar el nodo objetivo.
De no cumplirsedicha 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  es consistente (o monótona), es decir, que para cualquier nodo  y cualquiera de sus sucesores, el coste estimado de alcanzar el objetivo desde n no es mayor que el de alcanzar el sucesor más el costede alcanzar el objetivo desde el sucesor.
Complejidad computacional[editar · editar código]
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 , el algoritmo se ejecutará en tiempolineal. 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.
Complejidad en memoria[editar · editar código]
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...