Los investigadores están desarrollando el algoritmo de flujo más rápido posible.

Imagínese utilizar la red de transporte europea y buscar la ruta más rápida y económica para mover la mayor cantidad de mercancías posible de Copenhague a Milán. En tales casos, el algoritmo de Kyng se puede utilizar para calcular el flujo de tráfico óptimo y de menor costo para cualquier tipo de red, ya sea ferroviaria, vial, marítima o Internet. Su algoritmo realiza estos cálculos con tanta rapidez que puede proporcionar una solución al mismo tiempo que la computadora lee los datos que describen la red.

Los cálculos son tan rápidos como la red.

Antes de Kyng, nadie lo había logrado, a pesar de que los investigadores han estado trabajando en el problema durante unos 90 años. Anteriormente, calcular el flujo óptimo llevaba mucho más tiempo que procesar datos de la red. Y a medida que la red se hizo más grande y más compleja, el tiempo computacional requerido creció relativamente mucho más rápido que el tamaño real del problema computacional. Así que también vemos problemas de flujo en redes que son demasiado grandes para que una computadora pueda siquiera calcularlas.

El enfoque de King evita este problema: con su algoritmo, el tiempo de cálculo y el tamaño de la red aumentan al mismo ritmo, similar a hacer una caminata y mantener un ritmo constante, sin importar cuán empinado sea el camino. Una mirada a los números brutos muestra hasta dónde hemos llegado: hasta el cambio de milenio, ningún algoritmo logró calcular más rápido que metro^1.5dónde metro representa el número de conexiones en la red que la computadora necesita para calcular y solo leer datos de la red metro tiempo. En 2004, la velocidad informática necesaria para resolver el problema se redujo con éxito a metro^1.33. Con el algoritmo de Kyng, el tiempo de cálculo «extra» necesario para llegar a la solución después de leer los datos de la red ahora es insignificante.

Como un Porsche conduciendo un carruaje tirado por caballos

Así, los investigadores de ETH Zurich han desarrollado lo que teóricamente es el algoritmo de flujo de red más rápido posible. Hace dos años, Kyng y su equipo presentaron la prueba matemática de su concepto en un artículo innovador. Los científicos llaman a estos nuevos algoritmos, casi óptimamente rápidos, «algoritmos de tiempo casi lineal», y la comunidad teórica de informática respondió al avance de Kyng con asombro y entusiasmo.

El supervisor de doctorado de Kyng, Daniel A. Spielman, profesor de matemáticas aplicadas e informática en Yale y pionero y admirador del campo, comparó el algoritmo «absurdamente rápido» con un Porsche adelantando a un carruaje tirado por caballos. Además de ganar el premio al mejor artículo de 2022 en el Simposio anual del IEEE sobre fundamentos de la informática (FOCS), su artículo también fue destacado en el Journal of Computing. Comunicaciones de la ACMy editores de revistas de divulgación científica cuantos nombró el algoritmo de King como uno de los diez mayores descubrimientos en informática en 2022.

Desde entonces, los investigadores de ETH Zurich han perfeccionado su enfoque y desarrollado nuevos algoritmos de tiempo cuasi lineales. Por ejemplo, el primer algoritmo todavía se centró en redes fijas y estáticas cuyas conexiones están dirigidas, lo que significa que actúan como calles de sentido único en las redes de carreteras urbanas. Los algoritmos publicados este año ahora también pueden calcular flujos óptimos para redes que cambian gradualmente con el tiempo. La computación ultrarrápida es un paso importante para abordar redes altamente complejas y ricas en datos que cambian dinámicamente y muy rápidamente, como las moléculas o los cerebros en biología o la amistad humana.

Algoritmos ultrarrápidos para cambiar de red

El jueves, Simon Meierhan, miembro del equipo de Kyng, presentó un nuevo algoritmo de tiempo cuasi lineal en el Simposio anual ACM sobre Teoría de la Computación (STOC) en Vancouver. Este algoritmo resuelve el problema de flujo máximo de costo mínimo para redes que cambian incrementalmente a medida que se agregan nuevas conexiones. Además, en un segundo artículo aceptado por el Simposio IEEE sobre Fundamentos de Ciencias de la Computación (FOCS) en octubre, los investigadores de ETH desarrollaron otro algoritmo que también maneja las conexiones que se eliminan.

En concreto, estos algoritmos identifican las rutas más cortas en las redes donde se añaden o eliminan conexiones. Ejemplos de tales cambios en las redes de tráfico del mundo real en Suiza incluyen el cierre completo y posterior reapertura parcial del túnel de base de San Gotardo en los meses posteriores al verano de 2023 o el reciente deslizamiento de tierra que destruyó parte de la autopista A13, la principal alternativa. ruta hacia el túnel de carretera del San Gotardo.

Ante tales cambios, ¿cómo puede un ordenador, un servicio de mapas en línea o un planificador de rutas calcular la conexión más barata y rápida entre Milán y Copenhague? Los nuevos algoritmos de Kyng también calculan la ruta óptima para estas redes incrementales o que cambian progresivamente en un tiempo casi lineal, tan rápido que el tiempo de cálculo para cada nueva conexión, ya sea agregada mediante redireccionamiento o creando nuevas rutas, es nuevamente insignificante.

Pero, ¿qué es exactamente lo que hace que el enfoque de cálculo de Kyng sea mucho más rápido que cualquier otro algoritmo de flujo de red? En principio, todos los métodos computacionales enfrentan el problema de analizar la red en varias iteraciones para encontrar el flujo óptimo y la ruta de mínimo costo. Al hacerlo, pasan por cada una de las distintas conexiones que están abiertas, cerradas o sobrecargadas porque han alcanzado su límite de capacidad.

¿Calcular todo? ¿O sus partes?

Antes de Kyng, los informáticos tendían a elegir una de dos estrategias principales para resolver este problema. Uno de ellos se modeló a partir de una red ferroviaria e implicó el cálculo de una parte completa de la red con un flujo de tráfico modificado en cada iteración. La segunda estrategia, inspirada en los flujos de energía en una red eléctrica, calculó la red completa en cada iteración, pero utilizó promedios estadísticos para el flujo modificado de cada sección de la red para agilizar los cálculos.

El equipo de Kyng ahora ha combinado las respectivas ventajas de estas dos estrategias para crear un enfoque combinado radicalmente nuevo. «Nuestro enfoque se basa en muchos pasos computacionales pequeños, eficientes y de bajo costo que en conjunto son mucho más rápidos que unos pocos grandes», dice Maximilian Probst Gutenberg, profesor y miembro del grupo Kyng que jugó un papel clave en el desarrollo del método casi lineal. -algoritmos de tiempo.

Una breve mirada a la historia de la disciplina añade una dimensión adicional a la importancia del avance de Kyng: los problemas de flujo en redes estuvieron entre los primeros en resolverse sistemáticamente utilizando algoritmos en la década de 1950, y los algoritmos de flujo jugaron un papel importante en la informática teórica como un campo de investigación independiente. De esta época también procede un conocido algoritmo desarrollado por los matemáticos Lester R. Ford Jr. y Delbert R. Fulkerson. Su algoritmo resuelve eficazmente el problema del flujo máximo, cuyo objetivo es determinar cómo transportar tantas mercancías como sea posible a través de la red sin exceder la capacidad de las rutas individuales.

Rápido y amplio

Estos avances mostraron a los investigadores que el problema de flujo máximo, el problema de costo mínimo (el problema de transbordo o transporte) y muchos otros problemas importantes de flujo de red pueden tratarse como casos especiales del problema general de flujo de costo mínimo. Antes del estudio de Kyng, la mayoría de los algoritmos sólo podían resolver eficientemente uno de estos problemas, aunque no podían hacerse muy rápidamente ni extenderse al problema más amplio del flujo de costo mínimo. Lo mismo se aplica a los innovadores algoritmos de flujo de la década de 1970, por los cuales los científicos informáticos teóricos John Edward Hopcroft, Richard Manning Karp y Robert Andre Tarjan recibieron cada uno el Premio Turing, considerado el «Premio Nobel» de la informática. Karp recibió el suyo en 1985; Hopcroft y Tarjan obtuvieron el suyo en 1986.

Cambiando la perspectiva del ferrocarril a la electricidad

No fue hasta 2004 que los matemáticos e informáticos Daniel Spielman y Shang-Hua Teng, y más tarde Samuel Daich, lograron escribir algoritmos que también proporcionaran una solución rápida y eficiente al problema del flujo de costo mínimo. Fue este grupo el que se centró en el flujo de electricidad en la red eléctrica. Su cambio del ferrocarril a la electricidad supuso una importante diferencia matemática: si se cambia un tren en la red ferroviaria porque una línea está fuera de servicio, es posible que la siguiente mejor ruta según el horario ya esté ocupada por otro tren. En una red eléctrica es posible que los electrones que componen el flujo de corriente se desvíen parcialmente a una conexión de red por la que ya circula otra corriente. Así, a diferencia de los trenes, la corriente eléctrica se puede trasladar matemáticamente «parcialmente» a una nueva conexión.

Este redireccionamiento parcial permitió a Spielman y sus colegas calcular dichos cambios de redireccionamiento mucho más rápido y al mismo tiempo recalcular toda la red después de cada cambio. «Rechazamos el enfoque de Spielman de construir los algoritmos más potentes que podamos para toda la red», afirma Kyng. «En cambio, aplicamos su idea de cálculo de ruta parcial a los enfoques anteriores de Hopcroft y Karp». Este cálculo de rutas parciales en cada iteración fue fundamental para acelerar el cálculo del flujo total.

Un punto de inflexión en los principios teóricos.

Gran parte del progreso de los investigadores de la ETH Zurich se debe a la decisión de ampliar su trabajo más allá del desarrollo de nuevos algoritmos. El equipo también está utilizando y desarrollando nuevas herramientas matemáticas que aceleran aún más sus algoritmos. En particular, han desarrollado una nueva estructura de datos para organizar los datos de la red; permite una detección extremadamente rápida de cualquier cambio en la conexión de red; esto, a su vez, ayuda a que la solución algorítmica sea increíblemente rápida. Con tantas aplicaciones creadas para algoritmos de tiempo casi lineal y herramientas como la nueva estructura de datos, la espiral general de innovación pronto podría girar mucho más rápido que antes.

Sin embargo, sentar las bases para resolver problemas muy grandes que antes no se podían calcular de manera eficiente es sólo uno de los beneficios de estos algoritmos de flujo significativamente más rápidos, ya que, en primer lugar, también cambian la forma en que las computadoras calculan tareas complejas. «Durante la última década, ha habido una revolución en los fundamentos teóricos de algoritmos demostrablemente rápidos para problemas fundamentales en informática teórica», escribe un equipo internacional de investigadores de la Universidad de California, Berkeley, entre cuyos miembros se encuentran Rasmus King y Deeksha Adil. , investigador del Instituto de Estudios Teóricos de ETH Zurich.