Un algoritmo "absurdamente rápido" resuelve un atasco de 70 años: acelera el tráfico de red en áreas que van desde la programación de aerolíneas hasta Internet
Los investigadores han ideado un algoritmo "absurdamente rápido" para resolver el problema de encontrar el flujo más rápido a través de una red.
Cuando compra a través de enlaces en nuestro sitio, podemos ganar una comisión de afiliado. Así es como funciona.
Las ralentizaciones de la red pronto podrían ser cosa del pasado gracias a un nuevo algoritmo ultrarrápido.
El avance ofrece una solución dramáticamente más rápida a un problema que ha estado plagando a los científicos informáticos desde la década de 1950: 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.
Los algoritmos de flujo máximo anteriores lograron avances constantes e incrementales, pero todavía les llevó más tiempo encontrar el flujo óptimo que procesar los datos de la red. Pero la nueva investigación, presentada el 11 de junio en las Actas del 56º Simposio Anual ACM sobre Teoría de la Computación, detalla un algoritmo que puede resolver el problema aproximadamente tan rápido como se necesita para escribir los detalles del red caída.
El problema del flujo máximo es una piedra angular de la ciencia algorítmica y ha inspirado muchos de los avances más importantes en este campo. El primer intento de resolverlo se produjo en 1956, cuando los matemáticos Delbert Fulkerson y Lester Ford propusieron lo que llamaron una "solución codiciosa" a la cuestión.
Los algoritmos codiciosos funcionan tomando las decisiones más inmediatamente ventajosas en cada punto del árbol de decisión, eligiendo el mejor camino frente a él, independientemente de las rutas que esto pueda bloquear en el futuro.
Relacionado: La nueva computadora cuántica supera el récord de 'supremacía cuántica' en un factor de 100 y consume 30.000 veces menos energía
Imagine el problema de optimizar el tráfico que se mueve de A a B a lo largo de múltiples caminos posibles, una ruta formada por un primer segmento que es una autopista de seis carriles y el final por una carretera de tres carriles. Para solucionar esto, el algoritmo codicioso lanzará la mayor cantidad de tráfico posible (tres carriles de coches) a lo largo de la ruta, ajustando su capacidad y repitiendo los mismos pasos para otras rutas hasta que todos los caminos posibles estén a plena capacidad.
El algoritmo de Fulkerson y Ford demostró ser bastante eficaz, pero a menudo no produjo el mejor flujo posible: si se cortaban otras rutas y surgían atascos subóptimos, que así fuera. Los siguientes 70 años de contribuciones al problema intentaron refinar este aspecto de la solución, suavizando ralentizaciones innecesarias incorporando una mejor toma de decisiones en el algoritmo.
Estos ajustes cambiaron el tiempo de ejecución del algoritmo de un múltiplo m^2 (donde m es el número de nodos en la red) a un múltiplo de m^1,33 en 2004, pero luego el progreso se estancó.
Para llegar a su gran avance, los investigadores del estudio combinaron dos enfoques anteriores: la solución original que trataba las redes como tráfico; y uno posterior que los veía como una red eléctrica. A diferencia de los automóviles o los 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 en toda la red antes de aplicar el enfoque de tráfico segmento por segmento.
La combinación de estos dos enfoques dio como resultado un algoritmo híbrido que era "absurdamente rápido", dijo en un comunicado Daniel A. Spielman, profesor de matemáticas aplicadas e informática en la Universidad de Yale, quien supervisó el programa de doctorado de uno de los investigadores. Spielman comparó la nueva solución con las anteriores como si fuera "un Porsche que adelanta a un carruaje tirado por caballos".
Una vez perfeccionado, el nuevo algoritmo podría aplicarse potencialmente a una serie de aplicaciones, incluidos datos de Internet, programación de aerolíneas y mejora de la eficiencia de los mercados, dijeron los investigadores.