“El algoritmo de búsqueda A* se clasifica dentro de los algoritmos de búsqueda informada (que posee una información extra sobre la estructura del espacio en el que se realiza la búsqueda). Fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, siguiendo el esquema de utilizar una función heurística junto al cálculo del coste real del camino recorrido, y siempre y cuando se cumplan unas determinadas condiciones, calcula el camino de menor coste entre el origen y el objetivo.”
La heurística -“hallar, inventar“- como metodología científica incluye la elaboración de medios auxiliares, principios, reglas, estrategias y programas que faciliten la búsqueda de vías de solución a problemas.
El algoritmo A* utiliza la función de evaluación siguiente:
f(n) = g(n) + h’
donde h′(n) representa el valor heurístico del nodo a evaluar desde el actual, n, hasta el final, y g(n), el coste real del camino recorrido para llegar a dicho nodo, n, desde el nodo inicial.
Sin embargo, este algoritmo no sería aplicable cuando el coste es no asumible; tampoco en el caso de que no se minimice la heurística, es decir, cuando el heurístico no tiene solución mínima. Esto puede ser porque no haya solución a la función porque nunca llega al punto final definido, bien porque cae en un agujero que lo aleja (diverge) o bien porque llega a puntos en los que ya no puede avanzar más (converge o llega en otros puntos diferentes al final y se para).
En el caso de un juego en el que queremos pasar de un punto a otro rodeando de obstáculos, cuando los obstáculos no nos dejan un camino posible para llegar al punto final, o cuando tenemos un agujero al que caemos, no podremos llegar a la solución.
Por tanto, para poder utilizar el algoritmo A* se deberán cumplir las condiciones de coste y heurística mínimas o asumibles.
zIENtzia 