Utilizamos cookies propias y de terceros para mejorar nuestros servicios y facilitarte el uso de la web mediante el análisis de tus preferencias de navegación. También compartimos la información sobre el tráfico por nuestra web a los medios sociales y de publicidad con los que colaboramos. Si continúas navegando, consideramos que aceptas nuestra Política de cookies .

1 de Agosto de 2012
Matemáticas

El caso del viajante

Al buscar una solución para este problema aparentemente irresoluble, los matemáticos están vislumbrando los límites del cálculo.
THOMAS FUCHS
¿Es inútil intentar calcular la ruta más corta para visitar un gran número de ciudades? No solo una buena ruta, sino la más corta de todas. Este ejercicio, uno de los retos matemáticos más antiguos, se denomina el problema del viajante (PV).
Hallar un método que resolviera con rapidez todos los casos del PV constituiría un impresionante avance para las matemáticas. Mediante la teoría de la complejidad, este método nos permitiría solucionar cualquier problema de computación para el que las respuestas pudieran ser verificadas con facilidad. Sin embargo, muchos matemáticos consideran que esto es imposible.
Supongamos que le facilitan la localización de 100.000 ciudades. ¿Es imposible encontrar la ruta más corta? No estamos preguntando por la solución a todos los casos particulares del PV, sino al camino más rápido entre todos esos puntos.
Para enfrentarte al reto, lo mejor es seguir el consejo del viejo entrenador de béisbol Yogi Berra: «Cuando encuentres una bifurcación en la carretera, tómala». La programación lineal nos permite hacer justamente eso: asignar fracciones a las carreteras que unen pares de ciudades en lugar de decidir al momento si tomar una carretera o no. En este modelo, no hay ningún problema en enviar medio vendedor por cada uno de los ramales. El proceso comienza con la condición de que, para cada ciudad, las fracciones asignadas a las carreteras de llegada y de salida sumen uno. Después se añaden otras condiciones, que implican la suma de las fracciones asignadas a cada vía. Al final, la programación lineal nos indica la mejor solución para cada una y, por tanto, el recorrido más corto posible.
Debo añadir que 100.000 ciudades no es un reto hipotético. Los cálculos actuales se están ajustando para un conjunto de 100.000 puntos creado por Robert Bosch, de la Universidad de Oberlin, en el que la ruta recorre un dibujo de la Mona Lisa. Puede que no consigamos resolver todos los ejemplos del PV, pero las nuevas ideas pueden ampliar los límites actuales de lo que es resoluble.
A grandes rasgos, la teoría de la complejidad sugiere que el alcance de las técnicas generales de cálculo en la ciencia y en otros campos es limitado. ¿Cuáles son estos límites y en qué medida restringen nuestra búsqueda de conocimientos? De eso trata la investigación del PV.

Puedes obtener el artículo en...

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.