Cómo funciona
Es Dijkstra con brújula. Para cada celda conoce g, lo que ya ha costado llegar, y
estima h, lo que falta: la distancia Manhattan al destino (columnas de diferencia más
filas de diferencia). La frontera se ordena por f = g + h, el coste total estimado de un
camino que pase por esa celda.
Las celdas que se alejan del destino tienen una h grande y esperan al fondo del estante; muchas nunca
llegan a salir. Como cada paso cuesta al menos 1, h nunca sobrestima lo que falta (es
admisible), y por eso el camino encontrado sigue siendo el más barato. En los empates de f
gana la celda con menor h, la más cercana al destino.
Paso a paso: la misma colina que Dijkstra
Mapa de 7 × 5 de A3 a G3 con una colina de peso 5 de C2 a E4. Al empezar, h(A3) = 6.
- 01Cierro A3 (f = 0 + 6 = 6): B3 entra con f = 1 + 5 = 6; A2 y A4, que se alejan, con f = 1 + 7 = 8.
- 02Cierro B3 (f = 6): C3 está en la colina: g = 1 + 5 = 6 y f = 6 + 4 = 10. B2 y B4 entran con f = 8. Se cierran las cuatro celdas con f = 8: B2, B4, A2 y A4.
- 03Con f = 10 hay muchos empates y gana la de menor h: C3 se asoma a la colina (D3 tendría f = 14) y la búsqueda sigue por arriba: B1, C1, D1, E1, F1, G1, G2 y G3.
- ΣCoste 10, como Dijkstra, cerrando 15 celdas en vez de 31. Las de abajo (B5, A5…) y el resto de la colina no llegan a salir del estante. El camino: A3 → B3 → B2 → B1 → … → G1 → G2 → G3.
La heurística decide
Con h = 0, A* es exactamente Dijkstra. Cuanto mejor estima h sin pasarse, menos celdas cierra. Si h
sobrestimara (por ejemplo, multiplicada por 2), iría más rápido pero podría devolver un camino más caro.
Por eso A* es el estándar en videojuegos y navegación: la distancia en línea recta (o Manhattan, en una
rejilla) es una h barata y admisible.
Complejidad
- Peor caso
- Como Dijkstra
- Con buena h
- Muchas menos celdas
- Memoria
- O(V)
- Óptimo
- Sí, h admisible
- h en rejilla
- |Δcol| + |Δfila|
- Estructura
- Cola de prioridad