Visualizador de Búsqueda de Caminos
Aprender cómo las máquinas encuentran caminos óptimos
Entender funciones heurísticas
Comparar algoritmos BFS, DFS, Dijkstra y A*
Reconocer cuándo usar cada algoritmo
Visualizador de Búsqueda de Caminos
Visualiza algoritmos de búsqueda de caminos en acción
Instrucciones
- • Haz clic para colocar nodo inicial (verde)
- • Haz clic para colocar nodo final (rojo)
- • Dibuja muros haciendo clic y arrastrando
Guía de Aprendizaje
Elige tu estilo de aprendizaje
¿Qué Hace?
Algoritmos de pathfinding resuelven problemas de traversal de grafos con garantías de optimalidad. A* combina completitud de Dijkstra con heurísticas greedy (h(n)) para minimizar f(n) = g(n) + h(n). Crítico para navegación robótica, IA de juegos, y optimización de rutas en redes logísticas procesando millones de nodos.
¿Cómo Funciona?
- 1Modelar problema como grafo ponderado G(V,E) con nodos inicio y meta
- 2Inicializar conjunto abierto (cola prioridad) y cerrado (visitados)
- 3Computar g(n) = costo real desde inicio, h(n) = heurística a meta
- 4Extraer nodo con mínimo f(n) = g(n) + h(n) de la cola
- 5Expandir vecinos, actualizar costos si se encuentra mejor camino
- 6Terminar al alcanzar meta, reconstruir camino via punteros padre
Analogía Simple
A* es como Monte Carlo Tree Search (MCTS) en AlphaGo: balancea explotación (g(n) - costos conocidos) con exploración (h(n) - direcciones prometedoras). Heurísticas inadmisibles rompen optimalidad como alta temperatura en simulated annealing - más rápido pero subóptimo.
Concepto Clave
Admisibilidad de heurística es crucial: h(n) nunca debe sobrestimar costo real (h(n) ≤ h*(n)). Distancia Manhattan para grids, Euclidiana para espacio libre. Mala heurística = convergencia 100x más lenta en sistemas de ruteo en producción.
Conceptos Fundamentales
Heurísticas
Una adivinanza educada sobre distancia a la meta. Distancia Manhattan (|x1-x2| + |y1-y2|) para grids, Euclidiana (√((x1-x2)² + (y1-y2)²)) para espacio libre. Buena heurística = 10x más rápido.
Completitud
Garantía de encontrar solución si existe. BFS/A* son completos (siempre encuentran camino). DFS puede atascarse en loops infinitos. Crítico para robótica de seguridad crítica.
Optimalidad
Encontrar el camino más corto/barato, no solo cualquier camino. A* es óptimo cuando heurística es admisible (nunca sobreestima). Greedy es rápido pero no óptimo.
Expansión de Nodos
Cuántos cuadrados revisa el algoritmo antes de encontrar meta. BFS: O(b^d), A*: O(b^(d/2)). Para mapas grandes (d=20), diferencia es 1 millón vs 1 mil - por eso GPS es instantáneo.
Aplicaciones del Mundo Real
Ruteo Google Maps
A* con heurísticas de tráfico encuentra ruta más rápida a través de millones de segmentos de carretera en <100ms. Pondera distancia + tiempo + patrones históricos de tráfico.
Robots de Almacén
Centros de cumplimiento Amazon usan A* para 10,000+ robots navegando estantes. Obstáculos dinámicos (otros robots) requieren replanificación en tiempo real a 10Hz.
Navegación IA de Juegos
NPCs en Skyrim, Starcraft, League of Legends usan A* para moverse por mapas. 100+ unidades con pathfinding simultáneo a 60 FPS requiere optimización jerárquica de A*.
Planificación de Rutas de Vuelo
Aerolíneas usan A* con heurísticas de clima/combustible para encontrar rutas óptimas. Evitar tormentas, minimizar consumo, respetar zonas de control aéreo - optimización multi-objetivo.
Pruébalo Tú Mismo
Desafío Construir Laberinto
Dibuja un laberinto complejo con muchos callejones sin salida. Ejecuta BFS - míralo perder tiempo explorando cada callejón. ¡Ahora ejecuta A* - ve cómo ignora callejones y va directo a la meta! Cuenta cuadrados azules (expansiones) - A* debería ser 5-10x menos.
Batalla de Heurísticas: Manhattan vs Euclidiana
Crea un grid abierto (sin muros). A* con distancia Manhattan revisa ligeramente más nodos que Euclidiana porque sobreestima en movimiento diagonal. ¡Pruébalo! Esto muestra por qué elegir la heurística correcta importa.
Escenario del Peor Caso
Pon meta en esquina inferior derecha sin muros. BFS explora el grid COMPLETO (miles de nodos). A* va diagonal directo (decenas de nodos). Este caso extremo muestra el poder de A* cuando tienes buena info direccional.
Errores Comunes a Evitar
❌ Usar heurísticas inadmisibles
¿Por Qué? Si h(n) > h*(n) (sobreestima costo real), A* pierde garantía de optimalidad. Podría encontrar camino 20% más largo que óptimo. Siempre usa Manhattan/Euclidiana para grids - probadas admisibles.
❌ Olvidar revisar nodos visitados
¿Por Qué? Sin conjunto de visitados, algoritmo revisita nodos infinitamente en ciclos. Memoria explota, nunca termina. Bug clásico que crashea robots en producción.
❌ Usar DFS para camino más corto
¿Por Qué? DFS encuentra UN camino, no EL MÁS CORTO. Para robótica/navegación, esto significa rutas ineficientes, batería desperdiciada, tiempos de entrega más largos. Usa BFS o A* cuando optimalidad importa.