Lentidão na rede pode em breve ser coisa do passado, graças a um novo algoritmo super rápido.
O avanço oferece uma solução dramaticamente mais rápida para um problema que atormenta os cientistas da computação desde a década de 1950: fluxo máximo, ou como atingir o fluxo mais rápido de informações por meio de um sistema com capacidade limitada.
Os algoritmos de fluxo máximo anteriores fizeram avanços constantes e incrementais, mas ainda demoravam mais para encontrar o fluxo ideal do que para processar os dados da rede. Mas a nova pesquisa, apresentada em 11 de junho no Anais do 56º Simpósio Anual da ACM sobre Teoria da Computaçãodetalha um algoritmo que pode resolver o problema quase tão rápido quanto escrever os detalhes da rede.
O problema do fluxo máximo é uma pedra angular da ciência algorítmica e inspirou muitos dos avanços mais significativos no campo. A primeira tentativa de resolvê-lo ocorreu em 1956, quando os matemáticos Delbert Fulkerson e Lester Ford proposto o que eles chamaram de “solução gananciosa” para a questão.
Algoritmos gananciosos funcionam fazendo as escolhas mais imediatamente vantajosas em cada ponto da árvore de decisão, escolhendo o melhor caminho à sua frente, independentemente das rotas que isso pode bloquear no futuro.
Imagine o problema de otimizando o tráfego de A para B ao longo de vários caminhos possíveis, uma rota sendo composta de um primeiro segmento que é uma rodovia de seis faixas e o final uma estrada de três faixas. Para resolver isso, o algoritmo ganancioso lançará o máximo de tráfego possível (três faixas de carros) ao longo da rota, ajustando sua capacidade e repetindo os mesmos passos para outras rotas até que cada caminho possível esteja em capacidade máxima.
O algoritmo de Fulkerson e Ford provou ser eficaz o suficiente, mas muitas vezes não produzia o melhor fluxo possível: se outras rotas fossem cortadas e congestionamentos abaixo do ideal surgissem, que assim fosse. Os 70 anos subsequentes de contribuições ao problema tentaram refinar esse aspecto da solução, suavizando lentidões desnecessárias ao construir uma melhor tomada de decisão no algoritmo.
Esses ajustes mudaram o tempo de execução do algoritmo de um múltiplo de m^2 (onde m é o número de nós na rede) para um múltiplo de m^1,33 em 2004, mas depois o progresso estagnou.
Para chegar a essa descoberta, os pesquisadores do estudo combinaram duas abordagens anteriores: a solução original que tratava as redes como tráfego; e uma posterior que, em vez disso, as via como uma rede elétrica. Ao contrário de carros ou trens, o fluxo de elétrons pode ser parcialmente desviado para se juntar à corrente ao longo de outra rota, permitindo que os cientistas da computação mapeiem o melhor fluxo em toda a rede antes que a abordagem de tráfego segmento por segmento seja aplicada.
A combinação dessas duas abordagens resultou em um algoritmo híbrido que era “absurdamente rápido”. Daniel A. Spielmanprofessor de matemática aplicada e ciência da computação na Universidade de Yale que supervisionou o programa de doutorado de um dos pesquisadores, disse em uma declaração. Spielman comparou a nova solução às anteriores como sendo como “um Porsche ultrapassando carruagens puxadas por cavalos”.
Uma vez refinado, o novo algoritmo poderia ser potencialmente aplicado a uma série de aplicações, incluindo dados da internet, programação de companhias aéreas e melhoria da eficiência dos mercados, disseram os pesquisadores.
