Un personaje de videojuego que rodea una pared para llegar hasta ti, un robot que cruza un almacén esquivando estanterías, un programa que resuelve un laberinto: detrás de muchos de ellos está el mismo algoritmo, A* (se lee «A estrella»). Su truco es sencillo: en vez de explorar a ciegas en todas direcciones, en cada paso mira cuánto ha recorrido y cuánto le falta, y avanza por donde promete. Aquí lo verás buscar en un mapa que tú mismo puedes dibujar, y compararlo con otros dos métodos.
Un robot que necesitaba moverse
A finales de los años sesenta, en el Stanford Research Institute (hoy SRI International), un equipo construía Shakey, el primer robot móvil capaz de razonar sobre lo que hacía. Para moverse por sus salas necesitaba planificar rutas, y de ahí salió A*. Nils Nilsson propuso primero usar un método ya existente, Graph Traverser; Bertram Raphael sugirió puntuar cada posición sumando lo ya recorrido y una estimación de lo que faltaba, y Peter Hart puso la base matemática: demostró en qué condiciones el método encuentra siempre el camino más corto. Los tres lo publicaron en 1968 con el título «A Formal Basis for the Heuristic Determination of Minimum Cost Paths».
Partían de un algoritmo anterior, el de Edsger Dijkstra. Dijkstra lo ideó en 1956, según contó, sentado en la terraza de un café de Ámsterdam mientras iba de compras con su novia: «un invento de veinte minutos», hecho sin papel ni lápiz. Lo usó para calcular rutas en un mapa simplificado de 64 ciudades de los Países Bajos en el ordenador ARMAC, y lo publicó en 1959. Encuentra siempre el camino más corto, pero sin ninguna pista de hacia dónde está la meta.
La idea: lo recorrido más lo que falta
Los tres métodos de este artículo funcionan igual por fuera. Tienen una cola de casillas pendientes, empezando por la salida. En cada paso sacan de la cola la casilla más prometedora, la exploran y meten en la cola sus vecinas libres. Lo único que cambia es qué entienden por «más prometedora»:
- Dijkstra elige la casilla más cercana a la salida. Avanza como una mancha de aceite, igual hacia todos lados, y por eso explora muchísimo.
- La búsqueda voraz elige la que parece más cercana a la meta. Va derecha hacia ella, pero no tiene en cuenta lo que lleva recorrido, y se puede meter en un callejón y acabar con un camino más largo.
- A* suma las dos cosas: f = g + h, donde g son los pasos recorridos desde la salida y h una estimación de los que faltan hasta la meta.
En una cuadrícula en la que solo se puede ir arriba, abajo, a la izquierda y a la derecha, la estimación más habitual es la distancia Manhattan: las columnas más las filas que separan una casilla de la meta, como si no hubiera muros. Se llama así por las calles en cuadrícula de Nueva York, donde no se puede cortar en diagonal.
Pruébalo
Elige un algoritmo y un mapa, y pulsa «Paso» para ver cada casilla explorada o «Reproducir» para verlas seguidas. Con el ratón puedes dibujar muros directamente sobre la cuadrícula; en el móvil, elige antes una herramienta (pulsa otra vez para soltarla y que la página vuelva a desplazarse). «Salida» y «Meta» las mueven a la casilla que toques. Debajo de la cuadrícula verás cómo les va a los tres algoritmos en el mapa que tengas en ese momento.
- salida
- meta
- en la cola
- explorada
- explorando
- muro
Prueba el mapa «Vacío» con los tres: Dijkstra explora un rombo cada vez más grande hasta tocar la meta; A* y la voraz van casi en línea recta. Después, cierra con muros el lado derecho de la bolsa y verás que la voraz se mete dentro antes de darse cuenta. En el «Laberinto», en cambio, las tres exploran casi lo mismo: cuando solo hay un camino posible, ninguna pista ayuda mucho.
Tres formas de buscar, el mismo mapa
Este es el mapa con el que empieza la animación, en su versión pequeña: una bolsa abierta hacia la salida, justo entre ella y la meta. Los números salen del programa de Python que hay más abajo.
Por qué A* no se equivoca
La garantía de A* depende de una condición: que la estimación h no exagere nunca, es decir, que nunca diga que faltan más pasos de los que de verdad faltan. A esa estimación se le llama admisible. La distancia Manhattan lo es en esta cuadrícula, porque un muro solo puede alargar el camino, nunca acortarlo. Con una h admisible, A* nunca da por bueno un camino más largo que el óptimo: mientras quede en la cola una casilla que podría llevar a algo mejor, su f será menor y la explorará antes.
Si además la estimación es consistente (al dar un paso, h no baja más de lo que cuesta ese paso, algo que la distancia Manhattan también cumple), A* no necesita explorar ninguna casilla dos veces. Y en 1985, Rina Dechter y Judea Pearl demostraron que, con una h consistente y salvo casos rebuscados, ningún método de su misma familia que garantice el camino óptimo puede explorar menos casillas.
Los dos extremos también encajan en la fórmula: Dijkstra es A* con h = 0, una estimación que no ayuda pero que tampoco exagera, así que sigue siendo exacto. La voraz es lo contrario: solo mira h, y pierde la garantía. Si la cuadrícula permitiera moverse en diagonal, la distancia Manhattan dejaría de valer, porque exageraría, y habría que usar otra estimación, como la distancia en línea recta.
Este programa en Python hace las tres búsquedas con la biblioteca estándar, usando heapq como cola de prioridad. Cada entrada de la cola lleva la prioridad, un desempate (a igual f, A* prefiere la casilla más cercana a la meta) y un contador para que, en caso de empate total, salga primero la que entró antes:
"""A*, Dijkstra y búsqueda voraz en una cuadrícula, solo con la biblioteca estándar."""
import heapq
MAPA = """
..................
..........#.......
.S........#.......
..........#.......
.....######.......
..................
..................
.............G....
..................
"""
def leer(texto):
filas = texto.strip().splitlines()
celdas = {(x, y): c for y, fila in enumerate(filas) for x, c in enumerate(fila)}
muros = {p for p, c in celdas.items() if c == "#"}
inicio = next(p for p, c in celdas.items() if c == "S")
meta = next(p for p, c in celdas.items() if c == "G")
return len(filas[0]), len(filas), muros, inicio, meta
def buscar(ancho, alto, muros, inicio, meta, modo="astar"):
def h(p): # distancia Manhattan: sin diagonales, nunca sobrestima lo que falta
return abs(p[0] - meta[0]) + abs(p[1] - meta[1])
def prioridad(g, p):
if modo == "dijkstra":
return (g, 0) # solo lo recorrido
if modo == "voraz":
return (h(p), h(p)) # solo lo que falta
return (g + h(p), h(p)) # A*: f = g + h; con empate, la más cercana a la meta
g, padre, vistas, orden = {inicio: 0}, {}, set(), []
cola, turno = [(*prioridad(0, inicio), 0, inicio)], 1
while cola:
actual = heapq.heappop(cola)[-1]
if actual in vistas:
continue # entrada vieja: ya se expandió con un coste menor
vistas.add(actual)
orden.append(actual)
if actual == meta:
break
x, y = actual
for v in ((x, y - 1), (x + 1, y), (x, y + 1), (x - 1, y)):
if not (0 <= v[0] < ancho and 0 <= v[1] < alto) or v in muros or v in vistas:
continue
if g[actual] + 1 < g.get(v, float("inf")):
g[v], padre[v] = g[actual] + 1, actual
heapq.heappush(cola, (*prioridad(g[v], v), turno, v))
turno += 1
if meta not in vistas:
return None, orden
camino = [meta]
while camino[-1] != inicio:
camino.append(padre[camino[-1]])
return camino[::-1], orden
def dibujar(ancho, alto, muros, inicio, meta, camino, orden):
filas = []
for y in range(alto):
fila = ""
for x in range(ancho):
p = (x, y)
fila += ("S" if p == inicio else "G" if p == meta else "#" if p in muros
else "*" if p in camino else "·" if p in orden else ".")
filas.append(fila)
return "\n".join(filas)
if __name__ == "__main__":
ancho, alto, muros, inicio, meta = leer(MAPA)
print(f"Mapa de {ancho}×{alto}, de {inicio} a {meta}\n")
for modo, nombre in (("dijkstra", "Dijkstra"), ("astar", "A*"), ("voraz", "Voraz")):
camino, orden = buscar(ancho, alto, muros, inicio, meta, modo)
print(f"{nombre:9} camino de {len(camino) - 1} pasos, {len(orden)} casillas exploradas")
for modo, nombre in (("astar", "A*"), ("voraz", "Voraz")):
camino, orden = buscar(ancho, alto, muros, inicio, meta, modo)
print(f"\n{nombre} (* camino, · explorada):")
print(dibujar(ancho, alto, muros, inicio, meta, camino, orden))salidaMapa de 18×9, de (1, 2) a (13, 7) Dijkstra camino de 17 pasos, 125 casillas exploradas A* camino de 17 pasos, 28 casillas exploradas Voraz camino de 21 pasos, 27 casillas exploradas A* (* camino, · explorada): .................. ..........#....... .S***·····#....... ....*·····#....... ....*######....... ....**********.... .............*.... .............G.... .................. Voraz (* camino, · explorada): .........*****.... ........·*#..*.... .S********#..*.... ......····#..*.... .....######..*.... .............*.... .............*.... .............G.... ..................
Hemos comprobado que la animación de arriba hace exactamente las mismas cuentas: en 601 mapas, el de este ejemplo y 600 al azar de distintos tamaños y con distinta cantidad de muros, explora las mismas casillas, en el mismo orden, y devuelve el mismo camino que el programa de Python con los tres algoritmos. Además, A* y Dijkstra dieron siempre el camino más corto, y la voraz dio uno más largo en 59 de esos mapas.
Dónde se usa
A* es el método clásico para que los personajes de los videojuegos encuentren su camino, normalmente sobre una cuadrícula o una red de puntos por los que se puede pasar. También se usa en robótica, donde nació, para planificar trayectorias. En los navegadores de carretera, con mapas de millones de cruces, los sistemas actuales suelen preferir métodos que preparan el mapa de antemano y luego responden mucho más rápido, aunque muchos siguen siendo parientes de A* y de Dijkstra.
Su punto débil es la memoria: guarda todas las casillas que ha visto, y en problemas enormes eso no cabe. De ahí salieron variantes que gastan menos memoria a cambio de repetir trabajo, como IDA*.
Si te gustan los algoritmos que se entienden mejor viéndolos, tenemos más con animación: el código Huffman, que comprime un texto dando menos bits a las letras más usadas, el algoritmo de Myers, con el que Git encuentra las diferencias entre dos archivos, los epiciclos de Fourier y los boids.
Fuentes: P. E. Hart, N. J. Nilsson y B. Raphael, «A Formal Basis for the Heuristic Determination of Minimum Cost Paths», IEEE Transactions on Systems Science and Cybernetics 4(2), 100–107 (1968); E. W. Dijkstra, «A note on two problems in connexion with graphs», Numerische Mathematik 1, 269–271 (1959); la historia de los dos algoritmos y la entrevista de Dijkstra de 2001, en Wikipedia (A* y Dijkstra); R. Dechter y J. Pearl, «Generalized best-first search strategies and the optimality of A*» (1985). El programa se ejecutó con Python 3.13 y la comparación, con Node.js 22. La animación, los esquemas y la portada: decodigo.com.