Solucionador del Viajante — Encuentra la Ruta Más Corta Por Todas las Ciudades
Nuestro Solucionador del Viajante encuentra el recorrido de costo mínimo exacto que visita cada ciudad exactamente una vez y regresa a la ciudad de inicio, dada una matriz de distancias entre ciudades, usando el algoritmo de programación dinámica de máscara de bits de Held-Karp — un método exacto deliberadamente limitado a un máximo de 12 ciudades ya que el problema es NP-difícil en general.
Respuesta rápida
Introduce una matriz de distancias entre ciudades para encontrar al instante el recorrido de ida y vuelta más corto exacto mediante programación dinámica de Held-Karp.
Introduce una fila por ciudad, distancias separadas por comas, p. ej. 0,10,15,20 luego 10,0,35,25. Hasta 12 ciudades.
Cómo usar Solucionador del Viajante — Programación Dinámica Exacta de Held-Karp Online
- 1
Introduce una matriz de distancias, una fila por ciudad, con distancias separadas por comas, p. ej. 0,10,15,20 luego 10,0,35,25 y así sucesivamente.
- 2
La matriz debe ser cuadrada, con cada entrada dando la distancia entre dos ciudades (las entradas diagonales suelen ser 0).
- 3
Haz clic en 'Calcular' para encontrar el recorrido óptimo exacto mediante programación dinámica de Held-Karp.
¿Por qué usar Solucionador del Viajante — Programación Dinámica Exacta de Held-Karp Online?
El problema del viajante pregunta por la ruta más corta posible que visita cada ciudad exactamente una vez y regresa al inicio — un problema NP-difícil clásico donde comprobar por fuerza bruta las (n−1)!/2 rutas posibles se vuelve imposible más allá de un puñado de ciudades. El algoritmo de Held-Karp mejora dramáticamente la fuerza bruta usando programación dinámica sobre subconjuntos: rastrea, para cada subconjunto de ciudades visitadas y cada posible ciudad final, la forma más barata de llegar a ese estado, construyendo desde subconjuntos pequeños hasta el conjunto completo en tiempo O(n² · 2ⁿ) en lugar de O(n!). Eso sigue siendo exponencial, por lo que esta calculadora limita el problema a 12 ciudades, donde Held-Karp sigue siendo cómodamente rápido mientras encuentra el recorrido exacto y demostrablemente óptimo (no solo una buena aproximación).
Preguntas frecuentes
Herramientas relacionadas
Verificador de Camino Hamiltoniano — Visita Cada Nodo una Vez Online
Comprueba si un grafo tiene un camino hamiltoniano — un camino que visita cada nodo exactamente una vez — mediante búsqueda con retroceso. Calculadora gratuita, limitada a grafos de hasta 10 nodos.
Calculadora de Árbol de Expansión Mínima — Algoritmo de Kruskal Online
Encuentra el árbol de expansión mínima de un grafo ponderado usando el algoritmo de Kruskal. Calculadora gratuita con una entrada simple de lista de aristas y detección de ciclos mediante union-find.
Solucionador de Programación Lineal — Método de Punto de Esquina de 2 Variables Online
Resuelve un programa lineal de 2 variables encontrando y evaluando cada punto de esquina de la región factible. Calculadora gratuita, maximiza o minimiza con restricciones lineales.