Pesquisadores da ETH Zurich desenvolvem o algoritmo de fluxo mais rápido

 (ethz.ch)
1 pontos por GN⁺ 2024-06-30 | 1 comentários | Compartilhar no WhatsApp
  • A equipe de pesquisa de Rasmus Kyng, da ETH Zurich, desenvolveu um algoritmo que calcula, quase no limite matemático de velocidade, o problema de encontrar o fluxo máximo em uma rede e minimizar os custos de transporte
  • O novo algoritmo é uma abordagem de tempo quase linear, que entrega a resposta em uma escala quase igual ao tempo necessário para ler os dados da rede, e pode ser aplicado a cálculos de redes como ferrovias, estradas, hidrovias e internet
  • No passado, considerando m como o número de conexões, antes de 2000 não havia algoritmos melhores que m^1.5 e, em 2004, chegou-se ao nível de m^1.33; a abordagem de Kyng reduz o tempo adicional de computação após a leitura dos dados a um nível desprezível
  • A equipe também calcula caminhos mais curtos e fluxo máximo de custo mínimo em tempo quase linear em grafos incrementais, nos quais conexões são adicionadas, e em grafos decrementais, nos quais conexões são removidas, indo além de redes estáticas e direcionadas
  • Isso serve de base para recalcular rapidamente rotas ideais em situações em que redes reais mudam, como o fechamento e a reabertura parcial do Gotthard Base Tunnel e o deslizamento de terra na rodovia A13

Cálculo de problemas de fluxo em redes quase no limite de velocidade

  • O algoritmo de fluxo em redes da equipe de Rasmus Kyng trata do problema de encontrar o maior fluxo possível em uma rede enquanto minimiza os custos de transporte
  • Um exemplo típico é a situação de encontrar uma rota para transportar o máximo possível de mercadorias de Copenhagen a Milan da forma mais rápida e barata
  • É possível calcular o fluxo ideal de baixo custo em redes com conexões e capacidades, como ferrovias, estradas, hidrovias e a internet
  • A velocidade de cálculo foi reduzida a um nível quase igual ao tempo que o computador leva para ler os dados da rede

Por que é o algoritmo “mais rápido”

  • Antes, o tempo para calcular o fluxo ideal era muito maior do que o tempo para processar os dados da rede
  • À medida que a rede ficava maior e mais complexa, o tempo de computação necessário crescia mais rápido do que o tamanho do problema
  • A abordagem de Kyng faz com que o tempo de computação e o tamanho da rede aumentem na mesma proporção
    • Se o número de conexões da rede é m, só ler os dados uma vez já leva tempo m
    • Antes de 2000, não havia algoritmos que calculassem mais rápido que m^1.5
    • Em 2004, a quantidade de computação necessária para resolver o problema caiu para m^1.33
    • O algoritmo de Kyng reduz a um nível desprezível o tempo adicional de computação necessário para chegar à solução depois de ler os dados

Avaliação e expansão dos algoritmos de tempo quase linear

  • Há dois anos, a equipe de Kyng publicou um artigo com a prova matemática desse conceito
  • Algoritmos quase otimamente rápidos como esse são chamados de algoritmos de tempo quase linear
  • Daniel A. Spielman comparou esse algoritmo a um Porsche ultrapassando uma carruagem
  • O artigo recebeu o Best Paper Award no IEEE Annual Symposium on Foundations of Computer Science, FOCS, de 2022
  • A Communications of the ACM também destacou a pesquisa, e os editores da Quanta selecionaram o algoritmo de Kyng como uma das 10 maiores descobertas da ciência da computação em 2022

De redes estáticas a redes em mudança

  • O algoritmo inicial tinha foco em redes fixas e estáticas com direções de conexão definidas
    • Conexões direcionadas têm uma estrutura semelhante a ruas de mão única em uma malha urbana
  • Depois, a equipe desenvolveu algoritmos que também calculam o fluxo ideal em redes que mudam gradualmente ao longo do tempo
  • Simon Meierhans apresentou um novo algoritmo de tempo quase linear no Annual ACM Symposium on Theory of Computing, STOC, em Vancouver
    • Esse algoritmo resolve o problema de fluxo máximo de custo mínimo em redes às quais novas conexões são adicionadas
  • Em um segundo artigo aceito no IEEE Symposium on Foundations of Computer Science, FOCS, de outubro, a equipe desenvolveu um algoritmo que também lida com a remoção de conexões
  • Os dois algoritmos identificam caminhos mais curtos em redes nas quais conexões são adicionadas ou removidas

Exemplos de mudanças em redes reais

  • O Gotthard Base Tunnel, na Switzerland, ficou totalmente fechado desde o verão de 2023 e depois foi reaberto parcialmente
  • Parte da rodovia A13, uma importante rota alternativa ao Gotthard Road Tunnel, foi destruída recentemente por um deslizamento de terra
  • Quando mudanças desse tipo ocorrem, computadores, serviços de mapas online e planejadores de rotas precisam recalcular a conexão de menor custo e mais curta entre Milan e Copenhagen
  • O novo algoritmo de Kyng calcula rotas ideais em tempo quase linear mesmo em redes com adição ou remoção de conexões
  • Mesmo quando conexões são adicionadas por desvios ou novas rotas, o tempo adicional de computação é desprezível

Duas estratégias anteriores e a nova forma de combiná-las

  • O cálculo de fluxo em redes precisa analisar a rede várias vezes para encontrar o fluxo ideal e as rotas de custo mínimo
  • Em cada iteração, são examinadas variações como quais conexões estão abertas ou fechadas e quais estão congestionadas por terem atingido o limite de capacidade
  • Antes de Kyng, cientistas da computação usavam principalmente uma de duas estratégias
    • Modelo de rede ferroviária: em cada iteração, calcula-se todo um trecho da rede cujo fluxo de tráfego mudou
    • Modelo de rede elétrica: em cada iteração, calcula-se a rede inteira, mas usam-se valores médios estatísticos para o fluxo alterado em cada trecho, acelerando o cálculo
  • A equipe de Kyng combinou as vantagens das duas estratégias em uma nova abordagem híbrida
  • Maximilian Probst Gutenberg considera que combinar muitas etapas de cálculo pequenas, eficientes e de baixo custo é muito mais rápido do que usar poucas etapas grandes

Contexto histórico dos algoritmos de fluxo

  • O problema de fluxo em redes foi um dos primeiros problemas a serem resolvidos sistematicamente por algoritmos nos anos 1950
  • Algoritmos de fluxo tiveram papel importante para que a ciência da computação teórica se estabelecesse como um campo de pesquisa independente
  • O conhecido algoritmo de Lester R. Ford Jr. e Delbert R. Fulkerson também surgiu nesse período
  • O algoritmo Ford-Fulkerson resolve de forma eficiente o problema de fluxo máximo, transportando a maior quantidade possível de mercadorias pela rede sem exceder a capacidade de cada caminho
  • Pesquisas posteriores mostraram que o problema de fluxo máximo, o problema de custo mínimo e vários problemas de fluxo em redes são casos especiais do problema de fluxo de custo mínimo geral

Limitações dos algoritmos anteriores e a virada de 2004

  • Muitos algoritmos anteriores à pesquisa de Kyng conseguiam resolver um problema específico de forma eficiente, mas não eram rápidos o bastante e eram difíceis de estender ao problema mais amplo de fluxo de custo mínimo
  • John Edward Hopcroft, Richard Manning Karp e Robert Endre Tarjan, que criaram algoritmos de fluxo pioneiros nos anos 1970, receberam o Turing Award
    • Karp recebeu o prêmio em 1985
    • Hopcroft e Tarjan receberam em 1986
  • Em 2004, Daniel Spielman, Shang-Hua Teng e, posteriormente, Samuel Daitch criaram algoritmos que também ofereciam soluções rápidas e eficientes para o problema de fluxo de custo mínimo
  • Esse grupo mudou a perspectiva das ferrovias para o fluxo de eletricidade em redes elétricas
  • Em redes elétricas, é possível desviar parcialmente o fluxo de corrente para conexões pelas quais já passam outras correntes
  • Kyng não seguiu diretamente a poderosa abordagem algorítmica de Spielman para a rede inteira; em vez disso, aplicou a ideia de cálculo de caminhos parciais à abordagem anterior de Hopcroft e Karp
  • O cálculo de caminhos parciais em cada iteração teve papel importante em acelerar o cálculo do fluxo total

Novas ferramentas matemáticas e estruturas de dados

  • O avanço da equipe da ETH Zurich se baseia não só em novos algoritmos, mas também no projeto de ferramentas matemáticas que tornam os cálculos mais rápidos
  • A equipe desenvolveu uma nova estrutura de dados para organizar os dados da rede
  • Essa estrutura de dados permite identificar mudanças nas conexões da rede com muita rapidez
  • A identificação rápida de mudanças funciona como um fator que acelera a solução algorítmica
  • Os algoritmos de tempo quase linear e a nova estrutura de dados estabelecem uma base para resolver problemas muito grandes que antes não podiam ser calculados de forma eficiente

Artigos e materiais relacionados

Leituras relacionadas

1 comentários

 
GN⁺ 2024-06-30
Opiniões no Hacker News

  • Este algoritmo é assintoticamente quase linear no limite n -> inf
    No fim do vídeo, eles dizem que qualquer implementação desse algoritmo dificilmente venceria os algoritmos existentes no mundo real
    https://cacm.acm.org/research/almost-linear-time-algorithms-...

    • Então é mais um algoritmo galáctico?
      https://en.wikipedia.org/wiki/Galactic_algorithm
    • Depois de criar tanta expectativa no começo, isso é bem decepcionante
    • Fiquei muito cético assim que vi o título
      A expressão a velocidade mais rápida possível é uma afirmação realmente ousada
    • Outra pista nesses casos é que quase sempre é preciso uma solução absolutamente ótima
      Muitas vezes é muito mais prático gastar só 1% do tempo para obter 99% da qualidade

  • Curiosamente, a mesma pessoa também pesquisa como fazer algoritmos apenas teóricos funcionarem bem na prática [1]
    Só que esse processo também parece levar uns 20 anos. [1] foi construído sobre o avanço teórico de 2004 [2] e, pelo que entendi, esses algoritmos só começaram a funcionar na prática em 2024. Então talvez possamos esperar algoritmos práticos de fluxo de custo mínimo em 2044
    [1] https://arxiv.org/pdf/2303.00709
    [2] https://arxiv.org/abs/cs/0310051

  • Almost-Linear-Time Algorithm
    Ir de O(mn) para O(m) significa remover N, ou seja, o número de vértices, do cálculo. Não parece bom demais para ser verdade?

    • Os fatores constantes são tão grandes que, em entradas práticas, ele será mais lento que algoritmos existentes assintoticamente piores
      Ainda assim, é um resultado teoricamente elegante

  • Só de olhar os números brutos, dá para ver o quanto avançamos. Antes dos anos 2000, nenhum algoritmo conseguia calcular mais rápido que m1,5. Aqui, m significa o número de conexões de rede que o computador precisa calcular, e só ler os dados da rede uma vez já leva tempo m. Em 2004, a velocidade de cálculo necessária para resolver esse problema caiu para m1,33. Com o algoritmo de Kyng, o tempo de cálculo “extra” necessário para chegar à solução depois de ler os dados da rede agora é desprezível.
    O texto original não explicou o avanço de Kyng pela perspectiva da métrica m, que trata como tão importante; fico curioso sobre o motivo

  • Às vezes parece que se perdeu completamente o rumo ao usar complexidade como métrica
    Há cada vez mais algoritmos que otimizam a métrica de complexidade a níveis absurdos, mas que na prática não são úteis

    • Esse fenômeno existe há décadas
      Depois que os ganhos fáceis desapareceram, a pesquisa em algoritmos virou mais uma área altamente especializada, e a maioria dos artigos não vale muito o tempo gasto, a menos que você seja pesquisador de uma área muito próxima

  • Posts relacionados: https://news.ycombinator.com/item?id=31149038 (40 comentários)
    https://news.ycombinator.com/item?id=31675015 (72 comentários)

  • Onde estão o artigo ou o código?

  • Tem uma parte aqui que me confunde: o(n) parece uma proposição mais forte que O(n)
    Isso porque todo algoritmo o(n) é O(n), mas o inverso não é verdadeiro. Além disso, se o(n) se aplica até mesmo a n arbitrariamente pequeno, e O(n) só se aplica quando n -> inf, então este algoritmo não deveria ser aplicável também a n pequeno? Nesse caso, ele não deveria ser o oposto do algoritmo galáctico mencionado acima? Estou deixando passar alguma coisa?

    • A notação pequeno o também continua sendo uma afirmação assintótica, então não precisa se aplicar a n pequeno
      A definição de f(n) = o(g(n)) é, grosso modo, lim (n -> infinity) f(n)/g(n) = 0. Em outras palavras, para n suficientemente grande, g cresce mais rápido que f
      Por exemplo, uma função como f(n) = 10n if n < 1000 else 1e1000 é o(n). Isso porque, à medida que n cresce, 1e1000/n vai para 0. Essa é uma representação em pseudo-Python de uma função definida por partes que cresce exponencialmente até 101000 em n = 1000 e depois permanece constante
    • Se a complexidade de um algoritmo for 3↑↑64*n^0.999, ele é o(n), mas você pode chamá-lo tranquilamente de algoritmo galáctico

  • Se me lembro bem, 3↑↑64 é o número de Graham

  • Malditos fatores constantes, dá vontade de sacudir o punho para o céu

  • No resumo, só diz que o tempo é m^(1+o(1))
    Alguém sabe se há um limite superior mais concreto em algum lugar?

    • Aqui, o o é pequeno o, então captura um termo cujo “valor dividido por 1” vai para 0 quando m tende ao infinito
      https://de.m.wikipedia.org/wiki/Landau-Symbole
    • Significa que é possível escolher constantes para chegar tão perto de O(m) quanto se quiser
      Em outras palavras, é um esquema algorítmico que, para qualquer ɛ>1, produz um algoritmo que roda em tempo O(m^ɛ)
    • Esse já é o limite superior concreto
      Pequeno o é uma função que se aproxima de 0 quando n tende ao infinito, e é chamada de assintoticamente desprezível