El del viajante es un problema clásico: ¿cuál es la mejor forma de recorrer muchas ciudades y volver a casa? [fragmento de una ilustración de Lucy Reading-Ikkanda/Quanta Magazine; foto, T.Dallas].
Un viajante tiene que visitar todas y cada una de las principales ciudades de Estados Unidos. ¿Cuál es la forma más barata de pasar por cada una de ellas justo una vez y volver luego a casa? Es famosa la inviabilidad de la computación de la mejor respuesta de este problema, llamado «del viajante». No obstante, los científicos de la computación saben desde hace mucho cómo encontrar una ruta bastante buena, una que no cuesta más que 1,5 veces el coste óptimo.
El problema del viajante tiene como premisa que un viaje entre dos ciudades cualesquiera costará lo mismo yendo en una o en la otra dirección. Pero a menudo no es así. Por ejemplo, un vuelo de Chicago a Denver podría ser más barato (o llevar menos tiempo) que uno de Denver a Chicago. Dar con la trayectoria de vuelo óptima en esas circunstancias (el llamado problema asimétrico del viajante) tampoco es factible computacionalmente. Pero al contrario que en la solución del problema ordinario del viajante, los investigadores no saben cómo encontrar una ruta cuasióptima para un viaje a un número grande de ciudades. O mejor dicho, así era hasta agosto de 2017, cuando tres científicos de la computación anunciaron que habían concebido un algoritmo de aproximación que es efectivo en todos los casos.
¿Por qué es tan difícil el problema asimétrico del viajante? En pocas palabras: cuando las rutas son más caras en un sentido que en el otro, hay muchas más rutas que tomar en cuenta. La dificultad añadida significa que, hasta ahora, todos los algoritmos de resolución del problema asimétrico del viajante o requerían demasiado tiempo o escogían rutas inservibles. El nuevo algoritmo, por lo tanto, «resuelve un problema persistente y es un logro de primera magnitud», han escrito Ken Regan, de la Universidad de Búfalo, y Dick Lipton, del Tecnológico de Georgia, en Gödel’s Lost Letter y P = NP, un blog que trata de la investigación actual sobre algoritmos.
«La primera vez que pensé en el problema fue durante mi doctorado, en 2008», cuenta Ola Svensson, uno de los tres autores del nuevo artículo. Tras sietes años de darle vueltas al asunto, Svensson dio con una solución para un problema más simple, el de juntar las ciudades en grupos y visitar al menos una de cada grupo.
Svensson reclutó entonces a Jakub Tarnawski y Lászlo Végh, sus coautores, para que le ayudasen a elaborar un nuevo algoritmo que formase repetidamente subgrupos menores dentro de los grupos de ciudades y encontrase rutas baratas dentro de cada grupo. Se casaban entonces las rutas dentro de cada grupo, de forma derivada de la investigación anterior de Svensson, para construir una ruta completa. Mientras que los intentos anteriores de resolver el problema asimétrico del viajante se valieron de enfoques similares, ninguno consiguió localizar los grupos de rutas baratas que se podrían casar.
Si bien el artículo no ha pasado todavía por la revisión por pares, Regan dice que tiene muchas posibilidades de aguantar el escrutinio de la comunidad de la ciencia de la computación. «Las ideas de la prueba son muy claras», afirma. «Hay un punto [técnico] potencialmente sensible … [pero es] muy sólido, muy prometedor y está bien estructurado y bien traído».
Svensson dice que sus colaboradores y él tienen pensando enviar el artículo a un congreso venidero (el quincuagésimo Simposio sobre Teoría de la Computación) para que pase una revisión por pares.
Mark H. Kim/Quanta Magazine
Artículo traducido por Investigación y Ciencia con permiso de QuantaMagazine.org, una publicación independiente promovida por la Fundación Simons para potenciar la comprensión de la ciencia.
Referencia: «A constant-factor approximation algorithm for the asymmetric traveling salesman problem», de Ole Svensson et al., en arXiv: 1708.04215 [cs.DS].
