En la década de 1950 los científicos se dieron cuenta de que, a medida que las redes de transporte crecían, las congestiones de tráfico se volvían más comunes. Desde entonces, han surgido muchas propuestas para resolver este problema, pero la solución estaba en un algoritmo "absurdamente rápido".

El anuncio. Un equipo de la ETH de Zúrich, liderado por Rasmus Kyng, presentó en el Simposio de ACM el algoritmo de flujo de red más rápido posible. Este algoritmo no solo maximiza el flujo en una red, sino que también minimiza los costos de transporte.

Un ejemplo antes de explicarlo más detallado. Imagina una red de transporte europea, buscando la ruta más rápida y barata para llevar mercancías de Madrid a Londres. El algoritmo de Kyng puede calcular el flujo más eficiente en cualquier red, ya sea ferroviaria, vial, fluvial o de Internet, y lo hace tan rápido que es capaz de encontrar la solución en cuanto el ordenador lee los datos de la red.

Contexto. El equipo de Kyng ha logrado lo que otros investigadores no pudieron en 70 años: resolver el problema del flujo máximo y cómo mover la información lo más rápido posible a través de redes limitadas en capacidad.

Historia de un problema no resuelto. El problema del flujo máximo fue formalizado por Lester R. Ford y Delbert Fulkerson en la década de 1950. Su algoritmo Ford-Fulkerson propuso una "solución codiciosa", donde se aumentaba el flujo disponible por rutas que conectaban de un punto a otro.

El ejemplo. Imagina optimizar el tráfico de A a B, usando una autopista de seis carriles que desemboca en una carretera de tres carriles. El algoritmo Ford-Fulkerson lanzaba tráfico hasta que agotaba la capacidad de la ruta, pero no siempre ofrecía el mejor flujo posible, permitiendo que surgieran cuellos de botella no óptimos.

Pequeñas mejoras. En los años posteriores, algoritmos como el Edmonds-Karp mejoraron el proceso, reduciendo el tiempo de ejecución, pero el progreso fue limitado.

El algoritmo "absurdamente rápido". La propuesta de Kyng combina enfoques anteriores, tratando la red como si fuera eléctrica, donde los electrones pueden desviarse para optimizar el flujo. Esto permite calcular la mejor ruta en toda la red antes de aplicarlo por segmentos, lo que hace que sea más eficiente. Daniel A. Spielman, de la Universidad de Yale, comparó esta innovación como "un Porsche adelantando carruajes tirados por caballos", lo que revolucionará campos como las rutas de tráfico, internet y la programación de vuelos.

Fuente: xataka.com