Visualizador de algoritmos de búsqueda de caminos
observa cómo distintos algoritmos de búsqueda compiten en la misma cuadrícula, frontera a frontera
por qué importan las heurísticas 🖖
La fórmula f(n)=g(n)+h(n) hace que A* prefiera los nodos que son baratos hasta ahora y aún parecen cercanos a la meta. Si h nunca sobreestima el costo restante, A* conserva su garantía de camino más corto; una h admisible más fuerte explora menos celdas innecesarias. Cambia el menú desplegable de algoritmo para ver qué pasa si eliminas la heurística (Dijkstra), el costo acumulado (Greedy) o toda puntuación (BFS).
Un bucle, cuatro personalidades 🖖
Los cuatro algoritmos ejecutan exactamente el mismo bucle: sacan la celda más prometedora de una lista de espera (la frontera ámbar), la marcan como visitada (índigo) y añaden sus vecinas libres de nuevo a la lista. Solo se diferencian en cómo deciden qué celda parece más prometedora. Conclusión: el número de nodos expandidos es el verdadero marcador — menos celdas índigo significan que el algoritmo alcanzó la misma meta con menos trabajo desperdiciado.
Las diagonales pueden romper la garantía 🖖
Activa 'Permitir diagonal' junto con la heurística Manhattan y A* puede devolver sin avisar un camino que no es el más corto. Aquí un paso diagonal cuesta solo √2 ≈ 1.41, pero la distancia Manhattan lo cobra como 2 — así la heurística sobreestima, se vuelve no admisible y se pierde la garantía de optimalidad. Cambia a Euclidiana, que nunca supera la distancia en línea recta, y el camino más corto regresa.
Problemas de ejemplo
- cuadrícula abierta - Los obstáculos dispersos producen una ruta A* casi directa con muy pocas expansiones.
- tipo laberinto - Los obstáculos densos obligan a A* a hacer desvíos más largos y más expansiones.
- heurística débil - Una heurística más débil explora muchas más celdas antes de hallar la misma ruta.
- Dijkstra explora - Dijkstra ignora la meta y se expande en todas las direcciones.
- trampa greedy - El algoritmo voraz (Greedy Best-First) se lanza hacia la meta y puede quedar atrapado en callejones sin salida.
- bfs + diagonales - BFS trata los pasos diagonales y ortogonales con el mismo costo, por lo que su ruta puede diferir de la de A*.