Nota dominical: El problema del viajante

Por Francisco R. Villatoro, el 31 marzo, 2013. Categoría(s): Ciencia • Informática • Noticias ✎ 4

Dibujo20130325 travel salesman - 13509 cities with more than 500 people in USA 1998

El problema del viajante consiste en encontrar el camino más corto que permite visitar una serie de ciudades conectadas por carreteras volviendo al punto de partida y visitando cada ciudad una sola vez. No hay ningún algoritmo eficiente para resolver este problema (que es NP-duro [1]). En 1950 los ordenadores permitían resolver un problema con 50 ciudades, en 1980 con unas 2300 ciudades y en 2006 se alcanzó el récord actual, 85900 ciudades (en la figura aparecen 13509 ciudades de EEUU). Los informáticos han tratado de descubrir algoritmos eficientes que aproximen la solución del problema. En 1976, Nicos Christofides (Imperial College, Londres) desarrolló un algoritmo eficiente que produce caminos cuyo coste excede al óptimo en menos del 50% [2]. ¿Se puede mejorar? En 2011, se logró mejorar el algoritmo de Christofides con un nuevo algoritmo eficiente que excede del óptimo en menos del 49,99999999999999999999999999999999999999999999999996 por ciento [3]. ¿Por qué ha costado tanto obtener una ventaja tan pequeña? Nadie lo sabe, pero resulta muy sugerente. Nos lo cuenta Erica Klarreich, «Computer Scientists Take Road Less Traveled. After decades without progress, new shortcuts are discovered in the traveling salesman problem,» Simons Foundation, Jan 29, 2013.

Referencias

[1] Richard M. Karp (Univ. California at Berkeley), «Reducibility among combinatorial problems,» pp 219-241 in «50 Years of Integer Programming 1958-2008,» Springer, 2010 [free pdf].

[2] N. Christofides, «Worst case analysis of a new heuristic for the traveling salesman problem,» Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.

[3] Shayan Oveis Gharan, Amin Saberiy, Mohit Singh, «A Randomized Rounding Approach to the Traveling Salesman Problem,» IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011, pp. 550-559 [free pdf].



4 Comentarios

  1. tienen que dividirlo, ningun algoritmo lo puede cubrir todo, deben de hacer paquetes logicos, ejemplo, los que pueda la salud de un ser humano cubrir, y entonces, si podran lograrlo, eso mismo pasa actualmente con la fisica, que quieren explicar todas las funciones en una sola ecuacion y no se puede, lo que mas, fue logrado, fue la ecuacion de Albert Einstein, que ahora quieren cambiarla, por favor, pongan atencion, en la cuantica, si comen mucho, engordaran y enfermaran, es por eso que cuando se quiere obtener mas, nunca se logra, y si se logra, violamos las leyes cuanticas.

  2. Muy buena nota. La verdad que es muy interesante como un problema en apariencia sencillo, que teoricamente se puede formular y resolver en forma exacta, presenta tantas dificultades para resolverse en foma práctica. Yo lo uso de ejemplo para mostrarles a mis alumnos por que, a pesar de tener algoritmos de programación matemática exactos (para problemas lineales, por ejemplo), tenemos que decantarnos por aproximaciones heurísticas.

  3. aunque vean mal mi contestacion, podriamos poner de muestra a una pc, esta tiene muchas partes, por eso mismo, porque una sola configuracion no permite abarcar todas las funciones de una pc, pueden ser ciontroladas sus funciones por el mismo cerebro, pero no sus funciones podran ser ejecutadas por ese mismo cerebro, la alimentacion, las direcciones, el ram, el disco duro, los perifericos, etc, a ver si copian mi exposicion, o en el ser humano, puede hacer muchas cosas, su cerebro, virtualmente la inteligencia lo lleva todo acabo, pero coger el platano, lo hace la mano, desplazarse lo hacen los pies en la mayoria de los casos, y cuando faltan lo hacen las manos , alimentarse, la mano ayuda a la boca, el cerebro escucha, piensa, programa los movimientos y los actos, mas, no puede mandar al corazon a que no se pare o cuantas veces tiene que bombear, y solamente si falta oxigeno o riego, el cerebro queda fuera de las ordenes y no puede manipular dichos actos, es lo mismo, si no hacen paquetes, no podran unificar todo, en un solo paquete, asi mismo no pueden usar una sola ecuacion, para ver las funciones de la creacion, por ser vagos, trabajan el doble y eliminan las posibilidades de lograr todo junto, es mi opinion, en ayuda a razonar lo imposible.

  4. El problema del TSP es un magnífico ejemplo para ilustrar la potencia de los algoritmos basados en los paradigmas naturales: los algoritmos genéticos basados en los esquemas de evolución biológica, preferiblemente por reproducción sexual, y las redes neuronales, basados en esquemas cerebrales.

Deja un comentario