El algoritmo A*

El algoritmo A* se utiliza para resolver problemas cuando se desean encontrar caminos mínimos entre una posición inicial origen y una final objetivo. Este algoritmo conocido también como A estrella fue propuesto por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael. Como ya se ha dicho es un algoritmo, o conjunto de pasos a dar para la solución de un problema, para solucionar problemas de pathfinding, búsqueda de caminos.

Es un algoritmo heurístico, basado en el estudio de las diversas opciones, que se ha utilizado mucho desde cuando se creó. Este algoritmo valora todas las opciones para cada movimiento proponiendo un camino ha seguir.

El mayor problema de este algoritmo es que precisa de mucha memoria para poder proponer soluciones ya que en cada paso evalúa todos los movimientos posibles proponiendo los más adecuados que en ocasiones pueden ser varios. Para problemas relativamente sencillos puede ser adecuado pero a medida que se complica el problema la necesidad de memoria crece exponencialmente.

Otro problema que puede presentar es que no es muy adecuado para problemas dinámicos o que varíen una vez empezado el análisis de la solución. Ya que el algoritmo asigna unos valores a cada celda en función de su proximidad o lejanía tanto desde el origen como al objetivo. Si variamos las condiciones parece que el resultado obtenido so sería el idóneo.

A medida que se consigan computadoras mas potentes y con mayor velocidad computacional puede ser que el algoritmo A* se capaz de resolver satisfactoriamente cada vez problemas mas complejos.

Referencias:

https://www.lanshor.com/pathfinding-a-estrella/

https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_A*

http://www.cs.umss.edu.bo/doc/material/mat_gral_139/Busqueda%20A%20estrella-2.pdf

http://www.cs.us.es/~fsancho/?e=42

Imagen:

https://malnuer.es/wp-content/uploads/2015/07/algoritmo_a_star.png