Pesquisadores da ETH Zurich desenvolvem o algoritmo de fluxo mais rápido possível
Rasmus Kyng escreveu o algoritmo quase perfeito. Calcula o fluxo máximo de transporte a um custo mínimo para qualquer tipo de rede – seja ferroviária, rodoviária ou eléctrica – a uma velocidade que é, matematicamente falando, impossível de ser superada.
Numa descoberta que traz à mente Lucky Luke – o homem que dispara mais rápido do que a sua sombra – Rasmus Kyng e a sua equipa desenvolveram um algoritmo super-rápido que parece destinado a transformar todo um campo de investigação. O trabalho inovador da equipe de Kyng envolve o que é conhecido como algoritmo de fluxo de rede, que aborda a questão de como atingir o fluxo máximo em uma rede e, ao mesmo tempo, minimizar os custos de transporte.
Imagine que você está usando a rede de transporte europeia e procurando a rota mais rápida e barata para mover o máximo de mercadorias possível de Copenhague para Milão. O algoritmo de Kyng pode ser aplicado em tais casos para calcular o fluxo de tráfego ideal e de menor custo para qualquer tipo de rede – seja ferroviária, rodoviária, aquática ou a internet. Seu algoritmo realiza esses cálculos tão rápido que pode entregar a solução no exato momento em que um computador lê os dados que descrevem a rede.
Computações tão rápidas quanto uma rede são grandes
Antes de Kyng, ninguém jamais havia conseguido fazer isso – embora os pesquisadores tenham trabalhado nesse problema por cerca de 90 anos. Anteriormente, demorava significativamente mais para calcular o fluxo ótimo do que para processar os dados da rede. E conforme a rede se tornava maior e mais complexa, o tempo de computação necessário aumentava muito mais rápido, comparativamente falando, do que o tamanho real do problema de computação. É por isso que também vemos problemas de fluxo em redes que são grandes demais para um computador sequer calcular.
A abordagem de Kyng elimina esse problema: usando seu algoritmo, o tempo de computação e o tamanho da rede aumentam na mesma proporção – um pouco como fazer uma caminhada e manter constantemente o mesmo ritmo, por mais íngreme que seja o caminho. Uma olhada nos números brutos mostra até onde chegamos: até a virada do milênio, nenhum algoritmo conseguiu calcular mais rápido do que eu1.5onde eu representa o número de conexões em uma rede que o computador precisa calcular, e apenas ler os dados da rede uma vez leva eu tempo. Em 2004, a velocidade de computação necessária para resolver o problema foi reduzida com sucesso para eu1,33. Usando o algoritmo de Kyng, o tempo de computação “adicional” necessário para chegar à solução após a leitura dos dados da rede agora é insignificante.
Como um Porsche correndo em uma carruagem puxada por cavalos
Os pesquisadores desenvolveram assim o que é, em teoria, o algoritmo de fluxo de rede mais rápido possível. Há dois anos, Kyng e sua equipe apresentaram provas matemáticas de seu conceito em um artigo inovador. Os cientistas referem-se a esses novos algoritmos, quase idealmente rápidos, como “algoritmos de tempo quase linear”, e a comunidade de cientistas da computação teóricos respondeu à descoberta de Kyng com uma mistura de espanto e entusiasmo.
O supervisor de doutorado de Kyng, Daniel A. Spielman, Professor de Matemática Aplicada e Ciência da Computação em Yale e ele próprio um pioneiro e decano neste campo, comparou o algoritmo “absurdamente rápido” a um Porsche ultrapassando carruagens puxadas por cavalos. Além de ganhar o prêmio de Melhor Artigo de 2022 no Simpósio Anual do IEEE sobre Fundamentos da Ciência da Computação (FOCS), seu artigo também foi destacado no periódico de computação e pelos editores da revista científica popular Quanta classificou o algoritmo de Kyng como uma das dez maiores descobertas da ciência da computação em 2022.
Desde então, os pesquisadores refinaram sua abordagem e desenvolveram algoritmos de tempo quase linear. Por exemplo, o primeiro algoritmo ainda estava focado em redes fixas e estáticas cujas conexões são direcionadas, o que significa que funcionam como ruas de mão única em redes viárias urbanas. Os algoritmos publicados este ano também são capazes de calcular fluxos ideais para redes que mudam gradativamente ao longo do tempo. A computação extremamente rápida é um passo importante para lidar com redes altamente complexas e ricas em dados que mudam de forma dinâmica e muito rápida, como as moléculas ou o cérebro na biologia, ou as amizades humanas.
Algoritmos ultrarrápidos para redes em mudança
Na quinta-feira, Simon Meierhans – um membro da equipe de Kyng – apresentou um novo algoritmo de tempo quase linear no Simpósio Anual da ACM sobre Teoria da Computação (STOC) em Vancouver. Este algoritmo resolve o problema de fluxo máximo de custo mínimo para redes que mudam incrementalmente conforme novas conexões são adicionadas. Além disso, em um segundo artigo aceito pelo Simpósio IEEE sobre Fundamentos da Ciência da Computação (FOCS) em outubro, os pesquisadores desenvolveram outro algoritmo que também lida com conexões sendo removidas.
Especificamente, esses algoritmos identificam as rotas mais curtas em redes onde conexões são adicionadas ou excluídas. Em redes de tráfego do mundo real, exemplos dessas mudanças na Suíça incluem o fechamento completo e a reabertura parcial do Gotthard Base Tunnel nos meses desde o verão de 2023, ou o recente deslizamento de terra que destruiu parte da rodovia A13, que é a principal rota alternativa ao Gotthard Road Tunnel.
Confrontados com tais mudanças, como um computador, um serviço de mapa online ou um planejador de rotas calcula a conexão mais rápida e de menor custo entre Milão e Copenhague? Os novos algoritmos de Kyng também calculam a rota ideal para essas redes que mudam incremental ou decrementalmente em tempo quase linear – tão rapidamente que o tempo de computação para cada nova conexão, seja adicionada por meio de redirecionamento ou criação de novas rotas, é novamente insignificante.
Mas o que exatamente torna a abordagem de Kyng aos cálculos muito mais rápida do que qualquer outro algoritmo de fluxo de rede? Em princípio, todos os métodos computacionais enfrentam o desafio de ter que analisar a rede em múltiplas iterações para encontrar o fluxo ideal e a rota de custo mínimo. Ao fazê-lo, percorrem cada uma das diferentes variantes cujas ligações estão abertas, fechadas ou congestionadas porque atingiram o seu limite de capacidade.
Calcular o todo? Ou suas partes?
Antes de Kyng, os cientistas da computação tendiam a escolher entre duas estratégias principais para resolver esse problema. Um deles foi modelado na rede ferroviária e envolveu o cálculo de uma seção inteira da rede com um fluxo de tráfego modificado em cada iteração. A segunda estratégia – inspirada nos fluxos de energia na rede elétrica – calculou toda a rede em cada iteração, mas utilizou valores médios estatísticos para o fluxo modificado de cada seção da rede, a fim de tornar o cálculo mais rápido.
“Nossa abordagem é baseada em muitas etapas computacionais pequenas, eficientes e de baixo custo que, juntas, são muito mais rápidas do que algumas poucas etapas grandes.”
A equipe de Kyng uniu agora as respectivas vantagens dessas duas estratégias para criar uma abordagem combinada nova e radical. “Nossa abordagem é baseada em muitas etapas computacionais pequenas, eficientes e de baixo custo, que – tomadas em conjunto – são muito mais rápidas do que algumas etapas grandes”, diz Maximilian Probst Gutenberg, palestrante e membro do grupo de Kyng, que desempenhou um papel fundamental no desenvolvimento de algoritmos de tempo quase linear.
Uma breve olhada na história desta disciplina acrescenta uma dimensão adicional à significância da descoberta de Kyng: problemas de fluxo em redes estavam entre os primeiros a serem resolvidos sistematicamente com a ajuda de algoritmos na década de 1950, e algoritmos de fluxo desempenharam um papel importante no estabelecimento da ciência da computação teórica como um campo de pesquisa por direito próprio. O conhecido algoritmo desenvolvido pelos matemáticos Lester R. Ford Jr. e Delbert R. Fulkerson também deriva deste período. Seu algoritmo resolve eficientemente o problema de fluxo máximo, que busca determinar como transportar o máximo de mercadorias possível através de uma rede sem exceder a capacidade das rotas individuais.
Rápido e abrangente
Esses avanços mostraram aos pesquisadores que o problema do fluxo máximo, o problema do custo mínimo (problema de transbordo ou transporte) e muitos outros problemas importantes de fluxo de rede podem ser vistos como casos especiais do problema geral de fluxo de custo mínimo. Antes da pesquisa de Kyng, a maioria dos algoritmos só conseguia resolver um desses problemas de forma eficiente, embora não pudessem fazer isso de maneira particularmente rápida, nem pudessem ser estendidos ao problema mais amplo do fluxo de custo mínimo. O mesmo se aplica aos algoritmos de fluxo pioneiros da década de 1970, pelos quais os teóricos cientistas da computação John Edward Hopcroft, Richard Manning Karp e Robert Endre Tarjan receberam cada um o Prêmio Turing, considerado o “Prêmio Nobel” da ciência da computação. Karp recebeu o seu em 1985; Hopcroft e Tarjan ganharam o deles em 1986.
Mudança de perspectiva das ferrovias para a eletricidade
Foi somente em 2004 que os matemáticos e cientistas da computação Daniel Spielman e Shang-Hua Teng – e mais tarde Samuel Daitch – conseguiram escrever algoritmos que também forneceram uma solução rápida e eficiente para o problema do fluxo de custo mínimo. Foi esse grupo que mudou o foco para os fluxos de energia na rede elétrica. Sua mudança de perspectiva das ferrovias para a eletricidade levou a uma distinção matemática fundamental: se um trem é redirecionado na rede ferroviária porque uma linha está fora de serviço, a próxima melhor rota de acordo com o horário pode já estar ocupada por um trem diferente. Na rede elétrica, é possível que os elétrons que compõem um fluxo de energia sejam parcialmente desviados para uma conexão de rede pela qual outra corrente já esteja fluindo. Assim, diferentemente dos trens, a corrente elétrica pode, em termos matemáticos, ser “parcialmente” movida para uma nova conexão.
“Rejeitamos a abordagem de criar os algoritmos mais poderosos que podíamos para toda a rede.”
Este reencaminhamento parcial permitiu que Spielman e os seus colegas calculassem essas alterações de rota com muito mais rapidez e, ao mesmo tempo, recalculassem toda a rede após cada alteração. “Rejeitamos a abordagem de Spielman de criar os algoritmos mais poderosos possíveis para toda a rede”, diz Kyng. “Em vez disso, aplicamos sua ideia de cálculo de rota parcial às abordagens anteriores de Hopcroft e Karp.” Este cálculo de rotas parciais em cada iteração desempenhou um papel importante na aceleração do cálculo geral do fluxo.
Um ponto de viragem nos princípios teóricos
Grande parte do progresso dos pesquisadores se resume à decisão de estender seu trabalho além do desenvolvimento de novos algoritmos. A equipe também usa e projeta novas ferramentas matemáticas que aceleram seus algoritmos ainda mais. Em particular, eles desenvolveram uma nova estrutura de dados para organizar dados de rede; isso torna possível identificar qualquer alteração em uma conexão de rede extremamente rápido; isso, por sua vez, ajuda a tornar a solução algorítmica tão incrivelmente rápida. Com tantas aplicações alinhadas para os algoritmos de tempo quase linear e para ferramentas como a nova estrutura de dados, a espiral geral de inovação pode em breve girar muito mais rápido do que antes.
No entanto, estabelecer as bases para resolver problemas muito grandes que não podiam ser computados eficientemente antes é apenas um dos benefícios desses algoritmos de fluxo significativamente mais rápidos – porque eles também mudam a maneira como os computadores calculam tarefas complexas em primeiro lugar. “Na última década, houve uma revolução nas bases teóricas para obter algoritmos comprovadamente rápidos para problemas fundamentais na ciência da computação teórica”, escreve um grupo internacional de pesquisadores da Universidade da Califórnia, Berkeley, que inclui entre seus membros Rasmus Kyng e Deeksha Adil, pesquisadora do Instituto de Estudos Teóricos da ETH Zurich.
Referências
van den Brand, J, Chen, L, Kyng, R, Liu, YP, Meierhans, S, Probst Gutenberg, M, Sachdeva, S. Algoritmos de tempo quase lineares para gráficos decrementais: fluxo de custo mínimo e mais via dualidade. 65º Simpósio IEEE sobre Fundamentos da Ciência da Computação (FOCS) 2024. https://focs.computer.org/2024/accepted-papers-for-focs-2024/
Chen, L, Kyng, R, Liu, YP, Meierhans, S, Probst Gutenberg, M. Algoritmos de tempo quase lineares para gráficos incrementais: detecção de ciclo, SCCs, st Shortest Path e fluxo de custo mínimo. Anais do 56º Simpósio Anual da ACM sobre Teoria da Computação, junho de 2024 (STOC 2024). doi: https://doi.org/10.1145/3618260.3649745 .
Chen, L, Kyng, R, Liu, YP, Peng, R, Probst Gutenberg, M, Sachdeva, S, Kyng, R. Fluxo Máximo e Fluxo de Custo Mínimo em Tempo Quase Linear. 2022 IEEE 63º Simpósio Anual sobre Fundamentos da Ciência da Computação (FOCS), Denver, CO, EUA, 2022. doi: 10.1109/FOCS54457.2022.00064 .
Floriano Meyer
