El problema matemático del viajante (en inglés: Travelling Salesman Problem, TSP) es un clásico en el mundo de los algoritmos: encontrar la ruta más corta posible que visite cada ciudad una sola vez en un mapa, regresando a la ciudad de origen.
Como es de suponer, esto tiene miles de aplicaciones prácticas, pues también es un ejemplo de optimización y muchos problemas de otros campos pueden considerarse –matemáticamente– equivalentes. Si existiera un algoritmo definitivo no solo se podría ahorrar combustible y tiempo en los viajes, también optimizar cómo colocar los libros en una gran biblioteca o recorrer una calle para dejar los sobres de correo.
Por desgracia no existe un algoritmo definitivo: aunque a veces se puede encontrar la mejor solución si aumenta el número de nodos (en este caso: «ciudades») la complejidad del problema crece sobremanera; al cabo de un tiempo es fácil ver que no hay forma de probar todas las posibles soluciones ni de demostrar que una sea mejor que otra. Y aunque existen algoritmos parciales o para casos concretos –que son los que se utilizan en la práctica– debido entre otras cosas a que se sabe que es un problema NP-difícil (NP-hard) encontrar una forma de hacerlo supondría un gran avance matemático.
En la imagen un programa llamado Parano utiliza un algoritmo genético para resolver el TSP, mostrando visualmente los avances a medida que se producen: una forma original de resolverlo aunque probablemente no la óptima.
