Búsqueda A*

Dijkstra con sentido de orientación. Ordena la frontera por f = g + h: costo recorrido + estimación de lo que falta.

El único término extra

• Dijkstra elige el nodo más cercano al INICIO (solo g) → explora un círculo
• A* elige el nodo en el camino más prometedor hacia la META (g + h)
• h(n) = estimación heurística de la distancia restante (p. ej. Manhattan en una rejilla)
• h = 0 ⇒ A* ES Dijkstra. La heurística es toda la diferencia.

Mira la frontera estirarse hacia la meta

Morado = inicio · rojo = meta · azul = abiertos · gris = cerrados · verde = camino. La búsqueda se dobla alrededor de las paredes pero se estira hacia la esquina lejana.

Mismo camino, una fracción del trabajo

3600 celdas: Dijkstra expande ~3200 (toda la rejilla), A* ~290 → 11× menos. Mismo camino óptimo.

El detalle: la admisibilidad

• Es óptimo solo si h nunca SOBREESTIMA la distancia restante (admisible)
• Si sobreestima → más rápido pero regresa un camino que no es el más corto, en silencio
• La distancia Manhattan en una rejilla de 4 vecinos es admisible (no le ganas a |Δr|+|Δc| pasos)
• Desempate: prefiere la g mayor entre f iguales → pégate a la meta, no a una meseta

Conclusión

Gánale a un algoritmo general inyectando conocimiento del dominio que él no puede usar — aquí, geometría. Dijkstra es óptimo entre los ciegos a la meta; A* es óptimo entre los que conocen h. Sigue: árboles de expansión mínima — Prim es este mismo recorrido con heap, una palabra cambiada.