Algoritmos de busqueda y

El problema de algunos algoritmos de búsqueda en grafos informados, como puede ser el algoritmo voraz, es que se guían en exclusiva por la función heurística, la cual puede no indicar el camino decoste 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 alcanzarla solución. 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 delrecorrido.
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 parallegar a dicho nodo, n, desde el nodo inicial. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad (ordenada por el valor  de cadanodo), 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 nodoobjetivo, calcula la  de todos sus hijos, los inserta 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 enprofundidad: 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.

Como todo algoritmo debú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 , nos encontramos ante una búsqueda voraz. Si paratodo 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...