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
Visualiza algoritmos de búsqueda de caminos en acción
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.
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.
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.
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.
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.
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.
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.
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.
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.
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*.
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.
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.
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.
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.
❌ 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.