Algoritmo de búsqueda A* explicado: cómo funciona, código y complejidad

Qué problema resuelve A*

El algoritmo de Dijkstra expande los nodos en anillos de distancia creciente en todas las direcciones, incluso en las que se alejan de la meta. Cuando sabes dónde está la meta, eso es trabajo desperdiciado. A* añade una heurística, una estimación de la distancia que falta, de modo que la búsqueda se ve atraída hacia la meta. Es el algoritmo estándar para la búsqueda de caminos en videojuegos, robótica y mapas.

A* fue descrito por Peter Hart, Nils Nilsson y Bertram Raphael en 1968 en "A Formal Basis for the Heuristic Determination of Minimum Cost Paths".

La idea en palabras sencillas

1. Pon el nodo inicial en una cola de prioridad (el conjunto abierto) con g = 0 y f = h(inicio).
2. Extrae el nodo con menor f. Si es la meta, reconstruye el camino y termina.
3. Para cada vecino, calcula un g provisional = g(actual) + coste de la arista. Si mejora el g conocido del vecino, regístralo, asigna el padre e inserta el vecino con f = g + h.
4. Si el conjunto abierto queda vacío, no hay camino.

Con h(n) = 0 para todos los nodos, A* se convierte exactamente en el algoritmo de Dijkstra. Con una heurística perfecta, avanza en línea recta por un camino óptimo.

Elegir una heurística

Una heurística es admisible si nunca sobrestima el coste restante real. Es consistente (o monótona) si h(n) <= cost(n, m) + h(m) para toda arista n → m. Las heurísticas consistentes también son admisibles y, con ellas, cada nodo solo necesita expandirse una vez.

Implementación en Python sobre una cuadrícula

La cuadrícula siguiente tiene 5 filas y 7 columnas; # marca una pared en la columna 5. Las celdas son (row, column). Los movimientos son arriba, abajo, izquierda y derecha con coste 1, así que la distancia Manhattan es admisible y consistente.

import heapq
def a_star(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    h = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])
    g = {start: 0}
    parent = {start: None}
    open_heap = [(h(start), start)]
    while open_heap:
        f, cur = heapq.heappop(open_heap)
        if cur == goal:
            path = []
            while cur is not None:
                path.append(cur)
                cur = parent[cur]
            return path[::-1]
        if f > g[cur] + h(cur):
            continue                      # outdated entry
        r, c = cur
        for nb in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nb[0] < rows and 0 <= nb[1] < cols and grid[nb[0]][nb[1]] != "#":
                ng = g[cur] + 1
                if ng < g.get(nb, float("inf")):
                    g[nb] = ng
                    parent[nb] = cur
                    heapq.heappush(open_heap, (ng + h(nb), nb))
    return None
grid = [".......",
        ".....#.",
        ".....#.",
        ".....#.",
        "......."]
path = a_star(grid, (2, 3), (2, 6))
print(len(path) - 1, path)
# 7 [(2, 3), (2, 4), (1, 4), (0, 4), (0, 5), (0, 6), (1, 6), (2, 6)]

Ejemplo resuelto, paso a paso

En la cuadrícula anterior, el inicio (2, 3) está a 3 pasos de la meta (2, 6) en línea recta, así que el primer f es 0 + 3 = 3. La pared bloquea esa línea y el camino más corto real tiene 7 pasos. A* lo descubre por etapas: expande todas las celdas con el menor f y, cuando se agotan, las del siguiente f más pequeño.

A* expandió 15 de las 32 celdas abiertas. El algoritmo de Dijkstra (A* con h = 0) expande las 32, porque cada celda abierta está como mucho a 7 pasos del inicio. En mapas grandes y abiertos el ahorro es mucho mayor.

Complejidad temporal y espacial

Entre las variantes que ahorran memoria está IDA* (A* con profundización iterativa), que guarda solo el camino actual a costa de revisitar nodos.

Cuándo usar A* y usos en el mundo real

• Usa A* cuando hay una sola meta y una estimación barata y admisible del coste restante, como la distancia geométrica en un mapa.
• Usa Dijkstra cuando necesites distancias a muchos o a todos los nodos, o cuando no exista una heurística útil. Usa BFS en grafos sin pesos, donde una heurística aporta poco beneficio.
• Videojuegos: movimiento de unidades en mapas de casillas y mallas de navegación.
• Robótica y planificación de rutas, a menudo combinadas con puntos de referencia o jerarquías precalculados.
• Resolución de rompecabezas: el 8-puzzle y el 15-puzzle con la distancia Manhattan de las fichas como heurística.