Visualizador Algoritmo A*

Pseudocódigo

A* es Dijkstra con un término extra. Donde Dijkstra siempre expande el nodo de menor coste confirmado g, A* expande el de menor f = g + h, donde h estima el coste que queda. Pon h a cero en todas partes y el pseudocódigo de abajo se convierte exactamente en Dijkstra.

A*(grafo, inicio, meta, h):
    para cada vértice v: g[v] = infinito
    g[inicio] = 0
    f[inicio] = h(inicio)
    abiertos = cola de prioridad con (f[inicio], inicio)
    cerrados = conjunto vacío

    mientras abiertos no esté vacío:
        u = abiertos.extraerMin()      // f más pequeño
        si u == meta: devolver reconstruir(u)
        añadir u a cerrados

        para cada arista (u, v, w):
            si v en cerrados: continuar
            tentativo = g[u] + w
            si tentativo < g[v]:
                previo[v] = u
                g[v] = tentativo
                f[v] = tentativo + h(v)
                abiertos.insertar(f[v], v)

    devolver sin camino

Saltar los nodos cerrados en la línea 15 solo es seguro cuando h es consistente, es decir h(u) <= w(u, v) + h(v) para toda arista. Con una heurística meramente admisible hay que permitir que los nodos salgan del conjunto cerrado y se reabran, o A* puede devolver un camino subóptimo. El visualizador de arriba escala la distancia en línea recta por el coste por unidad más barato que ofrece cualquier arista, lo que hace h consistente por la desigualdad triangular, así que no hace falta reabrir nada.

Ejemplo resuelto, paso a paso

Cinco nodos, con S en el origen y la meta G cinco unidades a su derecha. Lo interesante de la traza es el nodo que A* nunca toca.

Grafo de ejemplo: S(0,0), A(2,1), B(2,-1), C(1,4), G(5,0). Aristas S-A = 3, S-B = 2, S-C = 4, A-B = 2, A-G = 4, B-G = 6, C-G = 7. Escalando la distancia en línea recta por el coste por unidad más barato de cualquier arista (0,894) resulta h(S) = 4,47, h(A) = 2,83, h(B) = 2,83, h(C) = 5,06, h(G) = 0.

1. 1. Expande S, el único nodo abierto, con f = 4,47. Relajar sus tres aristas deja A en g = 3, f = 5,83; B en g = 2, f = 4,83; y C en g = 4, f = 9,06. C ya parece caro: está cerca de S pero apunta lejos de la meta.
2. 2. Expande B, ahora el f más pequeño con 4,83. Alcanza la meta con g = 8, f = 8,00. Fíjate en que A* no se detiene aquí. Encontrar la meta no es lo mismo que expandirla, y todavía no se sabe que 8 sea lo mejor.
3. 3. Expande A con f = 5,83. Su arista hacia G da g = 7, que mejora el 8 encontrado por B, así que G pasa a f = 7,00.
4. 4. Expande G con f = 7,00, el f más pequeño del conjunto abierto. La meta ha sido expandida, su coste es definitivo y la búsqueda termina con C todavía intacto en el conjunto abierto con f = 9,06.

A* devuelve S a A a G con coste 7, habiendo expandido 4 nodos. Dijkstra sobre el mismo grafo devuelve el mismo camino con el mismo coste, pero expande 5: procesa C antes de estar dispuesto a fijar la meta. C nunca mereció una visita, y h es lo que permitió a A* saberlo sin comprobarlo.

Complejidad y de dónde sale

Tiempo: O((V + E) log V) en el peor caso con un montículo binario · Espacio: O(V)

El peor caso es el de Dijkstra, y por el mismo motivo: cada vértice puede entrar una vez en la cola de prioridad y cada arista puede disparar una operación de decremento de clave, lo que da V extracciones y E actualizaciones a O(log V) cada una. La heurística no cambia esa cota. Lo que cambia es la constante: los nodos cuyo f supera el coste final de la meta no se expanden nunca. Con h = 0 A* degenera exactamente en Dijkstra; con un h perfecto recorre directamente el camino óptimo. Sobre 4000 grafos ponderados generados al azar, la implementación de arriba expandió 4,58 nodos de media frente a los 5,52 de Dijkstra, y devolvió el coste óptimo todas las veces.

Cuándo usar Algoritmo A* y cuándo no

A* solo compensa su maquinaria extra cuando tienes una meta y una estimación utilizable de la distancia hasta ella. Sin alguna de las dos, una de estas opciones es la mejor herramienta.

Errores frecuentes

• Una heurística que sobreestima rompe la optimalidad. Si h puede superar el coste real restante, A* podría fijar la meta por una ruta que no es la más barata, y lo hará en silencio. La distancia en línea recta solo es admisible cuando está en las mismas unidades que los pesos de las aristas. La distancia en píxeles frente a pesos de 1 a 10 sobreestima muchísimo.
• Admisible no es lo mismo que consistente. El conjunto cerrado supone consistencia, h(u) <= w(u, v) + h(v) en toda arista. Una heurística admisible pero inconsistente necesita que los nodos se reabran cuando aparece una ruta más barata; si no, el camino devuelto puede ser subóptimo.
• Parar cuando la meta se descubre por primera vez. Llegar a la meta durante la relajación no demuestra nada. En la traza de arriba, B encuentra G con coste 8 un paso antes de que A la encuentre con 7. Hay que esperar a que la meta sea el nodo que se expande.
• Recalcular h en cada comparación. La heurística se llama una vez por nodo, no una vez por comparación en la cola de prioridad. Cachear h junto a g es la diferencia entre una heurística que se paga sola y otra que cuesta más de lo que ahorra.
• Dar por hecho que A* siempre gana a Dijkstra. Con una heurística débil, A* expande los mismos nodos que Dijkstra más el coste de calcular h. En grafos sin geometría, h = 0 es la elección honesta y Dijkstra es la implementación más simple.

Preguntas frecuentes

¿Qué significa realmente f = g + h?

g es lo que ha costado hasta ahora un camino hasta este nodo, y es un hecho. h es una estimación de lo que costará ir de aquí a la meta. Su suma f es el coste estimado de la ruta completa más barata que pasa por este nodo, y A* siempre trabaja sobre el nodo con la estimación más pequeña.

¿Qué hace que una heurística sea admisible?

Que nunca sobreestime el coste real restante. La distancia en línea recta cumple esto para desplazamientos en el plano, porque ninguna ruta puede ser más corta que una recta. La admisibilidad es lo que garantiza que A* devuelva un camino óptimo.

¿A* siempre es más rápido que Dijkstra?

Nunca expande más nodos que Dijkstra dado el mismo grafo y una heurística consistente, y normalmente expande menos. Pero no es asintóticamente más rápido: ambos son O((V + E) log V). La ganancia es un factor constante y se reduce a nada a medida que la heurística se debilita hacia cero.

¿Puede A* manejar pesos negativos?

No. Hereda la suposición que hace funcionar a Dijkstra: que alargar un camino nunca lo abarata. Usa Bellman-Ford cuando los pesos puedan ser negativos.

¿Quién inventó A*?

Peter Hart, Nils Nilsson y Bertram Raphael, en el Stanford Research Institute, en un artículo de 1968 titulado "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". Una nota de 1972 de los mismos autores corrigió la afirmación original sobre optimalidad, distinguiendo admisibilidad de consistencia.

¿Por qué A* se saltó el nodo C en el recorrido?

C está en f = 9,06 mientras que la meta se fijó en f = 7,00. Como la heurística nunca sobreestima, un f de 9,06 es la promesa de que ninguna ruta por C puede costar menos de 9,06, lo cual ya es peor que una respuesta terminada de 7. A* puede descartarlo sin mirar.