Averiguar la mejor ruta tenía un problema no resuelto en 70 años. Un algoritmo ha dado con la solución en lo que tardas en pestañear

En la década de 1950 los científicos informáticos se dieron cuenta de algo. Mientras la sociedad avanzaba y se hacía más grande y densa junto a sus redes de transporte, las ralentizaciones, aglomeraciones o congestiones de tráfico de todo tipo se hacían más palpables. Desde entonces, no han cesado las ideas y propuestas buscando resolver el problema de los “atascos” y sus flujos más eficientes. La solución estaba en un algoritmo "absurdamente rápido".

El anuncio. Un equipo de investigadores de la ETH de Zúrich ha presentado en el  Simposio Anual de la ACM sobre Teoría de la Computación lo que, en teoría, es el algoritmo de flujo de red más rápido posible. El trabajo pionero del equipo capitaneado por el investigador Rasmus Kyng aborda la largamente analizada cuestión de cómo lograr el flujo máximo en una red y, al mismo tiempo, minimizar los costes de transporte.

Un ejemplo antes de explicarlo más detallado. Imagina que estás utilizando una red de transporte europea buscando la ruta más rápida y barata para transportar la mayor cantidad posible de mercancías desde Madrid a Londres. El algoritmo de Kyng se puede aplicar en estos casos para calcular el flujo de tráfico óptimo y de menor coste para cualquier tipo de red, ya sea ferroviaria, vial, fluvial o de Internet. Y lo hace tan rápido que asusta: puede proporcionar la solución en el mismo momento en que un ordenador lee los datos que describen la red.

Contexto. Como decíamos al inicio, el alcance de lo conseguido por el equipo de Kyng es un hito. Un logro que ofrece una solución sin igual a un problema que ha estado atormentando a los investigadores desde hace 70 años: el flujo máximo, o cómo lograr el flujo más rápido de información a través de un sistema con capacidad limitada.

Historia de un problema no resuelto. El problema del flujo máximo fue formalizado en la década de 1950 por Lester R. Ford y Delbert Fulkerson, quienes introdujeron un famoso algoritmo, conocido como el algoritmo Ford-Fulkerson, para resolverlo. El problema nació en el contexto de la planificación de infraestructuras, como redes de transporte, suministro de agua y telecomunicaciones. En el mismo, se tiene una red dirigida donde cada arista tiene una capacidad que indica la cantidad máxima de flujo que puede pasar a través de ella.

La propuesta Ford-Fulkerson fue uno de los primeros métodos propuestos para resolver el rompecabezas a través de lo que llamaron "solución codiciosa". Funciona buscando caminos aumentantes, es decir, rutas desde la fuente hasta el sumidero donde el flujo se pueda incrementar. Una vez se encuentra un camino con capacidad disponible, se aumenta el flujo en esa ruta y se repite el proceso hasta que ya no se pueda encontrar un camino disponible.

El ejemplo. Para entenderlo, nada mejor que la cuestión que plantearon. Imagina el problema de optimizar el tráfico que se desplaza de A a B a lo largo de múltiples rutas posibles, una ruta formada por un primer segmento que es una autopista de seis carriles y el último una carretera de tres carriles. Para resolverlo, el algoritmo codicioso lanza tanto tráfico como sea posible (tres carriles de automóviles) a lo largo de la ruta, ajustando su capacidad y repitiendo los mismos pasos para otras rutas hasta que todas las rutas posibles estén a plena capacidad.

Y sí, lo cierto es que la propuesta de los investigadores era eficaz, pero tenía un problema: muchas veces no producía el mejor flujo posible. Si se cortaban otras rutas y surgían atascos no óptimos, el algoritmo decidía dejarlo así. Durante 70 años se han dado contribuciones al problema intentando refinar ese aspecto de la solución, suavizando las ralentizaciones innecesarias mediante la incorporación de una mejor toma de decisiones en el algoritmo.

Pequeñas mejoras. Por ejemplo, el algoritmo fue perfeccionado más tarde con implementaciones más eficientes, como el algoritmo de Edmonds-Karp, que usa una búsqueda en anchura para encontrar el camino aumentante más corto. Este y otros ajustes cambiaron el tiempo de ejecución del algoritmo de un múltiplo de m^2 (donde m es el número de nodos de la red) a un múltiplo de m^1,33 en 2004, pero luego el progreso se estancó.

El algoritmo “absurdamente rápido”. Y llegamos al revolucionario anuncio de estos días. Para ello, Kyng y su equipo combinaron los anteriores: la solución original que trataba las redes como tráfico; y una posterior que, en cambio, las consideraba como una red eléctrica. A diferencia de los autos o trenes, el flujo de electrones se puede desviar parcialmente para unirse a la corriente a lo largo de otra ruta, lo que permite a los científicos informáticos trazar el mejor flujo a través de toda la red antes de aplicar el enfoque del tráfico segmento por segmento.

Esta combinación dio algo así como un resultado de algoritmo híbrido, uno "absurdamente rápido", según la declaración de Daniel A. Spielman, profesor de matemáticas aplicadas y ciencias de la computación en la Universidad de Yale que supervisó el programa de doctorado de uno de los investigadores. De hecho, Spielman comparó la nueva solución con las anteriores, como si fuera "un Porsche que adelanta a los carruajes tirados por caballos".

Una comparación certera, y un avance que promete revolucionar muchos campos, desde los datos de Internet, las rutas de tráfico y transporte, la programación de vuelos en la red, hasta la mejora de la eficiencia de los mercados.

Imagen | Dominio Público, YouTube

En Xataka | El MIT ha descubierto un problema matemático imposible. Y está dentro de todos los juegos de Mario en 2D

En Xataka | Un antiguo problema de geometría ha inquietado a los matemáticos durante décadas. Por fin lo han resuelto