Dois cientistas da computação encontraram – nos lugares mais improváveis – exatamente a ideia de que precisavam para dar um grande salto na teoria dos grafos.
Em outubro passado, enquanto Jacob Holm e Eva Rotenberg folheavam um artigo que postaram alguns meses antes, eles perceberam que estavam sentados em algo grande.
Por décadas, os cientistas da computação têm tentado desenvolver um algoritmo rápido para determinar quando é possível adicionar arestas a um gráfico para que ele permaneça “plano”, o que significa que nenhuma de suas arestas se cruzam. Mas o campo não foi capaz de melhorar um algoritmo publicado há mais de 20 anos.
Holm e Rotenberg ficaram surpresos ao descobrir que seu artigo continha o insight necessário para fazer muito melhor. Isso “resolveu um dos maiores obstáculos que tínhamos para realmente conseguir um algoritmo real”, disse Holm, um cientista da computação da Universidade de Copenhagen. “Podemos ter dado a coisa toda.”
Os dois correram para redigir um novo artigo. Eles o apresentaram em junho no Simpósio ACM de Teoria da Computação, onde detalharam um método exponencialmente melhor para verificar se um gráfico é plano.
“O novo algoritmo é um notável tour de force”, disse Giuseppe Italiano, um cientista da computação da Universidade Luiss e co-autor do artigo de 1996 que descreve o que agora é o segundo algoritmo mais rápido. “Quando fui coautor desse artigo, não pensei que isso pudesse acontecer.”
Os gráficos são coleções de nós conectados por arestas. Eles podem ser usados para representar tudo, desde uma rede social até sistemas rodoviários e conexões elétricas em uma placa de circuito. Nas placas de circuito, se o gráfico não for plano, significa que dois fios se cruzam e causam curto-circuito.
Já em 1913, gráficos planares surgiram em um quebra-cabeça chamado problema dos três utilitários, publicado na The Strand Magazine. Ele pediu aos leitores que conectassem três casas a três concessionárias – água, gás e eletricidade – sem cruzar nenhuma das conexões. Não demora muito para ver que isso não pode ser feito.
Mas nem sempre é imediatamente óbvio se os gráficos mais complicados são planos. E é ainda mais difícil dizer se um gráfico planar complicado permanece plano quando você começa a adicionar arestas, como faria ao planejar um novo trecho de rodovia.
Os cientistas da computação estão procurando por um algoritmo que possa determinar rapidamente se você pode fazer a mudança desejada enquanto mantém o gráfico plano e sem verificar cada parte do gráfico quando apenas uma pequena parte é afetada. O algoritmo de 1996 exigiu uma série de etapas computacionais que eram aproximadamente proporcionais à raiz quadrada do número de nós no gráfico.
“[É] muito melhor do que fazer tudo do zero a cada vez, mas não é muito bom”, disse Holm.
O novo algoritmo verifica a planaridade em uma série de etapas proporcionais ao cubo do logaritmo do número de nós no gráfico – uma melhoria exponencial. Holm e Rotenberg, um cientista da computação da Universidade Técnica da Dinamarca, alcançaram a aceleração aproveitando uma propriedade especial dos gráficos planares que descobriram no ano passado.
Para entender seu método, a primeira coisa a notar é que o mesmo gráfico planar pode ser desenhado de várias maneiras. Nesses desenhos diferentes, as conexões permanecem as mesmas, mas as bordas podem estar em posições diferentes umas em relação às outras.
Por exemplo, você pode mudar o desenho A para o desenho B virando o triângulo feito pelos nós 1, 2 e 3 sobre a borda que conecta os nós 2 e 3. A seção superior do desenho B também pode ser refletida sobre os nós 4 e 5 para produzir o desenho C. Os desenhos parecem diferentes, mas são o mesmo gráfico.
Agora imagine que você deseja inserir uma nova aresta conectando dois nós em um grafo planar, digamos os nós 1 e 6 no exemplo abaixo. Para fazer isso, você vai realizar uma série de inversões. Da posição inicial à esquerda, são necessárias duas voltas para mover o nó 1 para um espaço onde ele pode ser conectado ao nó 6 sem cruzar nenhuma outra aresta.
Em seu artigo de 2019, Holm e Rotenberg descobriram que alguns desenhos fornecem uma posição inicial mais vantajosa para inserir uma aresta do que outros. Esses desenhos “bons” estão a apenas alguns passos de aceitar a aresta sem quebrar a planaridade.
O que eles reconheceram tardiamente em outubro foi que uma virada que aproxima você da capacidade de adicionar uma nova borda também deixa o gráfico mais próximo de se parecer com um dos bons desenhos que eles já haviam identificado. Ao mostrar que uma série de flips inevitavelmente move um gráfico em direção a um desenho favorável, o novo algoritmo coloca uma barreira no número de flips que você possivelmente precisa realizar antes de encontrar uma maneira de inserir uma aresta (desde que a inserção seja possível) .
“Percebemos rapidamente que, com essa nova análise, um algoritmo conceitualmente muito simples resolverá o problema”, disse Holm.
O novo algoritmo executa as inversões, uma de cada vez, em busca de uma solução. Eventualmente, uma de duas coisas acontece: ou o algoritmo encontra uma maneira de inserir a aresta desejada ou o próximo giro desfaz o giro anterior – ponto em que o algoritmo conclui que não há maneira de adicionar a aresta.
“Chamamos isso de [algoritmo] preguiçoso e ganancioso”, explicou Rotenberg. “Faz apenas as mudanças necessárias para acomodar a borda.”
Seu novo método aborda – mas não consegue – o desempenho do melhor algoritmo possível (ou limite inferior) para este tipo de problema. O novo algoritmo também tem que trabalhar com muitas etapas para a maioria das aplicações do mundo real, onde os gráficos relevantes são geralmente simples o suficiente para verificar com métodos de força bruta.
Mas para Holm e Rotenberg, a velocidade do algoritmo é menos importante do que os insights que o aceleraram. “Dessa compreensão surge algo rápido”, disse Rotenberg.
E Italiano acha que pode eventualmente ajudar com aplicações do mundo real. “[É] provável que tenha, mais cedo ou mais tarde, um impacto também fora da ciência da computação e da matemática”, disse ele.
Quanto a quando um algoritmo ainda mais rápido aparecerá, ninguém sabe. Isso pode exigir uma descoberta totalmente nova, ou o ingrediente secreto pode já estar lá fora, esperando em uma pilha de antigos artigos de pesquisa.
Publicado em 18/09/2020 17h35
Artigo original:
Achou importante? Compartilhe!
Assine nossa newsletter e fique informado sobre Astrofísica, Biofísica, Geofísica e outras áreas. Preencha seu e-mail no espaço abaixo e clique em “OK”: