Algoritmos Avanzados en Python

Algoritmos de búsqueda A*

La camioneta de PyEnvíos tiene que cruzar un barrio del centro dibujado como cuadrícula de 30 × 30: 652 celdas libres y 248 edificios. Va de (0, 0) a (29, 29) en cuatro direcciones, con costo 1 por paso. El camino más corto mide 58 pasos. Dijkstra lo encuentra expandiendo 635 celdas: casi todo el mapa. A* encuentra el mismo camino de 58 pasos expandiendo 282. La diferencia está en una sola idea: usar una estimación de cuánto falta.

1. La idea: $f = g + h$

A* fue publicado en 1968 por Peter Hart, Nils Nilsson y Bertram Raphael, del Stanford Research Institute, dentro del proyecto del robot móvil Shakey. Como Dijkstra, mantiene una cola de prioridad de celdas por explorar, pero no las ordena solo por el costo acumulado. Para cada celda $n$ calcula:

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

• $g(n)$: costo real del mejor camino conocido desde el inicio hasta $n$.
• $h(n)$: heurística, una estimación del costo que falta desde $n$ hasta la meta.
• $f(n)$: estimación del costo total de un camino que pasa por $n$.

Siempre se expande la celda con menor $f$. Con $h = 0$, A* es exactamente Dijkstra y explora en círculos; con una buena $h$, la búsqueda se estira hacia la meta.

2. Heurísticas admisibles y consistentes

Una heurística es admisible si nunca sobreestima: $h(n) \le h^*(n)$, donde $h^*(n)$ es el costo real que falta. Con una $h$ admisible, A* garantiza encontrar el camino óptimo. Es consistente si para cada vecino $n'$ alcanzado con costo $c(n, n')$ se cumple $h(n) \le c(n, n') + h(n')$: la estimación no baja más de lo que cuesta el paso. Toda heurística consistente es admisible.

En una cuadrícula con movimientos en cuatro direcciones, la distancia Manhattan $|r - r_m| + |c - c_m|$ es la heurística natural: es lo que costaría llegar sin edificios en medio, así que nunca sobreestima. La euclidiana (línea recta) también es admisible, pero subestima más, porque la camioneta no puede ir en diagonal. Una heurística admisible más cercana al costo real se llama más informada y expande menos nodos.

3. Implementación con heapq

La cola de prioridad es una lista manejada con heapq: heappush y heappop cuestan $O(\log n)$ y el mínimo siempre queda en la posición 0. Cada entrada es la tupla (f, g, celda); las tuplas se comparan elemento por elemento, así que se ordena por $f$ y los empates se rompen por $g$. La función supone la cuadrícula de generar_cuadricula(), donde 1 es edificio:

import heapq, math

def a_estrella(M, inicio, meta, h):
    n, g, cerrados = len(M), {inicio: 0}, set()
    pq = [(h(inicio), 0, inicio)]
    while pq:
        _, gc, (r, c) = heapq.heappop(pq)
        if (r, c) in cerrados:
            continue
        cerrados.add((r, c))
        if (r, c) == meta:
            return gc, len(cerrados)
        for v in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= v[0] < n and 0 <= v[1] < n and not M[v[0]][v[1]] and gc + 1 < g.get(v, math.inf):
                g[v] = gc + 1
                heapq.heappush(pq, (gc + 1 + h(v), gc + 1, v))
    return None, len(cerrados)

Devuelve el costo y las celdas expandidas, un conteo que no depende de la máquina. Si una celda entra varias veces a la cola, las copias viejas se descartan con cerrados.

M = generar_cuadricula()
meta = (29, 29)
manhattan = lambda p: abs(p[0] - meta[0]) + abs(p[1] - meta[1])
print(a_estrella(M, (0, 0), meta, lambda p: 0))                  # (58, 635)
print(a_estrella(M, (0, 0), meta, manhattan))                    # (58, 282)
print(a_estrella(M, (0, 0), meta, lambda p: math.dist(p, meta))) # (58, 473)
print(a_estrella(M, (0, 0), meta, lambda p: 3 * manhattan(p)))   # (60, 91)

4. Comparación en el mapa de PyEnvíos

Las tres primeras filas son óptimas: la heurística solo cambia cuánto trabajo cuesta llegar. La búsqueda voraz ignora $g$ y va siempre hacia la celda que parece más cercana a la meta; expande muy poco, pero se mete en callejones y entrega un camino de 74 pasos, 16 más que el óptimo. Multiplicar la heurística por 3 la vuelve no admisible: el resultado se acerca al voraz en trabajo y pierde la garantía (60 pasos). En PyEnvíos, donde cada paso es combustible, se usa la Manhattan.

Trampas comunes

• Heurística que sobreestima. Si se permiten diagonales, Manhattan deja de ser admisible: una diagonal cuesta menos que dos pasos rectos.
• Unidades distintas. Si el costo es en minutos, $h$ también debe estar en minutos; mezclar metros con minutos rompe la admisibilidad.
• Olvidar descartar entradas viejas. Sin el chequeo de cerrados, una celda se expande varias veces y el conteo se infla.
• Detenerse al descubrir la meta. El costo queda fijo cuando la meta sale de la cola, no cuando entra.
• Tuplas sin desempate. Si dos entradas empatan y el siguiente elemento no es comparable, heapq lanza TypeError.

Cierre

En el notebook busqueda-a-estrella se dibujan las celdas que expande cada estrategia sobre el mismo mapa. Antes de usar A* en un problema nuevo, escribe la heurística y comprueba que nunca supera el costo real; si no puedes argumentarlo, empieza con $h = 0$ y mejora desde ahí.