no hace mucho tiempo, un equipo de investigadores de las universidades de Stanford y McGill rompió un récord de 35 años en Ciencias de la computación por un margen casi imperceptible: cuatro centésimas de trillonésima de trillonésima de trillonésima de un porcentaje, para ser exactos., El avance-hecho a ese niño del cartel para los dilema difíciles de resolver de la informática, el problema del «vendedor ambulante» – era demasiado minúsculo tener cualquier significado práctico inmediato, pero ha insuflado nueva vida en la búsqueda para las soluciones aproximadas mejoradas.

*historia original reimpresa con permiso de Simons Science News, una división editorialmente independiente de SimonsFoundation.org cuya misión es mejorar la comprensión pública de la ciencia cubriendo los desarrollos y tendencias de la investigación en matemáticas y las Ciencias Computacionales, físicas y de la vida.,* El problema del vendedor ambulante pregunta: dado un conjunto de ciudades conectadas por carreteras, ¿Cuál es la ruta más corta que visita cada ciudad y regresa al lugar de partida? La respuesta tiene aplicaciones prácticas para procesos como perforar agujeros en placas de circuitos, programar tareas en una computadora y ordenar características de un genoma.

Ver más

el problema del vendedor ambulante es fácil de declarar y, al menos en teoría, se puede resolver fácilmente comprobando cada ruta de ida y vuelta para encontrar la más corta., El problema con este enfoque de fuerza bruta es que a medida que crece el número de ciudades, El número correspondiente de viajes de ida y vuelta para verificar supera rápidamente las capacidades de las computadoras más rápidas. Con 10 ciudades, hay más de 300,000 diferentes viajes de ida y vuelta__.__ Con 15 ciudades, El número de posibilidades se eleva a más de 87 mil millones.,

algoritmo de Christofides

en los primeros días de las computadoras, los matemáticos esperaban que alguien ideara un enfoque mucho mejor para los grandes problemas de los vendedores ambulantes: algún algoritmo que permitiera a las computadoras resolverlos en una cantidad razonable de tiempo. Pero si bien los científicos de la computación han avanzado con escenarios específicos, identificando la ruta de ida y vuelta más corta para__ un mapa de 49 ciudades en la década de 1950, un mapa de 2,392 ciudades en la década de 1980 y un mapa de 85,900 ciudades en 2006, nadie ha ideado un algoritmo que pueda resolver de manera eficiente todos los problemas de los vendedores ambulantes., Según un documento histórico publicado en 1972, tal solución podría ni siquiera ser posible. El científico de computación Richard Karp, de la Universidad de California en Berkeley, _ _ mostró que el problema del vendedor ambulante es «NP-hard», lo que significa que no tiene un algoritmo eficiente (a menos que una famosa conjetura llamada P=NP sea cierta, pero la mayoría de los científicos de computación ahora sospechan que es falso).

después de que se publicó el artículo de Karp, muchos científicos de la computación fijaron su mirada en la creación de un algoritmo eficiente para encontrar soluciones aproximadas al problema del vendedor ambulante: rutas de ida y vuelta cuyas longitudes se encuentran a una distancia sorprendente de la de la mejor ruta posible., Aquí, tuvieron mejor suerte: en 1976, nicos Christofides, profesor del Imperial College de Londres, desarrolló un algoritmo que produce rutas garantizadas como máximo un 50 por ciento más largas que la ruta más corta.

Cuando fue creado, muchos científicos de la computación asumieron que el algoritmo de Christofides, que es lo suficientemente simple como para enseñar a estudiantes de Ciencias de la computación en una hora, era un marcador de posición que eventualmente daría paso a un algoritmo más sofisticado capaz de aproximarse mejor a la verdadera solución. Sin embargo, durante décadas, ese algoritmo no se materializó.,

«casi todos los estudiantes graduados en Ciencias teóricas de la computación han pasado en algún momento unas semanas o meses inútiles tratando de mejorar el algoritmo de Christofides», dijo Sanjeev Arora, un científico informático de la Universidad de Princeton.

finalmente en 2011, el equipo de Stanford-McGill superó la garantía del 50 por ciento de Christofides para ciertos tipos de problemas de vendedores ambulantes, mostrando que las soluciones de su algoritmo estarían a lo 49.99999999999999999999999999999999999999999999999999996 por ciento más que la verdadera respuesta.,

una serie de Algoritmos de aproximación mejorados han surgido desde entonces, después de que los científicos de la computación comenzaron a mirar el problema con nuevos ojos. Aunque estas aproximaciones se aplican solo a ciertos tipos de problemas de vendedores ambulantes, el enfoque que encarnan es muy prometedor, dijo Michel Goemans, un informático del Instituto de tecnología de Massachusetts.

«apenas Hemos arañado la superficie», dijo. «Creo firmemente que, tal vez cinco años después, habrá un resultado mucho más poderoso.,»

El árbol más corto

El algoritmo de Christofides comienza buscando no la ruta de ida y vuelta más corta, sino el «árbol de expansión» más corto: una colección de ramas que unen las ciudades, sin bucles cerrados. A diferencia de la ruta de ida y vuelta más corta, el árbol de expansión más corto es fácil de construir de manera eficiente: comience por encontrar la carretera más corta que conecta dos ciudades; esa es la primera rama. Para agregar la siguiente rama, encuentre la carretera más corta que conecta una nueva ciudad con una de esas dos, y así sucesivamente hasta que se hayan alcanzado todas las ciudades.,

el árbol resultante no es una posible solución al problema del vendedor ambulante porque no crea una ruta de ida y vuelta. Pero se puede convertir en un viaje de ida y vuelta visualizando las ramas como paredes y luego imaginando caminar a lo largo del árbol, con el dedo tocando la pared, hasta que regrese a donde comenzó. El viaje resultante visita cada ciudad y regresa al punto de partida, pero por lo general está lejos del camino más corto para hacerlo, ya que normalmente implica volver sobre los pasos muchas veces — cada pared en el árbol se atraviesa dos veces, una a cada lado.,

Sin embargo, esta ruta de ida y vuelta es, en el peor de los casos, el doble de larga que la mejor solución al problema del vendedor ambulante. Al agregar algunas carreteras cuidadosamente elegidas a este árbol y tomar algunos atajos inteligentes, Christofides mostró cómo recortar este viaje de ida y vuelta a uno que sea como máximo un 50 por ciento más largo que la ruta más corta.

el árbol de expansión más corto fue un punto de partida natural para los esfuerzos por construir un recorrido corto de ida y vuelta., Pero este enfoque también ofreció una oportunidad para los investigadores que intentaban reducir la garantía del 50 por ciento de Christofides. Porque aunque el árbol de extensión más corto parece efectivo al principio, otros árboles pueden ser mejores cuando se trata del proceso de corta que convierte el árbol en un viaje de ida y vuelta; por ejemplo, un árbol que nunca se ramifica solo necesita una carretera adicional para convertirse en un viaje de ida y vuelta.

así que el objetivo era encontrar un árbol de expansión que logre el equilibrio perfecto entre la longitud y la fácil conversión en un viaje de ida y vuelta., Ningún algoritmo eficiente puede descubrir este árbol perfecto (a menos que P=NP), pero un algoritmo de aproximación exitoso solo necesita encontrar uno bastante bueno.

un viaje fraccionario

El camino hacia ese árbol de expansión «bastante bueno» ha involucrado la técnica ampliamente utilizada pero contraintuitiva de permitir soluciones fraccionadas a ciertos tipos de problemas. Un viaje de ida y vuelta fraccionario, por ejemplo, podría implicar ir en la mitad de la carretera de Minneapolis a Detroit y la mitad de la carretera de Cleveland a Detroit. Tal ruta es, por supuesto, un sinsentido desde una perspectiva práctica., Pero se puede formular en términos matemáticos precisos y, a diferencia del problema estándar del vendedor ambulante, esta versión fraccionada se puede resolver de manera eficiente.

muchos problemas de aproximación en Ciencias de la computación se pueden abordar mediante el cálculo de la solución a la versión fraccional del problema y luego encontrar una manera inteligente de redondear las fracciones para producir una solución aproximada al problema original. Pero hasta hace poco, nadie había descubierto una buena manera de hacer esto para el problema del vendedor ambulante.,

en 2009, Amin Saberi de la Universidad de Stanford y Arash Asadpour, entonces un estudiante graduado, desarrollaron una técnica de redondeo general que utiliza la aleatoriedad para tratar de elegir una solución de número entero que conserva tantas propiedades de la solución fraccionada como sea posible. Saberi vio esta nueva técnica de redondeo como » un martillo fuerte en busca de un clavo.»El clavo correcto, sospechó, podría ser el problema del vendedor ambulante.,

unos meses más tarde, Saberi, Asadpour, Goemans, el estudiante graduado de Stanford Shayan Gharan, y Aleksander Madry, ahora de la École Polytechnique Fédérale de Lausanne en Suiza, demostraron que la nueva técnica de redondeo podría producir un buen algoritmo de aproximación para una variación del problema del vendedor ambulante, el «caso asimétrico». Al año siguiente, Saberi, Gharan y Mohit Singh de la Universidad McGill utilizaron el mismo enfoque para desarrollar un nuevo algoritmo de aproximación para el problema del vendedor ambulante ordinario.,

dado un mapa de ciudades y carreteras, el nuevo algoritmo comienza calculando la solución fraccional exacta al problema del vendedor ambulante. A continuación, redondea esa solución fraccionada a un árbol de expansión que, con suerte, se acercará al deseado equilibrio entre la longitud y la fácil conversión a un viaje de ida y vuelta. Finalmente, el algoritmo conecta ese árbol de expansión — en lugar del árbol de expansión más corto-en el marco de Christofides.

el nuevo algoritmo fue «una idea que podríamos describir en una hora o dos, pero demostrar que realmente funcionó tomó más como un año», dijo Saberi.,

después de un largo análisis, el equipo de Stanford-McGill finalmente fue capaz de superar el algoritmo de Christofides por un pequeño margen para los problemas «gráficos» de los vendedores ambulantes, una amplia subclase. En pocos meses, otros grupos, energizados por el éxito del equipo Stanford-McGill, utilizaron otras técnicas de redondeo para producir algoritmos para el caso gráfico con mejores aproximaciones; el récord actual se sitúa en el 40 por ciento, una mejora sustancial sobre el 50 por ciento de Christofides.,

el caso gráfico «encapsula muchas de las mismas dificultades que se encuentran en el problema general», dijo Arora, y agregó que las mismas técnicas que funcionan para el caso gráfico pueden aplicarse al problema general del vendedor ambulante.

Sin embargo, dijo Saberi, resolver el problema de aproximación del vendedor ambulante en toda su generalidad probablemente requerirá una infusión de nuevas ideas.,

«El descubrimiento matemático es como abrirse camino en una habitación oscura: poner la mano aquí y encontrar una silla, poner la mano allí y encontrar una mesa», dijo, parafraseando al matemático Andrew Wiles. «En algún momento, tu mano golpea el interruptor de la luz, y de repente todo tiene sentido. Para el problema del vendedor ambulante, incluso después de tantos papeles que han empujado el sobre en tantas direcciones, no creo que hayamos golpeado ese interruptor todavía.»

historia original reimpresa con permiso de Simons Science News, una división editorialmente independiente de SimonsFoundation.,org cuya misión es mejorar la comprensión pública de la ciencia cubriendo los desarrollos y tendencias de investigación en matemáticas y Ciencias Computacionales, físicas y de la vida.