.
Por mais de meio século, pesquisadores de todo o mundo têm lutado com um problema algorítmico conhecido como “o problema do caminho mais curto de fonte única”. O problema consiste essencialmente em como conceber uma receita matemática que melhor encontre o caminho mais curto entre um nó e todos os outros nós de uma rede, onde podem existir ligações com pesos negativos.
Parece complicado? Possivelmente. Mas, na verdade, esse tipo de cálculo já é usado em uma ampla variedade de aplicativos e tecnologias das quais dependemos para nos orientarmos – como o Google Maps nos guia por paisagens e cidades, por exemplo.
Agora, pesquisadores do Departamento de Ciência da Computação da Universidade de Copenhague conseguiram resolver o problema do caminho mais curto de fonte únicaum enigma que intriga pesquisadores e especialistas há décadas.
“Descobrimos um algoritmo que resolve o problema em tempo praticamente linear, da maneira mais rápida possível. É um problema algorítmico fundamental, estudado desde a década de 1950 e ensinado em todo o mundo. Esse foi um dos motivos que nos levou a resolver isso”, explica o professor associado Christian Wulff-Nilsen, que claramente acha difícil deixar um problema algorítmico não resolvido sozinho.
Cálculos mais rápidos para roteamento de carros elétricos
No ano passado, Wulff-Nilsen fez outra descoberta na mesma área, que produziu um resultado que abordou como encontrar o caminho mais curto em uma rede que muda com o tempo. Sua solução para o enigma recente se baseia nesse trabalho.
O pesquisador acha que resolver o problema do caminho mais curto de fonte única pode abrir caminho para algoritmos que não apenas ajudam os carros elétricos a calcular a rota mais rápida de A a B em um instante, mas também o fazem da maneira mais eficiente em termos de energia.
“Estamos adicionando uma dimensão que os algoritmos anteriores não possuem. Essa dimensão nos permite ver o que chamamos de pesos negativos. Um exemplo prático disso pode ser com referência às colinas em uma rede rodoviária, o que é bom saber se você tem um carro elétrico que carrega enquanto desce”, explica Wulff-Nilsen.
Fatos sobre o problema do caminho mais curto de fonte única
- A mira de o caminho mais curto de fonte única O problema é encontrar os caminhos mais curtos de um determinado nó inicial para todos os outros nós em uma rede.
- A rede é representada como um grafo formado por nós e conexões entre eles, chamadas de arestas.
- Cada borda tem uma direção (por exemplo, isso pode ser usado para representar estradas de mão única), bem como um peso, que expressa o quanto custa viajar ao longo dessa borda. Se todos os pesos das arestas forem não negativos, o problema pode ser resolvido em tempo virtualmente linear com um algoritmo clássico de Dijkstra.
- O novo resultado resolve o problema quase na mesma quantidade de tempo que o algoritmo de Dijkstra, mas também permite pesos de borda negativos.
“Em princípio, o algoritmo poderia ser usado para alertar atores, como bancos centrais, se especuladores estão especulando sobre a compra e venda de várias moedas. Muito disso acontece usando computadores hoje. Mas como nosso algoritmo é tão rápido, pode ser capaz de para ser usado para detectar brechas antes de serem exploradas”, diz Christian Wulff-Nilsen.
O pesquisador destaca que já existem sistemas de cálculo tanto de moeda quanto de rotas para carros elétricos. Mas resolver o problema do caminho mais curto de fonte única permitiu que os pesquisadores criassem um excelente algoritmo que se torna quase impossível de superar em relação à velocidade. Ao mesmo tempo, sua simplicidade facilita a adoção para as diversas necessidades da sociedade.
Homenageado nos EUA
O trabalho para resolver o problema não passou despercebido. De fato, Christian Wulff-Nilsen e seus colegas já foram contatados por pessoas de todo o mundo para parabenizá-los e saber mais sobre como eles fizeram isso.
Ao mesmo tempo, o artigo de pesquisa que detalha sua descoberta foi homenageado com o “prêmio de melhor artigo” na conferência FOCS (Fundação da Ciência da Computação) em Denver, Colorado. Juntamente com o STOC, é a conferência de maior prestígio em ciência da computação teórica. A conferência FOCS decorreu de 31 de outubro a 3 de novembro de 2022.
“Pessoas de todo o mundo participam desta conferência para ver os melhores resultados sendo apresentados”, diz Christian Wulff-Nilsen.
A pesquisa foi realizada em colaboração entre Christian Wulff-Nilsen, do Departamento de Ciência da Computação, Danupon Nanongkai, do Max Planck Institute, e seu colega americano, Aaron Bernstein, da Rutgers University.
.
