A* (A-estrella)

A* (a-estrella) es un algoritmo de búsqueda informada que encuentra el camino de menor coste entre un punto inicial y un objetivo en un grafo. Lo publicaron Peter Hart, Nils Nilsson y Bertram Raphael en 1968. Combina lo mejor de dos estrategias: la garantía de optimalidad de la búsqueda de coste uniforme (el algoritmo de Dijkstra) y la rapidez de la búsqueda voraz guiada por una heurística.

La fórmula

En cada paso, A* expande el nodo con menor valor de f(n) = g(n) + h(n), donde g(n) es el coste real acumulado desde el inicio hasta ese nodo y h(n) es una estimación heurística del coste que falta hasta el objetivo. Así equilibra lo que ya ha costado llegar con lo que se estima que queda. Un ejemplo de heurística, en un mapa, es la distancia en línea recta al destino.

Cuándo garantiza el camino óptimo

A* encuentra el camino óptimo si la heurística es admisible, es decir, si nunca sobreestima el coste real que falta. Con una heurística consistente, una condición algo más fuerte, la garantía se mantiene también al reencontrar nodos por caminos distintos. Dos casos límite ayudan a entenderlo: si la heurística vale siempre cero, A* se reduce al algoritmo de Dijkstra; y si fuese perfecta, iría directo al objetivo sin explorar de más.

Usos y límite

A* es el estándar en el cálculo de rutas y la navegación (GPS), en el movimiento de personajes en videojuegos, en la planificación y en la resolución de puzles. Su principal límite es la memoria: guarda todos los nodos que va generando, y en problemas grandes puede agotarla. Para mitigarlo existen variantes como IDA*, que usa memoria lineal, o el A* ponderado, que sacrifica la optimalidad por velocidad.