Aprendizaje Interactivo de Teoría de Grafos
Aprendizaje Interactivo de Teoría de Grafos
Guest User
Using app without sign in
Solucionador en línea del problema del viajante
Halla la ruta más corta que visita todas las ciudades y regresa al inicio
Selecciona un algoritmo y genera pasos para comenzar la visualización
El problema del viajante (TSP) pide el recorrido más corto que visita cada ciudad exactamente una vez y regresa al inicio. Es el problema NP-difícil más famoso de la optimización combinatoria, simple de enunciar pero exponencialmente difícil de resolver de forma exacta.
La solución por programación dinámica de Held-Karp almacena, para cada subconjunto de ciudades y cada ciudad final, la forma más barata de visitar ese subconjunto. Cada estado se extiende con una ciudad no visitada a la vez, dando O(n al cuadrado por 2 elevado a n) tiempo, exacto pero solo factible para unas 20 ciudades. Las instancias mayores recurren a heurísticas como el vecino más cercano y 2-opt, o a metaheurísticas y solucionadores de ramificación y acotación que alcanzan recorridos casi óptimos para miles de ciudades.
El TSP modela la planificación de rutas de reparto, la preparación de pedidos en almacén, el taladrado de circuitos impresos, el ensamblaje de secuencias de ADN y la programación de observaciones de telescopios. Ancla el estudio de la NP-completitud y los algoritmos de aproximación, y los entrevistadores lo usan para sondear la comprensión de las clases de complejidad y la programación dinámica sobre máscaras de bits.
No existe un algoritmo exacto rápido para el problema del viajante, así que la respuesta práctica tiene dos etapas: construir una ruta decente deprisa y luego mejorarla localmente hasta que deje de mejorar.
// Etapa 1: vecino más cercano, construye una gira en O(n^2)
gira = [inicio]
mientras quede alguna ciudad sin visitar:
siguiente = ciudad sin visitar más cercana a gira.última
gira.añadir(siguiente)
gira.añadir(inicio) // cerrar el ciclo
// Etapa 2: 2-opt, elimina cruces hasta que nada mejore
repetir hasta que no haya mejora:
para cada par de aristas (a,b) y (c,d) de la gira:
si dist(a,c) + dist(b,d) < dist(a,b) + dist(c,d):
invertir el tramo de la gira entre b y c
// Exacto, para n pequeño: programación dinámica Held-Karp
dp[S][j] = mín sobre k en S\{j} de dp[S\{j}][k] + dist(k, j)Vale la pena entender el movimiento 2-opt de forma geométrica. Si dos aristas de una gira se cruzan, intercambiar sus extremos e invertir el tramo intermedio siempre acorta la gira por la desigualdad triangular. Así que 2-opt es, literalmente, la operación de deshacer los nudos de un lazo de cuerda.
Aplica vecino más cercano y luego 2-opt a cuatro ciudades situadas en las esquinas de un rectángulo, donde la elección voraz puede fallar de forma demostrable.
Grafo de ejemplo: Ciudades A(0,0), B(0,3), C(4,3), D(4,0). Distancias: A-B 3, B-C 4, C-D 3, A-D 4, y ambas diagonales A-C y B-D valen 5.
La gira óptima es el perímetro del rectángulo con coste 14, no ninguna de las giras con diagonales cruzadas a 18. Esta es toda la historia de las heurísticas para TSP en miniatura: una pasada constructiva rápida se acerca, y la búsqueda local elimina los cruces que introdujo la elección voraz.
Tiempo: O(n^2) heurístico, O(n^2 · 2^n) exacto · Espacio: O(n^2) heurístico, O(n · 2^n) exacto
Vecino más cercano recorre todas las ciudades restantes en cada uno de los n pasos, lo que da O(n al cuadrado). Cada barrido de 2-opt prueba los O(n al cuadrado) pares de aristas y se repite hasta que no hay mejora, lo cual es rápido en la práctica pero carece de cota útil en el peor caso. Held-Karp es exacto y llena una tabla indexada por subconjunto y extremo: hay 2 elevado a n subconjuntos por n extremos, y cada entrada cuesta O(n), de ahí O(n al cuadrado por 2 elevado a n) en tiempo y O(n por 2 elevado a n) en memoria. Eso supone un muro duro en torno a n = 20 o 25, ya que 2 elevado a 25 por 25 ya supera los mil millones de entradas. La fuerza bruta sobre todas las permutaciones es mucho peor, con O(n factorial).
El método adecuado depende casi por completo de cuántas ciudades tengas y de si necesitas un óptimo demostrable.
| Alternativa | Prefiérela cuando | Coste |
|---|---|---|
| Programación dinámica Held-Karp | Menos de unas 20 ciudades y necesitas una gira óptima garantizada. | O(n^2 · 2^n) |
| Christofides | Las distancias cumplen la desigualdad triangular y quieres una cota demostrada: nunca peor que 1,5 veces el óptimo. | O(n^3) |
| Vecino más cercano más 2-opt | De cientos a miles de ciudades y basta con una gira a pocos puntos porcentuales del óptimo. | O(n^2) por pasada |
| Lin-Kernighan | Instancias grandes donde la calidad importa más que el esfuerzo de implementación. El estado del arte práctico. | cerca de O(n^2.2) |
| Solucionadores de rutas de vehículos | El problema real tiene varios vehículos, capacidades o ventanas horarias. Entonces no es TSP en absoluto. | variable |
Leer el artículo completo: The Traveling Salesperson Problem Explained
Algoritmos relacionados: Camino Hamiltoniano, Rutas con Múltiples Vehículos, Rutas de Vehículos con Capacidad