Imaginá que sos un vendedor de máquinas de coser y debés reunirte con potenciales clientes en una cierta cantidad de ciudades distintas. Entre ciudad y ciudad debés desplazarte en tu propio auto y, para ahorrar tiempo y costos, buscás minimizar la distancia recorrida. En la superficie este parece un problema de optimización simple pero en la práctica es considerado uno de los problemas más difíciles de la ciencia de la computación.

La cuestión del ejercicio, planteado por el matemático W.R. Hamilton en el siglo XIX, parte del problema de que hay una cantidad exponencial de rutas posibles a medida que aumenta la cantidad de ciudades (para 15 ciudades hay 32.768 rutas posibles) y por lo tanto encontrar la ruta óptima se hace cada vez más difícil. Utilizar la analogía de un vendedor recorriendo una cierta cantidad de ciudades es metafórico y este problema debe ser resuelto en muchas situaciones incluidos la fabricación de microchips, logística y hasta para la secuenciación del ADN. Actualmente, existen numerosos algoritmos que permiten aproximar este problema pero ninguno que permita resolverlo con exactitud, los más utilizados con una precisión de 1 al 2%.

Por ejemplo, una aplicación en la práctica de la optimización “Travelling Salesman Problem” es crear una ruta óptima entre distintos puntos de un país, como hizo Randall Olson al unir las 50 mejores atracciones de Europa en la ruta por auto más corta en el plano a continuación utilizando un algoritmo de tipo genético, un viaje “óptimo” a través de Europa. Este viaje, como se ve en la imagen a continuación, implica recorrer una distancia de 26.000 kilómetros y manejar durante 14 días continuos.

Gracias a este problema, quizás te topes con un pequeño inconveniente la próxima vez que te toque organizar un viaje en donde intentes reducir los costos de transporte o el tiempo al mínimo si tenés muchas paradas. La mala noticia es que muy posiblemente no encuentres la solución “óptima” para tu viaje,  pero la buena noticia es que si encontrás una solución que sirva para n cantidad de ciudades seguramente ganes el premio Nobel.

Foto de portada: ..