Los investigadores desarrollan el algoritmo de flujo más rápido posible.

Imagine que está utilizando la red de transporte europea y busca la forma más rápida y económica de transportar la mayor cantidad de mercancías posible de Copenhague a Milán. El algoritmo de Kyng se puede aplicar en tales casos para calcular el flujo de tráfico óptimo y de menor costo para cualquier tipo de red, ya sea ferroviaria, por carretera, marítima o Internet. Su algoritmo realiza estos cálculos tan rápido que puede proporcionar soluciones al mismo tiempo que la computadora lee los datos que describen la red.

La computación es tan rápida como grande es la red.

Antes de Kyng, nadie había logrado hacer eso, a pesar de que los investigadores han estado trabajando en el problema durante casi 90 años. Anteriormente, se necesitaba mucho más tiempo para calcular el flujo máximo que para procesar los datos de la red. Y a medida que la red se hacía más grande y más compleja, el tiempo de cálculo requerido crecía relativamente más rápido que el tamaño real del problema informático. Esta es la razón por la que también vemos problemas de flujo en redes que son demasiado grandes para que las computadoras puedan calcularlas.

El enfoque de Kang evita este problema: usando su algoritmo, el tiempo de computación y el tamaño de la red crecen al mismo ritmo, un poco como hacer una caminata y mantener continuamente el mismo ritmo sin importar cuán difícil sea el camino. Una mirada a los datos sin procesar muestra cuán lejos hemos llegado: hacia el cambio de milenio, ningún algoritmo había sido capaz de calcular más rápido. metro^1.5Dónde metro Significa la cantidad de conexiones en una red que la computadora tiene que calcular, y solo toma tiempo leer los datos de la red una vez. metro En 2004 se logró reducir con éxito la velocidad de cálculo necesaria para resolver el problema. metro^1.33. Utilizando el algoritmo de Kyng, el tiempo de cálculo “extra” necesario para llegar a una solución después de leer los datos de la red ahora es insignificante.

Un carruaje tirado por caballos como un Porsche

Investigadores de ETH Zurich han desarrollado lo que es, en teoría, el algoritmo de flujo de red más rápido jamás creado. Hace dos años, Kang y su equipo presentaron una prueba matemática de su concepto en un artículo histórico. Los científicos se refieren a estos algoritmos novedosos, casi óptimamente rápidos, como “algoritmos de tiempo aproximadamente lineal”, y la comunidad de científicos informáticos teóricos respondió al avance de Kang con una mezcla de sorpresa y entusiasmo.

El supervisor doctoral de Kang, Daniel A. Spielman, profesor de matemáticas aplicadas e informática en Yale y pionero y decano en este campo, comparó el algoritmo “increíblemente rápido” con un carruaje tirado por caballos que supera a un Porsche. Su artículo también apareció en Computing Journal y ganó el premio al mejor artículo de 2022 en el Simposio anual del IEEE sobre fundamentos de la informática (FOCS). Comunicaciones de la ACMy editores de revistas de divulgación científica. cuantos El algoritmo de Kang fue nombrado uno de los diez principales descubrimientos informáticos de 2022.

Desde entonces, los investigadores de ETH Zurich han perfeccionado su enfoque y han desarrollado algoritmos de tiempo más cercano al lineal. Por ejemplo, los primeros algoritmos todavía se centraban en redes fijas y estáticas cuyas conexiones eran directas, es decir, actuaban como calles de sentido único en las redes de calles urbanas. Los algoritmos publicados este año también pueden calcular flujos óptimos para redes que cambian incrementalmente con el tiempo. La computación ultrarrápida es un paso importante para lidiar con redes altamente complejas y ricas en datos que son dinámicas y cambian muy rápidamente, como moléculas o cerebros en organismos, o amistades humanas.

Algoritmos ultrarrápidos para cambiar de red

El jueves, Simon Meierhans, miembro del equipo de Kang, presentó un nuevo algoritmo de tiempo aproximadamente 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 gradualmente a medida que se agregan nuevas conexiones. Además, en otro 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 caídas.

En concreto, estos algoritmos identifican los caminos más cortos en las redes donde se agregan o eliminan conexiones. En las redes de tráfico del mundo real, ejemplos de tales cambios en Suiza incluyen el cierre completo y luego la reapertura parcial del túnel de base del San Gotardo en los meses posteriores al verano de 2023, o los recientes deslizamientos de tierra que destruyeron una parte de la autopista A13. es el reemplazo principal. 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 mejor ruta para estas redes cambiantes que crecen o se reducen en un tiempo casi lineal, tan rápido que el tiempo de cálculo para cada nueva conexión, incluso si se agrega mediante redireccionamiento o creación de nuevas rutas, es irreversible.

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 desafío de analizar la red en múltiples iteraciones para encontrar el flujo óptimo y la ruta de costo mínimo. Al hacerlo, pasan por cada uno de los distintos tipos cuyas conexiones están abiertas, cerradas o congestionadas al haber alcanzado su límite de capacidad.

¿Contar el total? ¿O partes de él?

Antes de Kyng, los informáticos eligieron una de dos estrategias principales para resolver este problema. Uno de ellos se desarrolló en una red ferroviaria e implicó calcular toda la sección de la red con el flujo de tráfico cambiado en cada iteración. Otra estrategia, influenciada por el flujo de energía en la red eléctrica, calculó toda la red en cada iteración, pero utilizó valores promedio estadísticos para los flujos modificados de cada parte de la red para hacer el cálculo más rápido.

El equipo de Kyng ha combinado ahora las respectivas ventajas de estas dos estrategias para crear un enfoque conjunto 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 pasos grandes”, dice Maximilian Probst Gutenberg, profesor y miembro del grupo de King, que interpretó un papel. papel clave en el desarrollo de un algoritmo de tiempo aproximadamente lineal.

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 con algoritmos en la década de 1950 y los algoritmos de flujo jugaron un papel importante en su establecimiento. La informática teórica como campo de investigación por derecho propio. De esta época también es originario el conocido algoritmo desarrollado por los matemáticos Lester R. Ford Jr. y Delbert R. Fulkerson. Su algoritmo resuelve eficazmente el problema del flujo óptimo, que intenta determinar cómo mover la cantidad máxima de mercancías a través de una red sin exceder la capacidad de las rutas individuales.

Rápido y amplio

Estos desarrollos mostraron a los investigadores que el problema del flujo máximo, el problema del costo mínimo (problema de transbordo o transporte) y muchos otros problemas importantes del flujo de la red pueden generalizarse al costo mínimo y pueden verse como casos especiales del problema del flujo. Antes de la investigación de Kyng, la mayoría de los algoritmos sólo podían resolver uno de estos problemas de manera eficiente, aunque no podían hacerlo particularmente rápido, ni tenían flujos extensos de costo mínimo que pudieran extenderse al problema de. Lo mismo se aplica a los primeros algoritmos de flujo de la década de 1970, por los que los informáticos teóricos John Edward Hopcroft, Richard Manning Karp y Robert Andre Turgeon recibieron cada uno el Premio Turing, conocido como el “Premio Nobel” de la informática. Corp adquirida en 1985. Hopcroft y Tarzán ganaron en 1986.

Un cambio de enfoque del ferrocarril a la electricidad

No fue hasta 2004 que los matemáticos e informáticos Daniel Spellman y Shang Hua Teng, y más tarde Samuel Dyche, pudieron escribir un algoritmo que también proporcionó una solución rápida y eficiente al problema del flujo de menor costo. Fue este grupo el que se centró en el flujo de electricidad en la red eléctrica. En su enfoque, la transición del ferrocarril a la electricidad condujo a una distinción matemática importante: si un tren en una red ferroviaria es desviado porque una línea está fuera de servicio, la siguiente mejor ruta según el horario puede ser ocupada por. un tren diferente. En una red eléctrica es posible que los electrones que crean un flujo de electricidad se desvíen parcialmente hacia conexiones de red por las que ya circulan otras corrientes. Así, a diferencia de los trenes, la corriente eléctrica se puede transferir matemáticamente “parcialmente” a una nueva conexión.

Este redireccionamiento parcial permitió a Spellman y sus colegas calcular dichos cambios de ruta muy rápidamente y, al mismo tiempo, recalcular toda la red después de cada cambio. “Rechazamos el enfoque de Spielman de construir el algoritmo más potente para toda la red”, afirma Kang. “En cambio, aplicamos su idea de cálculo de ruta parcial al enfoque inicial de Hopcroft y Karp”. Este cálculo de caminos parciales en cada iteración contribuyó a acelerar el cálculo del flujo general.

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

Gran parte del progreso de los investigadores de ETH Zurich proviene de la decisión de ampliar su trabajo más allá del desarrollo de nuevos algoritmos. El equipo también utiliza y diseña nuevas herramientas matemáticas que hacen que sus algoritmos sean aún más rápidos. En particular, desarrollaron una nueva estructura de datos para gestionar datos de red. Esto permite identificar muy rápidamente 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 para herramientas como algoritmos de tiempo casi lineal y nuevas estructuras de datos, la innovación general pronto podría ser más rápida que nunca.

Sin embargo, sentar las bases para resolver problemas muy grandes que antes no se podían calcular de manera eficiente es sólo una de las ventajas de estos algoritmos de flujo significativamente más rápidos, ya que también cambiarían la forma en que las computadoras calculan por primera vez tareas complejas. Un grupo internacional de investigadores de la Universidad de California, Berkeley, escribe: “Durante la última década, ha habido una revolución en los fundamentos teóricos para lograr algoritmos potencialmente rápidos para problemas fundamentales en la informática teórica. Entre sus miembros se incluyen Rasmus Kyng y otros. . Deeksha Adil, investigadora del Instituto de Estudios Teóricos de ETH Zurich.