Solucionador del Viajante de Comercio (TSP)

Solucionador del Viajante de Comercio (TSP)

El Solucionador del Viajante de Comercio es una calculadora práctica y educativa para el clásico Problema del Viajante de Comercio (TSP): dado un conjunto de ciudades y distancias entre pares, encontrar el recorrido más corto posible que visite cada ciudad exactamente una vez y regrese al inicio. Este solucionador acepta coordenadas planas o una matriz de distancias personalizada, selecciona automáticamente el mejor algoritmo según el tamaño del problema y representa el recorrido resultante como un mapa SVG animado.

¿Qué es el Problema del Viajante de Comercio?

Formalmente, dado un grafo ponderado completo G = (V, E) con un conjunto de vértices V = {1, 2, ..., n} y pesos de aristas d(i, j), el TSP busca una permutación π de los vértices que minimice:

El término final cierra el bucle. El TSP es uno de los problemas más antiguos y estudiados en optimización combinatoria: es NP-duro en el caso general, lo que significa que no se conoce ningún algoritmo que resuelva cada instancia en tiempo polinomial. A pesar de ello, aparece en innumerables aplicaciones del mundo real: rutas de vehículos, perforación de PCB, secuenciación de ADN, rutas de recogida en almacenes, horarios de observación astronómica e incluso entrega de correo rural.

Cómo Funciona este Solucionador

Programación Dinámica de Held–Karp (Exacta)

Para instancias pequeñas (hasta 12 ciudades), el solucionador calcula el recorrido demostrablemente óptimo utilizando el algoritmo de Held–Karp, publicado de forma independiente por Richard Bellman y por Michael Held y Richard Karp en 1962. La recurrencia clave, donde C(S, j) es el camino más corto desde el vértice 1 hasta el vértice j visitando exactamente el subconjunto S, es:

El costo del recorrido óptimo es entonces min_j [C({1,...,n}, j) + d(j, 1)]. Held–Karp se ejecuta en un tiempo O(2ⁿ · n²) y memoria O(2ⁿ · n), una mejora enorme sobre la fuerza bruta n!, pero sigue siendo exponencial. Pasadas las 20 ciudades aproximadamente, la huella de memoria se vuelve impracticable.

Vecino más Cercano + 2-opt (Heurística)

Para instancias más grandes, el solucionador utiliza una heurística de dos etapas. Primero, el Vecino más Cercano construye un recorrido rápido dirigiéndose con avidez a la ciudad no visitada más cercana desde cada vértice de inicio. El solucionador prueba muchos vértices de inicio y se queda con el mejor recorrido. Luego, la búsqueda local 2-opt mejora el recorrido eliminando iterativamente dos aristas y volviendo a conectar los dos caminos resultantes de la única otra manera posible:

Geométricamente, 2-opt elimina cada "cruce" en el recorrido: cualquier par de segmentos que se crucen siempre se puede descruzar para obtener una longitud total más corta. El algoritmo se detiene en un óptimo local donde ningún intercambio individual ayuda, lo que se denomina un recorrido 2-óptimo. En instancias euclidianas realistas, 2-opt suele encontrar recorridos dentro del 2 al 5% del óptimo real en milisegundos.

Formatos de Entrada

Modo de Coordenadas (x, y)

Una ciudad por línea. Cada línea es etiqueta, x, y (la etiqueta es opcional). El solucionador calcula las distancias euclidianas automáticamente y visualiza las ciudades en sus posiciones reales.

Modo de Matriz de Distancias

Una matriz cuadrada de n × n distancias no negativas, una fila por línea, valores separados por espacios o comas. Las matrices pueden ser simétricas o asimétricas; las matrices asimétricas modelan calles de sentido único, precios de vuelos con disponibilidad variable y viajes que dependen del viento. Opcionalmente, proporciona etiquetas en el campo de Etiquetas de matriz.

Comparación de Algoritmos

Cómo Usar este Solucionador

1. Elige un modo de entrada. Coordenadas si tus ciudades tienen posiciones (x, y) significativas; Matriz de distancias si tus costos no son euclidianos o son asimétricos.
2. Pega o escribe tus datos. Una ciudad o fila por línea. Haz clic en un botón de ejemplo rápido sobre el formulario para rellenar un ejemplo válido.
3. Elige el algoritmo. Déjalo en Auto para el valor predeterminado correcto: Held–Karp cuando la instancia es lo suficientemente pequeña para la optimización demostrable, NN + 2-opt en caso contrario. Fuerza un algoritmo específico si deseas comparar.
4. Elige cerrado o abierto. Un recorrido cerrado regresa al inicio (el TSP tradicional). El modo de ruta abierta resuelve el problema relacionado del Camino Hamiltoniano, donde el viajante termina en una ciudad diferente.
5. Haz clic en Resolver. La página de resultados muestra la longitud total del recorrido, un SVG animado de la ruta (haz clic en "Reproducir animación" para repetirla), la secuencia completa de ciudades, un desglose por arista y la matriz de distancias con las aristas del recorrido resaltadas.

Ejemplo Práctico

Considera cinco ciudades —un rectángulo más un pico—: A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5). El solucionador devuelve:

• Recorrido: A → D → E → C → B → A
• Longitud: 3 + √8 + √8 + 3 + 4 ≈ 15.66
• ¿Óptimo? Sí — Held–Karp demuestra que no existe un recorrido más corto.
• ¿Por qué este orden? La ruta traza la envolvente convexa de los cinco puntos (A → D → E → C → B → A). Una propiedad clásica del TSP euclidiano es que un recorrido óptimo visita los puntos de la envolvente convexa en su orden cíclico; los puntos interiores se insertan entre vecinos adyacentes de la envolvente. Cualquier recorrido que cruce su propia ruta, como A → C → B → D → E → A (longitud ≈ 21.2), siempre puede ser descruzado por 2-opt para obtener un resultado más corto.

Aplicaciones en el Mundo Real

• Logística y entrega — optimiza la ruta diaria de un conductor a través de 15 paradas para minimizar combustible y tiempo.
• Fabricación — ordena los agujeros que debe realizar un taladro CNC en un PCB para minimizar el desplazamiento del cabezal.
• Ensamblaje de genomas — ordena fragmentos de ADN por similitud de solapamiento, codificados como una matriz de distancias.
• Astronomía — programa los movimientos del telescopio entre estrellas objetivo para maximizar el tiempo de observación.
• Recogida en almacén — secuencia las visitas a los pasillos para completar un pedido en el menor número de pasos.
• Planificación turística — planifica un viaje por varias ciudades que minimice el tiempo de viaje y el costo del pasaje.

Preguntas Frecuentes

¿Qué es el Problema del Viajante de Comercio?

El Problema del Viajante de Comercio (TSP) busca el recorrido más corto posible que visite cada ciudad exactamente una vez y regrese a la ciudad de origen. Es uno de los problemas más famosos en optimización combinatoria y es NP-duro en el caso general, lo que significa que no existe un algoritmo conocido que resuelva todas las instancias en tiempo polinomial.

¿Qué es el algoritmo Held–Karp?

Held–Karp es un algoritmo de programación dinámica que resuelve el TSP exactamente en tiempo O(2ⁿ · n²) y memoria O(2ⁿ · n). Es drásticamente más rápido que la fuerza bruta (n factorial) pero sigue siendo exponencial, por lo que en la práctica solo se usa para instancias de hasta unas 20 ciudades. Este solucionador utiliza Held–Karp cuando hay 12 ciudades o menos.

¿Qué es 2-opt y por qué se utiliza?

2-opt es una heurística de búsqueda local que elimina repetidamente dos aristas del recorrido actual y vuelve a conectar los dos caminos resultantes de la otra manera posible. Cuando el nuevo recorrido es más corto, se mantiene el intercambio. 2-opt se ejecuta en tiempo polinomial por iteración y encuentra sistemáticamente recorridos dentro de un pequeño porcentaje del óptimo, por lo que es la heurística clásica de referencia para instancias de TSP de mayor tamaño.

¿Cuándo debo usar coordenadas frente a una matriz de distancias?

Usa coordenadas cuando tus ciudades se sitúen en un plano con distancias en línea recta; por ejemplo, puntos en un mapa, ubicaciones de almacenes o agujeros en una placa de circuito. Usa una matriz de distancias cuando el costo entre pares no sea euclidiano; por ejemplo, precios de vuelos, tiempos de viaje con tráfico, distancias en carreteras de sentido único o costos asimétricos. El modo de matriz acepta cualquier distancia no negativa, incluso las asimétricas.

¿Es óptima la solución 2-opt?

No, 2-opt devuelve un recorrido 2-óptimo, lo que significa que no se puede intercambiar ningún par individual de aristas para producir una ruta más corta. Se trata de un óptimo local que suele estar a pocos puntos porcentuales del óptimo global en instancias bien comportadas, pero no se garantiza que sea el mejor global. Para un recorrido demostrablemente óptimo en instancias pequeñas, elige Held–Karp.

¿Admite esta herramienta matrices de distancia asimétricas?

Sí. En el modo de Matriz de distancias puedes introducir cualquier matriz cuadrada no negativa, incluidas las asimétricas donde D[i][j] difiere de D[j][i]. Tanto Held–Karp como 2-opt gestionan correctamente las matrices asimétricas. Esto es útil para problemas de rutas del mundo real con calles de sentido único, tráfico o costos de vuelo que dependen del viento.

Lecturas Adicionales

• Problema del viajante — Wikipedia
• Algoritmo de Held–Karp — Wikipedia
• 2-opt — Wikipedia
• Algoritmo del vecino más cercano — Wikipedia

Operaciones matemáticas avanzadas:

• Calculadora de Matriz de Adyacencia Nuevo
• Calculadora de Antilogaritmo
• Calculadora de funciones Beta
• Calculadora de Coeficientes Binomiales
• Calculadora de distribución binomial Popular
• Calculadora Bit a Bit
• Simplificador de Álgebra Booleana Popular
• Calculadora del Teorema del Límite Central
• Calculadora del Teorema Chino del Resto
• Calculadora de Combinación Popular
• Calculadora de Función de Error Complementaria
• Calculadora de Números Complejos
• Calculadora de fracciones continuas
• Calculadora de Desarreglo (Subfactorial)
• Calculadora de Camino más Corto de Dijkstra
• Calculadora de Entropía
• Calculadora de función error
• Calculadora de la Función Totiente de Euler
• Calculadora de decaimiento exponencial
• Calculadora de Crecimiento Exponencial de Alta Precisión Popular
• Calculadora de Integral Exponencial
• Calculadora de Exponentes (Alta Precisión) Popular
• Calculadora del Algoritmo Euclidiano Extendido
• Calculadora de Factorial
• Calculadora de Función Gamma
• Calculadora de Proporción Áurea Popular
• Calculadora de Coloración de Grafos Nuevo
• Validador de secuencia de grados de grafo
• Calculadora de Orden en Teoría de Grupos Nuevo
• Calculadora de Media Vida
• Verificador de Camino Hamiltoniano Nuevo
• Calculadora de Inclusión-Exclusión Nuevo
• Solucionador de Mapa de Karnaugh (K-Map) Nuevo
• Solucionador de Programación Lineal Nuevo
• Calculadora de Estado Estacionario de Cadena de Markov
• Calculadora de Árbol de Expansión Mínimo
• Calculadora de Exponenciación Modular Nuevo
• Calculadora del Inverso Multiplicativo Modular
• Calculadora de Distribución Binomial Negativa Nuevo
• Calculadora de Flujo de Red (Flujo Máximo) Nuevo
• Calculadora de Tasa de Crecimiento Porcentual Popular
• Calculadora de Permutación Popular
• Calculadora de Permutaciones con Repetición Nuevo
• Calculadora del Principio del Palomar
• Verificador de Grafo Planar Nuevo
• Calculadora de Distribución de Poisson
• Calculadora de Raíces de Polinomios con Pasos Detallados
• Calculadora de Raíz Primitiva
• Calculadora de probabilidad
• Calculadora de Distribución de Probabilidad Popular
• Calculadora de Proporciones
• Calculadora de Fórmula Cuadrática
• Calculadora de Anillos y Cuerpos Nuevo
• Calculadora de Redondeo Nuevo
• Calculadora Científica Popular
• Calculadora de notación científica Popular
• Calculadora de Teoría de Conjuntos
• Calculadora de Cifras Significativas Nuevo
• Solucionador del Problema del Matrimonio Estable Nuevo
• Calculadora de Números de Stirling
• Calculadora de Suma de Cubos
• Calculadora de suma de números enteros positivos
• Calculadora de Suma de Cuadrados
• Calculadora de Ordenación Topológica Nuevo
• Solucionador del Viajante de Comercio (TSP) Nuevo
• Generador de Tabla de Verdad
• Generador de Diagrama de Venn (3 Conjuntos)