El problema del viajante busca el recorrido cerrado de menor costo que visita cada ciudad exactamente una vez. Es fácil describirlo, pero resolverlo de forma óptima puede requerir explorar una cantidad enorme de posibilidades.
Un viajante debe salir de una ciudad, visitar todas las demás una sola vez y regresar al inicio. Cada traslado tiene un costo, que puede representar distancia, tiempo, dinero o consumo de energía.
El objetivo es minimizar la suma total. TSP es uno de los problemas más estudiados de optimización combinatoria y sirve como modelo para numerosas tareas de planificación.
Dado un grafo ponderado G = (V,E), se busca un ciclo que visite cada vértice exactamente una vez y regrese al vértice inicial, minimizando el costo.
Si alguna conexión no existe, puede considerarse de costo infinito o trabajarse directamente sobre el grafo incompleto.
Una ruta válida de TSP es un ciclo hamiltoniano: visita todos los vértices exactamente una vez. TSP agrega el objetivo de encontrar el de menor peso.
Determinar si existe un ciclo hamiltoniano puede reducirse a una instancia de TSP, lo que ayuda a explicar la dificultad computacional del problema.
| Variante | Propiedad | Ejemplo |
|---|---|---|
| Simétrico | w(u,v) = w(v,u) | Distancias euclidianas |
| Asimétrico | w(u,v) puede diferir de w(v,u) | Calles de un sentido o tarifas |
En el caso simétrico, recorrer un ciclo en sentido inverso tiene el mismo costo.
Una instancia es métrica cuando los costos son simétricos y cumplen la desigualdad triangular.
Ir directamente nunca es peor que desviarse por otro vértice. Esta propiedad permite algoritmos de aproximación con garantías que no existen para el TSP general.
Comienza con el orden alfabético o construye una ruta por vecino más cercano. Después aplica 2-opt para reemplazar dos aristas cuando la inversión de un segmento reduce la distancia.
Ruta actual
Último intercambio
Acción actual
2-opt elimina cruces y otras desviaciones evidentes, pero detenerse sin mejoras solo certifica un óptimo local.
Fijando una ciudad inicial, existen (n − 1)! órdenes posibles. En TSP simétrico, una ruta y su inversa son equivalentes, por lo que quedan (n − 1)! / 2 ciclos distintos.
Para instancias pequeñas pueden enumerarse todas las permutaciones, calcular el costo de cada ciclo y conservar el menor.
function costoRuta(ruta, distancia) {
let total = 0;
for (let i = 0; i < ruta.length; i++) {
const siguiente = (i + 1) % ruta.length;
total += distancia[ruta[i]][ruta[siguiente]];
}
return total;
}Fijar la primera ciudad elimina rotaciones equivalentes, pero la complejidad continúa siendo O(n!).
Branch and bound construye rutas parciales. Si una cota inferior demuestra que una rama no puede mejorar la mejor solución conocida, la descarta.
Una buena solución inicial fortalece la poda. Sin embargo, en el peor caso todavía puede explorarse una cantidad exponencial de estados.
Held-Karp representa un subproblema mediante un subconjunto S de ciudades visitadas y la última ciudad j.
La recurrencia prueba como penúltima ciudad cada i de S. Reduce el tiempo factorial a O(n²2ⁿ), a costa de O(n2ⁿ) memoria.
for (let mascara = 1; mascara < (1 << n); mascara++) {
for (let ultimo = 0; ultimo < n; ultimo++) {
if (!(mascara & (1 << ultimo))) continue;
const anterior = mascara ^ (1 << ultimo);
for (let previo = 0; previo < n; previo++) {
if (anterior & (1 << previo)) {
dp[mascara][ultimo] = Math.min(
dp[mascara][ultimo],
dp[anterior][previo] + distancia[previo][ultimo]
);
}
}
}
}La inicialización fija una ciudad de origen. Al final se suma el regreso desde la última ciudad al origen.
La heurística comienza en una ciudad y visita repetidamente la ciudad no visitada más cercana. Es rápida y fácil de implementar.
Puede tomar buenas decisiones iniciales y dejar una conexión final muy costosa. Probar varios puntos de partida suele mejorar el resultado.
2-opt selecciona dos aristas (a,b) y (c,d), las elimina y reconecta (a,c) y (b,d), invirtiendo el segmento intermedio.
Se repite hasta que ningún intercambio mejora la ruta. En distancias euclidianas elimina todos los cruces, porque un cruce nunca es óptimo.
Una cota inferior indica un costo que ninguna ruta óptima puede superar hacia abajo. El peso de un árbol de expansión mínima es una cota porque quitar una arista de cualquier ciclo hamiltoniano produce un árbol generador.
Cotas más fuertes pueden construirse con árboles 1-tree y relajaciones de programación lineal.
En TSP métrico, duplicar las aristas de un MST y acortar vértices repetidos produce una ruta de costo como máximo dos veces el óptimo.
El algoritmo de Christofides combina un MST con un emparejamiento mínimo de los vértices de grado impar y garantiza un factor de aproximación de 3/2.
La versión de decisión —¿existe una ruta de costo a lo sumo K?— es NP-completa. La versión de optimización es NP-difícil.
No se conoce un algoritmo polinómico que resuelva exactamente todas las instancias. En la práctica se combinan formulaciones enteras, cortes, ramificación y heurísticas.
TSP muestra la diferencia entre verificar una solución y encontrar la mejor entre un espacio factorial. Las instancias pequeñas admiten métodos exactos; las grandes requieren combinar buenas construcciones, mejoras locales y cotas.
En el próximo tema profundizaremos en los grafos hamiltonianos, la estructura que determina si existe un ciclo capaz de visitar todos los vértices una sola vez.