Roto, 37 años después, el record del problema del viajante de comercio

Lo de batir records no es algo asociado solamente a deportes o ventas, en el mundo de las matemáticas y/o la computación también se puede dar y hoy, domingo de Carnaval, os traemos en Genbeta Dev un nuevo record en el mundo de los algoritmos de computación, concretamente se ha conseguido mejorar la mejor aproximación a uno de los problemas más clásicos y que todos hemos tenido que sufrir en alguna ocasión en nuestros años académicos: el viajante de comercio.

Para aquellos con memoria de pez recuerdo, a grandes rasgos, el contenido del problema: dadas una serie de ciudades conectadas por autopistas, encontrar la ruta más corta para visitarlas todas y retornar a la ciudad de salida. Al ser un problema que tiene un coste exponencial al aumentar el número de ciudades, la aproximación por fuerza bruta pues no es una buena solución genérica. La mejor solución hasta la fecha databa de 1976, se la conocía como algoritmo de Christofides y te da siempre una solución que es como mucho un 50 por ciento más costosa que la mejor.

Pues bien, investigadores de las universidades de Stanford y McGill han conseguido, 37 años después, mejorar el record del algoritmo de Christofides y presentar un algoritmo que te devuelve una solución que es como mucho un 49.99999999999999999999999999999999999999999999999996 por ciento más costosa que la mejor. Sí, es una mejora casi imperceptible pero seguro que en los campos donde la búsqueda del camino más corto es capital, como la genética o la circuitería, están aplaudiendo a dos manos hasta que les sangren las manos. Además afirman que esto es sólo el comienzo, que en cinco años conseguirán una mejora sustancial y realmente apreciable.

Si quieres conocer a fondo este nuevo algoritmo (y el de Christofides), no dudes en pasarte por la fuente original, que el artículo está supercurrado.

Vía | Simons Foundation