Ciudad visitada
Ruta actual
Mejor ruta
Problema del Viajero
Traveling Salesman Problem
▸ Paso actual
Presiona reproducir o haz clic en el mapa para agregar ciudades.
📊 Metricas
0
Distancia
0
Ciudades
0
Iteracion
-
Mejora %
📐 Algoritmo
...
📐 Formula
d(a,b) = √((x₂−x₁)² + (y₂−y₁)²)
📚 Sobre TSP
El Problema del Viajero (TSP) busca la ruta mas corta que visita todas las ciudades exactamente una vez y regresa al origen.
Es un problema NP-hard fundamental en optimizacion combinatoria, con aplicaciones en logistica, manufactura, diseno de circuitos y secuenciacion de ADN.
Para N ciudades existen (N−1)!/2 rutas posibles. Con 20 ciudades, eso es ~6 × 10¹⁶ rutas, haciendo la busqueda exhaustiva imposible.
TSP
NP-Hard
Optimizacion
Combinatoria
Heuristica
© 2019 Juan Echeverri