Algoritmo A*

En ciencias de la computación, A* (estrella) es un algoritmo informático que fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael. Es un algoritmo muy utilizado para buscar una ruta posible y eficiente entre dos puntos. Esta ruta que ha de tener el menor coste posible se produce entre un origen y un destino llamados nodos.

A* es un algoritmo heurístico, ya que hará uso de una función de evaluación heurística. Esta que es una de sus principales características se basa en que etiqueta los diferentes nodos de la red según el coste de llegar al objetivo. Esta forma de etiquetar los nodos está compuesta a su vez por otras dos funciones: 1) una muestra la distancia actual desde el nodo origen hasta el nodo a etiquetar, y  2) la otra indica la distancia desde este nodo a etiquetar hasta el nodo destino. Esto le sirve, en función de los valores obtenidos, de establecer la probabilidad que tienen los nodos de la red de formar parte de la ruta más eficiente. Existen diferentes heurísticas, pero solo son admisibles si nunca sobreestiman el coste de alcanzar el objetivo. Es decir, solo son válidas cuando en el punto actual la estimación del coste de alcanzar el objetivo nunca es mayor que el menor coste posible.

El algoritmo A* solo puede utilizarse cuando se cumplen unas determinadas condiciones. Además, hay situaciones donde podría no funcionar bien por diferentes razones. Una desventaja práctica muy importante del algoritmo A* es su necesidad de almacenamiento ya que guarda en su memoria todos los nodos generados. Otra de sus limitaciones es cuando existen factores dinámicos, es decir, cuando el terreno es modificable o existen objetos móviles. Por ejemplo, algunos videojuegos que tienen mapas muy grandes son muy exigentes en cuando a requerimientos en tiempo real, así como en cuanto a almacenamiento de datos y tiempo de procesador. Aunque hubiera suficiente memoria para realizar los cálculos, podría ser que estos fueran ineficientes e inadecuados.