Na década de 1950, os cientistas da computação perceberam algo. À medida que a sociedade avançava e se tornava maior e mais densa, junto com suas redes de transporte, as lentidões, aglomerações e congestionamentos de tráfego se tornavam mais evidentes. Desde então, não têm cessado as ideias e propostas em busca de resolver o problema dos engarrafamentos e de seus fluxos mais eficientes — a solução estava em um algoritmo “absurdamente rápido”.
O anúncio
Em junho de 2024, uma equipe de pesquisadores do ETH (Instituto Federal de Tecnologia) de Zurique apresentou no Simpósio Anual da ACM sobre Teoria da Computação o que, em teoria, é o algoritmo de fluxo de rede mais rápido possível. O trabalho pioneiro da equipe liderada pelo pesquisador Rasmus Kyng aborda a questão de como alcançar o fluxo máximo em uma rede e, ao mesmo tempo, minimizar os custos de transporte.
Um exemplo antes de explicar com mais detalhes. Imagine que você está utilizando uma rede de transporte europeia buscando a rota mais rápida e barata para transportar a maior quantidade possível de mercadorias de Madrid a Londres. O algoritmo de Kyng pode ser aplicado nesses casos para calcular o fluxo de tráfego ótimo e de menor custo para qualquer tipo de rede, seja ferroviária, rodoviária, fluvial ou da internet. E ele faz isso tão rapidamente que assusta: pode fornecer a solução no mesmo momento em que um computador lê os dados que descrevem a rede.
Contexto
Como mencionamos no início, o feito da equipe de Kyng é histórico. Ele oferece uma solução sem igual para um problema que atormenta os pesquisadores há 70 anos: o fluxo máximo, ou seja, como executar o fluxo mais rápido de informação através de um sistema com capacidade limitada.
História de um problema não resolvido
O problema do fluxo máximo foi formalizado na década de 1950 por Lester R. Ford e Delbert Fulkerson, que introduziram um famoso algoritmo conhecido como algoritmo Ford-Fulkerson para resolvê-lo. O problema surgiu no contexto do planejamento de infraestruturas, como redes de transporte, abastecimento de água e telecomunicações. Nele, há uma rede direcionada onde cada aresta tem uma capacidade que indica a quantidade máxima de fluxo que pode passar por ela.
A proposta Ford-Fulkerson foi um dos primeiros métodos sugeridos para resolver o quebra-cabeça através do que chamaram de "solução gananciosa". O algoritmo funciona buscando caminhos da origem ]até o destino onde o fluxo pode ser aumentado. Assim que um caminho com capacidade disponível é encontrado, o fluxo nessa rota é aumentado e o processo é repetido até que não seja mais possível encontrar um caminho disponível.
O exemplo
Para entender, nada melhor do que a questão que foi proposta. Imagine o problema de otimizar o tráfego que se desloca de A a B ao longo de várias rotas possíveis, sendo uma rota formada por um primeiro segmento que é uma rodovia de seis faixas e o último uma estrada de três faixas. Para resolvê-lo, o algoritmo ganancioso lança tanto tráfego quanto possível (três faixas de automóveis) ao longo da rota, ajustando sua capacidade e repetindo os mesmos passos para outras rotas até que todas as rotas possíveis estejam com capacidade total.
E sim, a verdade é que a proposta dos pesquisadores era eficaz, mas tinha um problema: muitas vezes, não produzia o melhor fluxo possível. Se outras rotas eram cortadas e surgiam congestionamentos não otimizados, o algoritmo decidia deixar a situação como estava. Ao longo de 70 anos, houve contribuições para o problema tentando refinar esse aspecto da solução, suavizando as lentidões desnecessárias por meio da incorporação de uma melhor tomada de decisões no algoritmo.
Por exemplo, o algoritmo foi aperfeiçoado posteriormente com implementações mais eficientes, como o algoritmo de Edmonds-Karp, que usa uma busca em largura para encontrar o caminho aumentante mais curto. Esse e outros ajustes mudaram o tempo de execução do algoritmo de um múltiplo de m² (onde m é o número de nós da rede) para um múltiplo de m¹,³³ em 2004. Mas, depois, o progresso estagnou.
O algoritmo "absurdamente rápido"
E chegamos ao revolucionário anúncio. Kyng e sua equipe combinaram as propostas anteriores: a solução original, que tratava as redes como tráfego, e uma posterior que, por outro lado, as considerava como uma rede elétrica. Diferentemente de automóveis ou trens, o fluxo de elétrons pode ser desviado parcialmente para se unir à corrente ao longo de outra rota, permitindo que os cientistas da computação tracem o melhor fluxo através de toda a rede antes de aplicar a abordagem do tráfego segmento por segmento.
Essa combinação resultou em algo semelhante a um algoritmo híbrido, "absurdamente rápido", segundo a declaração de Daniel A. Spielman, professor de matemática aplicada e ciências da computação na Universidade de Yale, que supervisionou o programa de doutorado de um dos pesquisadores. Spielman comparou a nova solução com as anteriores, dizendo que era "como um Porsche que ultrapassa carruagens puxadas por cavalos".
Uma comparação acertada e um avanço que promete revolucionar muitos campos, como os dados da internet, as rotas de tráfego e transporte, a programação de voos na rede e até mesmo a melhoria da eficiência dos mercados.
Texto traduzido e adaptado dos site Xataka Espanha
Imagem | Public Domain, YouTube
Ver 0 Comentários