# El problema del viajante - Sitio: Ikusmira — enciclopedia en castellano de ciencias sociales y humanidades - URL canónica: https://ikusmira.org/p/el-problema-del-viajante/ - Categoría: Informática - Publicado: 2026-05-24 - Autoría: Josemari Sarasola Ledesma — Editor coordinador; Profesor titular de escuela universitaria, Universidad del País Vasco/Euskal Herriko Unibertsitatea - Perfiles del autor: https://ekoizpen-zientifikoa.ehu.eus/investigadores/127490/detalle, https://dialnet.unirioja.es/servlet/autor?codigo=333202 - Política editorial (autoría, revisión, correcciones, financiación): https://ikusmira.org/politica-editorial/ El **problema del viajante** (en inglés, *travelling salesman problem*, TSP) pide lo siguiente: dadas unas ciudades y la distancia entre cada par, encontrar el recorrido más corto que pase por todas una sola vez y vuelva al punto de partida. Se enuncia en una frase, cualquiera lo entiende y nadie sabe resolverlo deprisa. Con *n* ciudades hay (*n* − 1)! / 2 recorridos posibles, y la cuenta se dispara: diez ciudades dan 181.440 rutas, quince, más de cuarenta mil millones, y veinte, unos sesenta mil billones. Probarlas todas deja de ser una opción antes de que el mapa deje de caber en una servilleta. La figura de esta página reparte ciudades al azar y prueba tres estrategias. «Vecino más cercano» hace lo que haría una persona con prisa: ir siempre a la ciudad más próxima que quede por visitar. «Mejorar» toma esa ruta y deshace cruces: cada vez que dos tramos se cortan, cambiarlos por los dos que no se cortan acorta el recorrido, y se repite hasta que no quedan cruces. «Óptimo» calcula el mejor recorrido de verdad, lo que la figura solo puede permitirse porque hay pocas ciudades. La lectura compara las tres longitudes y dice cuántas rutas había. Lo primero que enseña la figura es que lo fácil no es tan malo. El vecino más cercano da rutas un veinte o un veinticinco por ciento más largas que la óptima, de media, y suele terminar con un tramo larguísimo de vuelta a casa, porque ha ido dejando atrás ciudades aisladas. Deshacer cruces, un método que se llama 2-opt y que se conoce desde los años cincuenta, recorta buena parte de esa diferencia. Lo segundo es que el óptimo no se puede comprobar mirando: una ruta sin cruces y de aspecto razonable puede ser varios puntos por ciento más larga que la mejor, y la única manera de saberlo es haber descartado todas las demás, o tener una cota matemática que diga que ninguna puede bajar de cierta longitud. Esa es la dificultad de fondo, y tiene nombre desde 1972. Richard Karp demostró ese año que el viajante pertenece a una familia de problemas, los NP-completos, con una propiedad extraña: si alguien encontrara para uno cualquiera de ellos un algoritmo cuyo tiempo creciera como una potencia del tamaño, un polinomio en el lenguaje de [la notación O grande](https://ikusmira.org/p/la-notacion-o-grande/), lo habría encontrado para todos. Entre ellos están el horario de un colegio, el reparto de la carga de un camión y la rotura de muchos cifrados. Nadie ha encontrado ese algoritmo ni ha demostrado que no exista; es el problema de si P es igual a NP, el más famoso de la informática teórica. Lo mejor que se sabe hacer con garantías es la [programación dinámica](https://ikusmira.org/p/la-programacion-dinamica/) de Held y Karp, de 1962, que resuelve el problema en un tiempo del orden de *n*² por 2 elevado a *n*: es lo que usa el botón «Óptimo» de la figura y, con un millón de veces menos trabajo que probar todas las rutas, sigue siendo exponencial. La historia del problema es la de aprender a resolver lo que no se puede resolver. Karl Menger lo planteó en Viena en 1930, con el nombre de problema del mensajero, y en Princeton se le puso el del viajante durante esa década. En 1954, George Dantzig, Ray Fulkerson y Selmer Johnson resolvieron en la RAND Corporation un mapa de 49 ciudades, una por estado de Estados Unidos más Washington, con un método que no probaba rutas sino que las acotaba. Relajaban el problema a uno de programación lineal, que sí se resuelve rápido, y añadían una desigualdad cada vez que la solución relajada hacía algo que un recorrido de verdad no puede hacer, como partirse en dos ciclos. Ese método de planos de corte es el que, con sesenta años de refinamientos, resolvió en 2004 las 24.978 ciudades de Suecia y en 2006 un mapa de 85.900 puntos, los agujeros de un circuito integrado que una máquina debía perforar, el mayor caso del viajante resuelto hasta la fecha con demostración de optimalidad. William Cook, uno de los autores de ese programa, llamado Concorde, lo cuenta en su libro de 2012. Para los casos en que no hace falta la certeza hay dos escuelas. La de las garantías la fundó Nicos Christofides en 1976 con un algoritmo que, si las distancias cumplen la desigualdad triangular, nunca da una ruta más de un 50 por ciento más larga que la óptima. Esa cota pareció inmejorable durante 44 años, hasta que en 2020 Anna Karlin, Nathan Klein y Shayan Oveis Gharan la bajaron en una cantidad del orden de una billonésima de billonésima de billonésima, que no cambia ninguna ruta pero demuestra que el muro se puede mover. La escuela de la práctica no promete nada y lo hace casi todo: las heurísticas de la familia de Lin y Kernighan, que deshacen cruces de maneras más elaboradas que la figura, encuentran en minutos rutas a menos de un uno por ciento de la óptima para millones de ciudades. Son lo que hay dentro de los programas que planifican los repartos de paquetería, el orden en que una máquina taladra una placa, la secuencia en que un telescopio apunta a sus objetivos de la noche o el camino de un operario por los pasillos de un almacén. Lo que hace al viajante tan buen ejemplo es el contraste con su primo. Encontrar el camino más corto entre dos ciudades lo resuelve [el algoritmo de Dijkstra](https://ikusmira.org/p/el-algoritmo-de-dijkstra/) en una fracción de segundo para el mapa entero de Europa; encontrar el camino más corto que pase por todas no se sabe resolver para un mapa de cien sin astucia. Los dos enunciados se parecen y están a una distancia que la informática no ha conseguido medir en cincuenta años. Mientras tanto, los paquetes llegan: con rutas que nadie puede demostrar óptimas y que casi nunca están lejos de serlo. [La programación dinámica](https://ikusmira.org/p/la-programacion-dinamica/) – [El algoritmo de Dijkstra](https://ikusmira.org/p/el-algoritmo-de-dijkstra/) – [La notación O grande](https://ikusmira.org/p/la-notacion-o-grande/) – [Los algoritmos de ordenación](https://ikusmira.org/p/los-algoritmos-de-ordenacion/) – [La búsqueda en anchura y en profundidad](https://ikusmira.org/p/la-busqueda-en-anchura-y-en-profundidad/) ## Fuentes - Karl Menger — *Das Botenproblem*, Ergebnisse eines Mathematischen Kolloquiums 2 (1932) - George Dantzig, Ray Fulkerson y Selmer Johnson — *Solution of a Large-Scale Traveling-Salesman Problem*, Journal of the Operations Research Society of America 2 (4) (1954) — https://doi.org/10.1287/opre.2.4.393 - Richard M. Karp — *Reducibility Among Combinatorial Problems*, Complexity of Computer Computations, Plenum Press (1972) — https://doi.org/10.1007/978-1-4684-2001-2_9 - Nicos Christofides — *Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem*, Operations Research Forum 3 (20), reedición del informe de 1976 (2022) — https://doi.org/10.1007/s43069-021-00101-z - William J. Cook — *In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation*, Princeton University Press (2012) - Anna R. Karlin, Nathan Klein y Shayan Oveis Gharan — *A (Slightly) Improved Approximation Algorithm for Metric TSP*, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021) — https://doi.org/10.1145/3406325.3451009 --- Cómo citar: Sarasola, Josemari (2026). «El problema del viajante». Ikusmira. https://ikusmira.org/p/el-problema-del-viajante/ Índice del sitio para modelos: https://ikusmira.org/llms.txt