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á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.

A equipe de Kyng agora uniu as respectivas vantagens dessas duas estratégias para criar uma nova abordagem combinada 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 poucas grandes”, diz Maximilian Probst Gutenberg, um palestrante e membro do grupo de Kyng, que desempenhou um papel fundamental no desenvolvimento dos 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 nem isso particularmente rápido, nem pudessem ser estendidos ao problema mais amplo de fluxo de custo mínimo. O mesmo se aplica aos algoritmos de fluxo pioneiros da década de 1970, pelos quais os cientistas teóricos da computação John Edward Hopcroft, Richard Manning Karp e Robert Endre Tarjan receberam cada um um 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.

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 da ETH Zurich 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 anteriormente não podiam ser calculados de forma eficiente é apenas um benefício destes algoritmos de fluxo significativamente mais rápidos – porque eles também mudam a forma como os computadores calculam tarefas complexas. “Na última década houve uma revolução nos fundamentos teóricos para a obtenção de 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 em Berkeley que inclui entre seus membros Rasmus Kyng e Deeksha Adil, pesquisadora do Instituto de Estudos Teóricos da ETH Zurique.