A (A-star)* es un algoritmo de búsqueda de caminos que combina Dijkstra (costo real acumulado) con una heurística (estimación al objetivo). Es óptimo y más eficiente que Dijkstra porque guía la búsqueda hacia el objetivo.

Es el algoritmo estándar en videojuegos, robótica, y sistemas de navegación.

Función de Evaluación

f(n) = g(n) + h(n)

• g(n): costo real desde start hasta n.
• h(n): estimación heurística desde n hasta goal.
• f(n): costo total estimado del camino start → ... → n → goal.

Heurística Admisible

Una heurística es admisible si nunca sobrestima el costo real: h(n) ≤ costo_real(n, goal) para todo n.

Si h(n) es admisible, A es óptimo*: encuentra el camino de menor costo.

Heurística Consistente

Una heurística es consistente (monotónica) si para cada arista (n, a):

h(n) ≤ c(n, a) + h(a)

Si es consistente, g(n) siempre aumenta, y no necesitamos re-procesar nodos.

Ejemplo: Grid con Manhattan Distance

Grid con obstáculos, start=(0,0), goal=(4,4).

h(n) = |n.x - goal.x| + |n.y - goal.y| (Manhattan distance).

A* explora menos nodos que Dijkstra porque h guía hacia el goal.

Comparación

Aplicaciones

• Videojuegos — pathfinding de personajes (NPCs)
• Robótica — navegación autónoma
• Sistemas de navegación — Google Maps, Waze
• Planificación — movimiento en espacios continuos
• Enseñanza — introduce heurísticas y best-first search

Casos Extremos

• h(n) = 0 — A* se convierte en Dijkstra.
• h(n) = costo_real — explora solo el camino óptimo.
• h(n) > costo_real — no admisible, puede ser más rápido pero no óptimo.
• Weighted A* — multiplica h por w > 1: más rápido pero subóptimo.

Trayectoria de Práctica

1. Implementa A* en un grid 2D; traza la exploración.
2. Prueba con Manhattan distance y Euclidean distance.
3. Verifica optimalidad comparando con Dijkstra.
4. Investiga weighted A*: ¿cómo afecta w > 1?
5. Investiga D* Lite: ¿para qué se usa en robótica?