Actualidad informática

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.

Ampliar en:  microsiervos