Pesquisadores desenvolvem algoritmo de fluxo mais rápido possível

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.

Cálculos tão rápidos 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 eu^1,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 eu^1,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 da ETH Zurique 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 Comunicações da ACMe os editores da popular revista científica Quanta nomeou o algoritmo de Kyng como uma das dez maiores descobertas da ciência da computação em 2022.

Desde então, os pesquisadores da ETH Zurique refinaram sua abordagem e desenvolveram novos 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 agora 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 no combate a 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 do ETH 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.

Confrontado com tais mudanças, como é que um computador, um serviço de mapas online ou um planeador de rotas calculam a ligação mais rápida e de menor custo entre Milão e Copenhaga? Os novos algoritmos de Kyng também calculam a rota ideal para essas redes que mudam de forma incremental ou decrescente em tempo quase linear – tão rapidamente que o tempo de computação para cada nova conexão, seja adicionado por meio de reencaminhamento ou criação de novas rotas, é novamente insignificante.

Mas o que exatamente torna a abordagem de Kyng para computações 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 ótimo e a rota de custo mínimo. Ao fazer isso, eles percorrem cada uma das diferentes variantes de quais conexões estão abertas, fechadas ou congestionadas porque atingiram 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á