Dois cientistas da computação encontraram uma ideia em um lugar muito inesperado que lhes serviu apenas para um avanço na teoria dos gráficos
Em outubro de 2019, Jacob Holm e Eva Rotenberg estavam folheando um trabalho que haviam publicado alguns meses antes - e de repente perceberam que haviam tropeçado em algo sério.
Durante décadas, os cientistas da computação tentaram desenvolver um algoritmo rápido para determinar se as arestas podem ser adicionadas a um gráfico específico para que permaneça “plano” - isto é, para que suas arestas não se cruzem. No entanto, ninguém conseguiu melhorar o algoritmo publicado há mais de 20 anos.
Holm e Rothenberg ficaram surpresos ao descobrir isso em seu trabalhoexiste uma ideia que tornou possível melhorar este algoritmo bastante fortemente. Ela "resolveu um dos maiores obstáculos para um algoritmo real", disse Holm, cientista da computação da Universidade de Copenhagen. "Talvez tenhamos divulgado totalmente esse problema."
O casal correu para trabalhar em um novo artigo . Eles o apresentaram em junho no Association for Computing Machinery Symposium on Computational Theory , onde detalharam um método para verificar a planaridade de um gráfico, exponencialmente superior à versão anterior.
“O novo algoritmo é verdadeiramente magistral”, disse Giuseppe Italiano , um cientista da computação da Universidade de Louis, coautor de um artigo de 1996 que agora descreve o segundo algoritmo mais rápido. "Quando estive envolvido na redação desse trabalho, não pensei que isso pudesse acontecer."
Os gráficos são coleções de vértices conectados por arestas. Eles podem ser usados para rotular tudo, desde mídia social a redes rodoviárias e condutores elétricos em uma placa. Se, neste último caso, o gráfico não for plano, os dois condutores se cruzarão, o que levará a um curto-circuito.
Em 1913, gráficos planares apareceram em um quebra-cabeça "comum" complexo sobre três casas , publicado na The Strand Magazine. A publicação pediu aos leitores que estabelecessem comunicações para três casas, conectando cada uma delas com três portadores de energia - água, gás e eletricidade - para que as comunicações não se cruzassem. Não demora muito para perceber que essa tarefa é intransponível.
No entanto, em casos com gráficos mais complexos, nem sempre é óbvio se eles são planos. É ainda mais difícil dizer se um gráfico complexo permanecerá plano quando você começar a adicionar arestas a ele - como é o caso ao planejar novas estradas.
Os cientistas da computação há muito procuram um algoritmo que possa determinar rapidamente se a mudança desejada pode ser feita de modo que o gráfico permaneça plano, sem passar por cada uma das partes do gráfico quando apenas uma pequena parte dele é alterada. O algoritmo de 1996 exigiu uma série de etapas para isso, aproximadamente proporcional à raiz quadrada do número de vértices no gráfico.
“É muito melhor do que verificar tudo do zero sempre, mas não perfeito”, disse Holm.
O novo algoritmo verifica a planaridade em um número de etapas proporcionais ao cubo do logaritmo do número de vértices no gráfico - a melhoria é exponencial. Holm e Rothenberg, da Universidade Técnica Dinamarquesa, alcançaram essa aceleração tirando vantagem de uma propriedade especial dos gráficos planares que descobriram no ano passado.
Para entender seu método, você deve primeiro notar que o mesmo gráfico planar pode ser desenhado de maneiras diferentes . Todas as conexões dessas opções permanecem as mesmas, no entanto, as bordas podem ser localizadas em relação umas às outras de maneiras diferentes.
Por exemplo, a figura A pode ser alterada para a figura B invertendo o triângulo que constitui os vértices 1, 2 e 3 em relação à aresta que conecta os vértices 2 e 3. O topo da figura B também pode ser invertido em relação aos vértices 4 e 5, resultando na figura C. As figuras se parecem com diferentemente, mas denotam o mesmo gráfico.
Agora imagine que você deseja inserir uma nova aresta que conecta dois vértices de um gráfico planar - digamos, vértices 1 e 6. Para fazer isso, você executa uma sequência de inversões. Da posição inicial à esquerda, em duas voltas, você pode transferir o vértice 1 para o local onde ele pode ser conectado ao vértice 6 sem cruzar outras arestas.
Em um artigo de 2019, Holm e Rothenberg descobriram que alguns desenhos têm mais vantagens para a inserção de bordas do que outros. Esses padrões “bons” precisam apenas de algumas voltas para adicionar uma nova aresta sem quebrar a planaridade.
O que eles perceberam tardiamente em outubro é que uma virada que o aproxima da posição em que você pode adicionar uma nova aresta também aproxima o gráfico de um dos bons padrões que eles já definiram. Ao mostrar que uma sequência de flips inevitavelmente aproxima o gráfico dos padrões preferidos, um novo algoritmo pode ser feito para limitar o número de flips que você pode precisar para encontrar uma maneira de adicionar uma aresta (se possível).
“Percebemos muito rapidamente que com esta nova análise o problema poderia ser resolvido
um algoritmo de conceito extremamente simples ”, disse Holm.
Jacob Holm e Eva Rothenberg O
novo algoritmo realiza uma virada de cada vez em busca de uma solução. Como resultado, uma de duas coisas acontece: ou o algoritmo encontra uma maneira de inserir a aresta necessária ou o próximo flip cancela a anterior - após o que o algoritmo conclui que não há como adicionar uma nova aresta.
“Chamamos esse algoritmo de ganancioso preguiçoso”, explicou Rotenberg. "Faz apenas as alterações necessárias para acomodar a nova costela."
Seu novo método se aproxima - mas não corresponde - ao desempenho do melhor algoritmo possível para tais tarefas. O novo algoritmo também tem que passar por muitas etapas para ser usado na maioria dos aplicativos do mundo real - geralmente os gráficos são simples o suficiente para serem testados com força bruta.
Mas para Holm e Rothenberg, a velocidade do algoritmo não é tão importante quanto as idéias que o aceleraram. "Há implicações imediatas desse entendimento", disse Rotenberg.
Italiano acredita que eventualmente encontrará usos reais. “Mais cedo ou mais tarde, isso certamente afetará o que está fora da ciência da computação com a matemática”, disse ele.
Ninguém sabe quando algoritmos ainda mais rápidos podem aparecer. Isso pode exigir uma descoberta completamente nova, ou o ingrediente secreto pode já existir em algum lugar, esperando nas asas em uma pilha de pesquisas antigas.