Pesquisadores da ETH Zurique 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.
Em um avanço que traz à mente Lucky Luke – o homem que atira mais rápido que sua sombra – Rasmus Kyng e sua equipe desenvolveram um algoritmo super rápido que parece pronto para transformar todo um campo de pesquisa. 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 transportar 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 havia conseguido fazer isso – embora os pesquisadores trabalhem nesse problema há cerca de 90 anos. Anteriormente, demorava significativamente mais tempo para calcular o fluxo ideal do que para processar os dados da rede. E à medida que a rede se tornou maior e mais complexa, o tempo de computação necessário aumentou muito mais rapidamente, 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 serem calculadas por um computador.
A abordagem de Kyng elimina esse problema: usando seu algoritmo, o tempo de computação e o tamanho da rede aumentam na mesma taxa – um pouco como fazer uma caminhada e manter constantemente o mesmo ritmo, não importa o quão íngreme o caminho fique. Uma olhada nos números brutos mostra o quão longe chegamos: até a virada do milênio, nenhum algoritmo conseguiu computar mais rápido do que eu1,5onde eu representa o número de conexões em uma rede que o computador deve calcular, e apenas ler os dados da rede 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, portanto, o que é, em teoria, o algoritmo de fluxo de rede mais rápido possível. Dois anos atrás, Kyng e sua equipe apresentaram uma prova matemática de seu conceito em um artigo inovador. Cientistas se referem a esses algoritmos novos, quase otimamente rápidos, como “algoritmos de tempo quase linear”, e a comunidade de cientistas teóricos da computação 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, estes algoritmos identificam as rotas mais curtas nas redes onde as conexões são adicionadas ou excluídas. Nas redes de tráfego do mundo real, exemplos de tais mudanças na Suíça incluem o encerramento total e depois a reabertura parcial do Túnel Base de São Gotardo nos meses desde o verão de 2023, ou o recente deslizamento de terra que destruiu parte da autoestrada A13, que é a principal alternativa rota para o Túnel Rodoviário de São Gotardo.
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. Uma delas foi modelada na rede ferroviária e envolveu a computação 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 – calculava a rede inteira em cada iteração, mas usava valores médios estatísticos para o fluxo modificado de cada seção da rede para tornar a computação mais rápida.
“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.
Um breve olhar sobre a história desta disciplina acrescenta uma dimensão adicional à importância da descoberta de Kyng: os problemas de fluxo em redes estavam entre os primeiros a serem resolvidos sistematicamente com a ajuda de algoritmos na década de 1950, e os algoritmos de fluxo desempenharam um papel importante no estabelecimento 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 desse período. Seu algoritmo resolve com eficiência o problema de fluxo máximo, que busca determinar como transportar o maior número possível de mercadorias 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
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 este grupo que mudou o foco para os fluxos de energia na rede eléctrica. A sua mudança de perspectiva dos caminhos-de-ferro para a electricidade levou a uma distinção matemática fundamental: se um comboio for reencaminhado na rede ferroviária porque uma linha está fora de serviço, o próximo melhor itinerário de acordo com o horário pode já estar ocupado por um comboio diferente. Na rede elétrica, é possível que os elétrons que compõem um fluxo de potência sejam parcialmente desviados para uma conexão de rede por onde já circula outra corrente. Assim, diferentemente dos trens, a corrente elétrica pode, em termos matemáticos, ser deslocada “parcialmente” para uma nova ligação.
“Rejeitamos a abordagem de criar os algoritmos mais poderosos possíveis 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 o seu trabalho além do desenvolvimento de novos algoritmos. A equipe também utiliza e projeta novas ferramentas matemáticas que aceleram ainda mais seus algoritmos. Em particular, desenvolveram uma nova estrutura de dados para organizar os dados da rede; isso permite identificar qualquer alteração em uma conexão de rede com extrema rapidez; isso, por sua vez, ajuda a tornar a solução algorítmica 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 da inovação poderá em breve tornar-se muito mais rápida 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 linear para gráficos incrementais: detecção de ciclo, SCCs, st caminho mais curto e fluxo de custo mínimo. Anais do 56º Simpósio Anual 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
