El problema del viajante explicado
Dale a un viajante una lista de ciudades y pídele el viaje más corto que visite cada una de ellas una vez y vuelva a casa. Cualquiera puede comprobar una ruta propuesta, y cualquiera puede mejorar a ojo una mala, pero nadie conoce un método rápido que encuentre siempre la mejor. El problema del viajante se ha convertido en el ejemplo por excelencia de problema difícil, y los métodos inventados para atacarlo planifican hoy repartos, taladran placas de circuito y ensamblan genomas.
El problema
Una ruta visita cada ciudad exactamente una vez y termina donde empezó; su longitud es la suma de las distancias del recorrido. La tarea es encontrar la ruta más corta. En la versión de aquí, las distancias son líneas rectas en un mapa, así que ir de A a C nunca es más largo que pasar por B: es el problema del viajante métrico. El matemático Karl Menger trató el acertijo hacia 1930, y el nombre se hizo común en las décadas siguientes, cuando lo estudiaron matemáticos de la RAND Corporation.
La explosión de rutas
Fija la ciudad de salida. Hay n − 1 opciones para la siguiente ciudad, n − 2 para la de después, y así sucesivamente, y cada ruta puede recorrerse en dos sentidos, de modo que hay (n − 1)! / 2 rutas. Para 10 ciudades son 181.440, algo fácil para un ordenador. Para 20 son unas 6 × 10¹⁶, y para 70 superan el número de átomos del universo observable. Los ordenadores más rápidos no ayudan mucho: cada ciudad adicional multiplica el trabajo por aproximadamente n.
NP-difícil
En 1972 Richard Karp demostró que la cuestión de si un grafo tiene una ruta circular que pase por todos los vértices, un ciclo hamiltoniano, pertenece a una familia de problemas NP-completos que son todos igual de difíciles. El problema del viajante la contiene, así que es NP-difícil. Un método rápido para resolverlo daría métodos rápidos para miles de otros problemas de planificación, logística y criptografía. Si existe tal método es la cuestión P frente a NP, uno de los problemas del milenio.
Un método exacto: Held–Karp
En 1962 Michael Held y Richard Karp, y de forma independiente Richard Bellman, usaron la programación dinámica. Para cada conjunto S de ciudades y cada ciudad j de S, se calcula el camino más corto que empieza en la ciudad de origen, visita exactamente las ciudades de S y termina en j. Cada valor se obtiene de los valores para S sin j, así que la tabla se rellena de los conjuntos pequeños a los grandes y al final sale la ruta más corta. Necesita unos n² · 2ⁿ pasos en lugar de n!, lo que para 30 ciudades es la diferencia entre minutos y la edad del universo, pero sigue creciendo exponencialmente.
Reglas de construcción rápidas
El vecino más cercano viaja siempre a la ciudad más próxima que aún no ha visitado. Es sencillo y rápido, pero tiende a dejar abandonadas algunas ciudades que hay que recoger al final con largos desvíos, de modo que sus rutas suelen ser alrededor de un 25 % más largas que la mejor. Los métodos de inserción, en cambio, mantienen un circuito cerrado y añaden las ciudades restantes una a una donde menos cuestan. En 1976 Nicos Christofides encontró una construcción que garantiza como mucho 1,5 veces el óptimo en cualquier mapa métrico, una cota que se mantuvo casi imbatida durante más de cuarenta años.
Mejorar una ruta: 2-opt
La búsqueda local parte de cualquier ruta y va haciendo pequeños cambios que la acortan. El movimiento clásico, 2-opt, quita dos aristas y vuelve a conectar los dos trozos al revés, lo que invierte el tramo entre ellas. Siempre que dos aristas se cruzan, este movimiento las descruza y ahorra longitud, así que una ruta que 2-opt no puede mejorar nunca se cruza consigo misma. En mapas aleatorios, las rutas 2-opt suelen quedar alrededor de un 5 % por encima del óptimo. Movimientos más potentes que intercambian tres aristas, o el método de profundidad variable de Lin y Kernighan de 1973, se acercan todavía más.
Recocido simulado
La búsqueda local puede quedarse atascada en una ruta en la que cada movimiento individual la empeora, aunque exista una ruta mucho mejor. El recocido simulado, aplicado a este problema por Scott Kirkpatrick, Daniel Gelatt y Mario Vecchi en 1983, toma prestada una idea de la metalurgia: acepta un movimiento peor con una probabilidad que depende de una temperatura, alta al principio y que se va bajando lentamente. Al principio la ruta vaga libremente; al final solo se aceptan mejoras. Con un enfriamiento lo bastante lento encuentra de forma fiable rutas muy buenas.
Explóralo
Abre la demo del problema del viajante para colocar hasta 200 ciudades al azar, en un círculo, en grupos, en una cuadrícula o donde hagas clic. Mira cómo el vecino más cercano deja abandonadas sus últimas ciudades, cómo 2-opt deshace cada cruce, sigue la temperatura del recocido simulado mientras se enfría y deja que Held–Karp demuestre la ruta más corta para hasta 12 ciudades. Comparar todos ejecuta cada método sobre el mismo mapa y muestra cuánto supera cada ruta a la más corta encontrada.
Preguntas frecuentes
¿Dónde se usa el problema del viajante?
Allí donde algo tiene que visitar muchos lugares en un orden eficiente: rutas de reparto y de recogida, el recorrido de un taladro o un láser sobre una placa de circuito, el orden en que un telescopio observa las estrellas, el orden de preparación de pedidos en un almacén y, con otras distancias, el orden de los fragmentos al ensamblar una secuencia de ADN.
¿Cuál es el mayor problema resuelto de forma exacta?
En 1954 George Dantzig, Ray Fulkerson y Selmer Johnson demostraron la ruta más corta por 49 ciudades de Estados Unidos. En 2006 el solucionador Concorde de David Applegate, Robert Bixby, Vašek Chvátal y William Cook demostró la ruta óptima por 85.900 puntos procedentes del diseño de un chip, tras años de tiempo de cálculo.
¿La ruta más corta está siempre libre de cruces?
Sí, en un mapa plano con distancias en línea recta. Si dos aristas se cruzaran, cambiarlas por dos lados del cuadrilátero que forman acortaría la ruta, así que una ruta con cruces no puede ser la más corta.
¿Las heurísticas dan siempre la misma ruta?
El vecino más cercano, la inserción más barata y 2-opt, tal como se usan aquí, son deterministas: con las mismas ciudades dan la misma ruta. El recocido simulado parte de una ruta aleatoria y hace movimientos aleatorios, así que dos ejecuciones pueden acabar con rutas distintas, normalmente de casi la misma longitud.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Abrir la demo del problema del viajante