Los informáticos rompen el récord de ‘vendedor ambulante’


Cuando Nathan Klein Empezó la escuela de postgrado hace un par de años, sus aconsejes plantearon un plan modesto: trabajar juntos en uno de los inconvenientes más conocidos y viejos de la informática teorética.

Historia original reimpresa con permiso de Revista Quanta, una publicación editorialmente independiente de la Fundación Simons cuya misión es progresar la entendimiento pública de la ciencia al cubrir los desarrollos de investigación y las tendencias en matemáticas y ciencias físicas y de la vida.

Incluso si no conseguían resolverlo, pensaron, Klein aprendería mucho en el proceso. Él estuvo conforme con la idea. “No sabía que debía intimidarme”, afirmó. «Yo era solo un estudiante de postgrado de primer año, no sé qué pasa».

Ahora, en un artículo publicado online en el mes de julio, Klein y sus aconsejes en la Universidad de Washington, Anna Karlin y Shayan Oveis Gharan, por último han conseguido un propósito que los científicos informáticos han perseguido a lo largo de prácticamente medio siglo: una mejor forma de localizar soluciones aproximadas a el inconveniente del vendedor itinerante.

Este inconveniente de optimización, que busca el viaje de ida y vuelta más corto (o bien menos costoso) mediante un conjunto de urbes, tiene aplicaciones que van desde la secuenciación de ADN hasta la logística de viajes compartidos. Durante las décadas, ha inspirado muchos de los avances más esenciales de la informática, ayudando a alumbrar el poder de técnicas como la programación lineal. Mas los estudiosos todavía deben explorar totalmente sus posibilidades, y no por estimar procurarlo.

El inconveniente del vendedor itinerante “no es un inconveniente, es una adicción”, como le agrada decir a Christos Papadimitriou, un señalado especialista en dificultad computacional.

La mayoría de los informáticos piensan que no hay un algoritmo que pueda localizar de forma eficaz las mejores soluciones para todas y cada una de las combinaciones posibles de urbes. Mas en mil novecientos setenta y seis, Nicos Christofides inventó un algoritmo que halla de forma eficaz soluciones aproximadas: viajes de ida y vuelta que son como máximo un cincuenta por ciento más largos que el mejor viaje de ida y vuelta. En ese instante, los informáticos aguardaban que alguien pronto mejorara el algoritmo simple de Christofides y se acercara a la auténtica solución. Mas el avance adelantado no llegó.

«Bastante gente pasó innumerables horas tratando de progresar este resultado», afirmó Amin Saberi de la Universidad de Stanford.

Ahora Karlin, Klein y Oveis Gharan han probado que un algoritmo concebido hace una década supera el factor del cincuenta por ciento de Christofides, si bien solo pudieron quitar 0,2 mil millonésimas de billonésimas de billonésimas de por ciento. No obstante, esta minúscula mejora rompe un atasco teorético y sicológico. Los estudiosos aguardan que abra las compuertas a nuevas mejoras.

“Este es un resultado que he querido mi carrera”, afirmó David Williamson de la Universidad de Cornell, quien ha estado estudiando el inconveniente de los vendedores itinerantes desde la década de mil novecientos ochenta.

El inconveniente del vendedor itinerante es de los pocos inconvenientes esenciales a los que los científicos informáticos teóricos recurren una y otra vez para probar los límites de la computación eficaz. El nuevo resultado «es el primero de los pasos para probar que las fronteras de la computación eficaz son en verdad mejores de lo que pensábamos», afirmó Williamson.

Progreso fraccional

Si bien seguramente no hay un procedimiento eficaz que siempre y en todo momento halle el viaje más corto, es posible localizar algo prácticamente tan bueno: el árbol más corto que conecta todas y cada una de las urbes, esto es, una red de conexiones (o bien “bordes”) sin bucles cerrados. El algoritmo de Christofides emplea este árbol como columna vertebral para un recorrido de ida y vuelta, añadiendo bordes auxiliares para transformarlo en un viaje de ida y vuelta.

Cualquier senda de ida y vuelta debe tener un número par de bordes en todos y cada urbe, en tanto que cada llegada es seguida por una salida. Resulta que lo opuesto asimismo es cierto: si cada urbe en una red tiene un número par de conexiones, los bordes de la red deben rastrear un viaje de ida y vuelta.

El árbol más corto que conecta todas y cada una de las urbes carece de esta propiedad de uniformidad, en tanto que cualquier urbe al final de una rama tiene solo una conexión con otra urbe. Entonces, para transformar el árbol más corto en un viaje de ida y vuelta, Christofides (que murió el año pasado) halló la mejor forma de conectar pares de urbes que tienen números impares de bordes. Entonces probó que el viaje de ida y vuelta resultante jamás va a ser más del cincuenta por ciento más largo que el mejor viaje de ida y vuelta posible.

Al hacerlo, inventó tal vez el algoritmo de aproximación más conocido de la informática teorética, uno que acostumbra a ser el primer ejemplo en los libros de texto y los cursos.

«Todo el planeta conoce el algoritmo simple», afirmó Alantha Newman de la Universidad de Grenoble Alpes y el Centro Nacional de Investigación Científica en Francia. Y cuando lo sabes, afirma, «conoces el estado del arte», cuando menos, lo sabías hasta julio pasado.

Deja un comentario