Búsqueda A*

Qué cubre este capítulo

Dijkstra encuentra el camino más corto, pero lo hace a ciegas: sin idea de dónde está la meta, explora hacia afuera en todas direcciones por igual, fijando nodos en un círculo que crece hasta que el destino cae dentro por casualidad. Cuando sí sabes a dónde vas — un destino en un mapa, una casilla objetivo en un juego — eso es un desperdicio. A* es Dijkstra con sentido de orientación. Mantiene una estimación de qué tan lejos sigue estando cada nodo de la meta y usa esa estimación para dirigir la búsqueda, así que avanza hacia el objetivo en lugar de inundar todo alrededor. Con una estimación bien elegida encuentra exactamente el mismo camino más corto que Dijkstra, pero expandiendo una fracción mínima de los nodos — en la prueba de rejilla abierta de este capítulo, como una décima parte. Aquí lo construimos, vemos cómo su frontera se estira hacia la meta en un laberinto, y dejamos clara la única propiedad que la estimación debe cumplir para que sobreviva la garantía de camino más corto.

Un poco de historia

A* se publicó en 1968 por Peter Hart, Nils Nilsson y Bertram Raphael en el Stanford Research Institute, donde se inventó para guiar a Shakey, el robot — uno de los primeros robots móviles capaces de razonar sobre sus propias acciones — mientras planeaba rutas por un cuarto lleno de obstáculos. Su artículo hizo algo importante más allá de dar un algoritmo: demostró que A* es óptimamente eficiente. Entre todos los algoritmos que usan la misma información heurística y garantizan encontrar un camino más corto, ninguno puede expandir menos nodos que A*. Es una afirmación fuerte — dice que la idea de "distancia recorrida más estimación de lo que falta" no es solo una buena heurística, es el mejor uso posible de esa heurística. El nombre es literalmente "A estrella": sus algoritmos anteriores se llamaban A1, A2, y así, y como demostraron que este era óptimo, se ganó la estrella. Desde entonces ha sido la columna vertebral de la IA en videojuegos y de la navegación robótica, y se apoya directamente sobre Dijkstra — que esa misma comunidad ya tenía desde 1959 — como "Dijkstra más una heurística".

La intuición

Dijkstra elige el siguiente nodo a expandir usando solo $g(n)$ — la distancia más barata desde el inicio hasta ese momento. Por eso crece como un círculo uniforme: siempre expande el nodo sin fijar más cercano al inicio, sin importar la dirección. A* agrega un segundo término. Para cada nodo también calcula $h(n)$, una estimación heurística de la distancia restante de $n$ a la meta, y ordena su priority queue por la suma $f(n) = g(n) + h(n)$ — la longitud total estimada de un camino que pase por $n$. Ahora el nodo que expande después no es el más cercano al inicio, sino el que está en el camino más prometedor hacia la meta. En una rejilla, si la meta está al este, un nodo que ya avanzó de verdad hacia el este se ve mejor que otro a la misma distancia del inicio pero hacia el norte, porque su $h$ es menor. La búsqueda se alarga hacia el objetivo.

La heurística depende del problema y es donde vive la inteligencia. En una rejilla donde solo puedes moverte en las cuatro direcciones cardinales, la estimación natural es la distancia Manhattan — el número de filas más columnas que separan un nodo de la meta — porque es imposible llegar a la meta en menos pasos unitarios que esos. Esa última cláusula es la propiedad crucial: la estimación nunca debe afirmar que la meta está más lejos de lo que realmente está. Subestimar (o acertar exacto) está bien; sobreestimar no, y el deep dive explica por qué. Pon $h(n) = 0$ en todas partes — la estimación trivial de "no tengo idea de qué tan lejos está la meta" — y entonces $f(n) = g(n)$, y A* se convierte en Dijkstra exactamente. La heurística es toda la diferencia entre los dos algoritmos, y una mejor heurística significa una búsqueda más angosta y más rápida.

Complejidad: cómo escala

El peor caso de A* es el mismo que el de Dijkstra — con una heurística inútil puede expandir todos los nodos, dando $O(E \log V)$ — así que su Big-O no captura lo que lo hace rápido. Lo que importa es cuántos nodos expande realmente, y eso depende por completo de la calidad de la heurística. Ese es el duelo: A* y Dijkstra encontrando el mismo camino más corto en rejillas de tamaño creciente, contando nodos expandidos:

Ambos algoritmos regresan exactamente el mismo camino óptimo — la verificación de correctitud confirma que el costo de A* siempre es igual al de Dijkstra — pero hacen cantidades de trabajo salvajemente distintas para lograrlo. En una rejilla de 3600 celdas, Dijkstra expandió unos 3200 nodos (casi toda la rejilla, con su círculo inflándose hasta tragarse la meta), mientras que A* expandió alrededor de 290 — como once veces menos, porque la heurística Manhattan lo mantuvo marchando hacia el objetivo en lugar de explorar detrás y a los lados del inicio. La brecha crece con el tamaño de la rejilla, que es exactamente por lo que A* domina el pathfinding real: entre más grande el mundo, más desperdicia Dijkstra en direcciones que se alejan de a dónde vas, y más ahorra una heurística.

En qué es bueno y en qué no

A* es la herramienta correcta para caminos más cortos hacia una meta conocida cuando tienes una heurística decente — que es la mayoría del pathfinding real. Personajes de videojuegos navegando un mapa, robots planeando movimiento, ruteo de GPS (con heurísticas como la distancia en línea recta), solucionadores de puzzles (el 15-puzzle y el cubo de Rubik, con heurísticas que cuentan fichas mal colocadas), y cualquier problema de "llegar de aquí a allá eficientemente" en un espacio de estados grande. Cuando la heurística es buena, A* explora una fracción mínima de lo que exploraría Dijkstra, y nunca sacrifica la optimalidad para lograrlo, siempre que la heurística sea admisible.

Donde A* no ofrece nada es cuando no hay una meta única o no hay heurística útil. Si necesitas distancias a todos los nodos, o estás explorando sin un objetivo, la heurística es $0$ y A* es solo Dijkstra con papeleo extra — usa Dijkstra. Si no puedes estimar la distancia restante (un grafo abstracto sin geometría), lo mismo. A* también asume pesos de arista no negativos, heredando eso de Dijkstra. Y una heurística pobre puede hacerlo apenas más rápido que Dijkstra mientras cuesta más por nodo; una heurística deshonesta (que sobreestima) lo hace aún más rápido pero regresa caminos no óptimos en silencio — a veces es un intercambio aceptable (el A* ponderado hace exactamente esto a propósito), pero es una trampa si no era tu intención.

Los datos, o las entradas

El duelo corre sobre rejillas aleatorias de tamaño creciente con cerca del 10% de las celdas bloqueadas, y cuenta cuántos nodos expanden A* (con la heurística Manhattan) y Dijkstra (sin heurística) para encontrar el mismo camino más corto de esquina a esquina. La verificación de correctitud confirma, en cientos de rejillas aleatorias, que el costo del camino de A* siempre iguala el óptimo de Dijkstra y que el camino devuelto es una secuencia realmente conectada y de la longitud correcta. La animación corre A* en un laberinto fijo con dos paredes escalonadas, para que veas cómo la frontera se dobla alrededor de los obstáculos sin dejar de estirarse hacia la meta en la esquina opuesta.

Constrúyelo, una función a la vez

La búsqueda en sí — una priority queue ordenada por f = g + h, con el desempate que se pega a la meta:

def astar(adj, start, goal, h):
    """Cheapest path from start to goal over non-negative weighted edges, guided by heuristic
    h[n] (an estimate of the remaining distance from n to goal). The priority queue is ordered
    by f = g + h, so nodes that look closer to the goal are explored first. With an admissible
    h (never an overestimate) the first time we pop `goal` we have its true shortest distance.
    Returns (path, cost, expanded) where `expanded` counts nodes settled — the work done."""
    g = {start: 0}
    parent = {start: None}
    # Priority is (f, -g): order by f = g + h, and among equal f prefer the LARGER g — i.e.
    # the node already closer to the goal. This admissible tie-break makes A* hug a straight
    # line to the target instead of fanning across a plateau of equal-f nodes on open grids.
    pq = [(h[start], 0, start)]              # (f, -g, node)
    settled = set()
    expanded = 0
    while pq:
        f, neg_g, u = heapq.heappop(pq)
        if u in settled:
            continue
        settled.add(u)
        expanded += 1
        gu = -neg_g
        if u == goal:                        # popped the goal → its distance is final
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return path[::-1], gu, expanded
        for v, w in adj[u]:
            ng = gu + w
            if ng < g.get(v, float("inf")):  # a cheaper way to v → relax and re-prioritize
                g[v] = ng
                parent[v] = u
                heapq.heappush(pq, (ng + h[v], -ng, v))
    return None, float("inf"), expanded

Convertir una rejilla con paredes en un grafo, y la heurística Manhattan admisible para ella:

def grid_graph(rows, cols, walls):
    """Turn a grid with blocked cells into a weighted adjacency list (4-connected, unit
    edges). Cells are numbered r*cols + c; `walls` is a set of (r, c) that can't be entered."""
    def nid(r, c):
        return r * cols + c

    adj = {}
    for r in range(rows):
        for c in range(cols):
            if (r, c) in walls:
                continue
            nbrs = []
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in walls:
                    nbrs.append((nid(nr, nc), 1))
            adj[nid(r, c)] = nbrs
    return adj


def manhattan(rows, cols, goal):
    """The admissible, consistent heuristic for a 4-connected unit grid: the straight-line
    grid distance (|Δrow| + |Δcol|) to the goal. It never overestimates, because you can't
    reach the goal in fewer than that many unit steps."""
    gr, gc = divmod(goal, cols)
    return {r * cols + c: abs(r - gr) + abs(c - gc) for r in range(rows) for c in range(cols)}

Míralo funcionar

Aquí está A* resolviendo un laberinto desde la esquina superior izquierda (morado) hasta la inferior derecha (rojo), con dos paredes escalonadas que tiene que rodear. Las celdas azules son el open set — descubiertas, esperando en la priority queue; las grises están cerradas — ya expandidas; la naranja es el nodo que se está expandiendo en ese paso. Fíjate en la forma de la exploración: no se esparce parejo como lo haría el círculo de Dijkstra — se estira hacia la meta en la esquina lejana, abultándose solo donde una pared lo obliga a desviarse, para luego volver de golpe a la línea recta. Cuando por fin saca la meta de la cola, las celdas verdes trazan el camino más corto. Dijkstra habría llenado de gris mucho más de esta rejilla antes de encontrar la misma ruta; la heurística de A* es lo que mantiene el gris confinado a un pasillo:

El código completo

La pestaña "desde cero" es A* con los helpers de rejilla y la heurística Manhattan; la pestaña de librería es Dijkstra — A* con la heurística apagada — que es a la vez el contraste que hace legible a A* y la referencia contra la que se verifica su óptimo. La llamada a networkx que usarías en producción está anotada arriba. Cámbiate entre ellas.

"""A* search — Dijkstra with a sense of direction. Dijkstra explores outward in every
direction equally, because it has no idea where the goal is; it will happily expand
thousands of nodes away from the target before stumbling onto it. But when you DO know
where you're going — a point on a map, a goal tile in a game — you can estimate how far
each node still is from the goal and let that estimate pull the search toward it.

A* orders its priority queue not by distance-so-far g(n) alone (that's Dijkstra) but by
f(n) = g(n) + h(n), where h(n) is a heuristic guess of the remaining distance to the goal.
If h never overestimates the true remaining distance — an "admissible" heuristic — A* is
guaranteed to find the shortest path, exactly like Dijkstra, but it expands far fewer nodes
because it stops wandering away from the target. Set h(n) = 0 and A* IS Dijkstra: the
heuristic is the only difference, and it's the difference between a flood and an arrow.
"""
import heapq


# region: astar
def astar(adj, start, goal, h):
    """Cheapest path from start to goal over non-negative weighted edges, guided by heuristic
    h[n] (an estimate of the remaining distance from n to goal). The priority queue is ordered
    by f = g + h, so nodes that look closer to the goal are explored first. With an admissible
    h (never an overestimate) the first time we pop `goal` we have its true shortest distance.
    Returns (path, cost, expanded) where `expanded` counts nodes settled — the work done."""
    g = {start: 0}
    parent = {start: None}
    # Priority is (f, -g): order by f = g + h, and among equal f prefer the LARGER g — i.e.
    # the node already closer to the goal. This admissible tie-break makes A* hug a straight
    # line to the target instead of fanning across a plateau of equal-f nodes on open grids.
    pq = [(h[start], 0, start)]              # (f, -g, node)
    settled = set()
    expanded = 0
    while pq:
        f, neg_g, u = heapq.heappop(pq)
        if u in settled:
            continue
        settled.add(u)
        expanded += 1
        gu = -neg_g
        if u == goal:                        # popped the goal → its distance is final
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return path[::-1], gu, expanded
        for v, w in adj[u]:
            ng = gu + w
            if ng < g.get(v, float("inf")):  # a cheaper way to v → relax and re-prioritize
                g[v] = ng
                parent[v] = u
                heapq.heappush(pq, (ng + h[v], -ng, v))
    return None, float("inf"), expanded
# endregion


# region: grid
def grid_graph(rows, cols, walls):
    """Turn a grid with blocked cells into a weighted adjacency list (4-connected, unit
    edges). Cells are numbered r*cols + c; `walls` is a set of (r, c) that can't be entered."""
    def nid(r, c):
        return r * cols + c

    adj = {}
    for r in range(rows):
        for c in range(cols):
            if (r, c) in walls:
                continue
            nbrs = []
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in walls:
                    nbrs.append((nid(nr, nc), 1))
            adj[nid(r, c)] = nbrs
    return adj


def manhattan(rows, cols, goal):
    """The admissible, consistent heuristic for a 4-connected unit grid: the straight-line
    grid distance (|Δrow| + |Δcol|) to the goal. It never overestimates, because you can't
    reach the goal in fewer than that many unit steps."""
    gr, gc = divmod(goal, cols)
    return {r * cols + c: abs(r - gr) + abs(c - gc) for r in range(rows) for c in range(cols)}
# endregion

"""The library counterpart and the built-in contrast. In production A* comes from networkx
(`nx.astar_path`, which takes a heuristic callback) or from a game/robotics pathfinding
library:

    import networkx as nx
    nx.astar_path(G, source, target, heuristic=lambda a, b: manhattan(a, b), weight="weight")

The contrast that makes A* legible is DIJKSTRA — which is literally A* with the heuristic
switched off (h ≡ 0). `dijkstra` below is exactly the A* in impl.py with a zero heuristic;
the trace generator runs both to the same goal on the same grid and counts how many nodes
each expands, so the only variable is the heuristic. It's also the trusted reference: with
an admissible heuristic A* must return the same optimal cost as Dijkstra.
"""
import heapq


# region: dijkstra
def dijkstra(adj, start, goal):
    """A* with h ≡ 0: no goal direction, so it expands outward uniformly. Same code shape as
    impl.astar, minus the heuristic — which is the whole point. Returns (cost, expanded)."""
    g = {start: 0}
    pq = [(0, start)]
    settled = set()
    expanded = 0
    while pq:
        gu, u = heapq.heappop(pq)
        if u in settled:
            continue
        settled.add(u)
        expanded += 1
        if u == goal:
            return gu, expanded
        for v, w in adj[u]:
            ng = gu + w
            if ng < g.get(v, float("inf")):
                g[v] = ng
                heapq.heappush(pq, (ng, v))
    return float("inf"), expanded
# endregion

Desde cero vs librería

La comparación que enseña aquí es A* contra Dijkstra, y el remate es que son el mismo algoritmo — A* con $h = 0$ es Dijkstra, línea por línea. Todo lo que separa "explora 3200 nodos" de "explora 290 nodos" vive en un solo término extra, la heurística, que codifica conocimiento que el algoritmo simple no tiene: dónde está la meta. Esa es una lección sobre diseño de algoritmos más amplia que el pathfinding. Muchas veces la forma de ganarle a un algoritmo general no es una estructura de datos más astuta sino inyectar conocimiento del dominio que la versión general no puede usar — aquí, geometría. Dijkstra es óptimo entre los algoritmos que no saben nada de la meta; A* es óptimo entre los algoritmos que conocen la heurística; y la heurística eres tú diciéndole a la búsqueda algo cierto sobre tu problema específico. En producción llamarías networkx.astar_path con un callback de heurística, o usarías el pathfinder de un motor de juego; construirlo tú mismo es lo que convierte "la heurística es toda la diferencia" en un hecho que ya viste en vez de un eslogan.

Dónde te lo vas a encontrar

A* es el algoritmo de pathfinding por defecto de la industria de los videojuegos — casi todo juego de estrategia, RPG y RTS mueve sus unidades con A* sobre una rejilla o malla de navegación, y por eso es uno de los algoritmos que más se ejecuta en hardware de consumo. La robótica lo usa para planeación de movimiento, seguido con variantes de espacio continuo (A* híbrido, D*). Los motores de mapas y ruteo lo usan (y a sus descendientes fuertemente optimizados, como las contraction hierarchies) con heurísticas de distancia en línea recta. Los solucionadores de puzzles — el 15-puzzle, el cubo de Rubik, Sokoban — usan A* con heurísticas de pattern database. Los planeadores de redes y logística lo usan donde sea que exista una meta y una estimación de distancia. Donde la tarea sea "encuentra la mejor ruta a un lugar específico, rápido", A* es el algoritmo, y su heurística es la perilla que lo hace rápido.

Conclusiones

A* encuentra caminos más cortos hacia una meta conocida expandiendo nodos en orden de $f = g + h$ — costo recorrido más una estimación heurística del costo que falta — lo que dirige la búsqueda hacia el objetivo y, con una buena heurística, expande una fracción mínima de los nodos que expandiría Dijkstra (como una décima parte en la rejilla abierta de este capítulo) mientras regresa el mismo camino óptimo. La garantía se sostiene precisamente cuando la heurística es admisible, o sea que nunca sobreestima la distancia real restante; pon la heurística en cero y A* es exactamente Dijkstra. El algoritmo es la misma búsqueda con priority queue de Dijkstra — toda la ventaja está en la heurística, que es conocimiento del dominio que la versión ciega no puede aprovechar.

Con esto se completa la familia de caminos más cortos. Los últimos tres capítulos del bloque de grafos se van a otra pregunta — no caminos sino estructura: conectar todos los nodos lo más barato posible (árboles de expansión mínima, lo que sigue, vía Prim y luego Kruskal), y descomponer un grafo dirigido en sus componentes fuertemente conexas. El algoritmo de Prim, apropiadamente, es este mismo recorrido con priority queue con una sola palabra cambiada en lo que mete al heap.