A versão original de esta história apareceu em Revista Quanta.
Se você quiser resolver um problema complicado, muitas vezes ajuda se organizar. Você pode, por exemplo, dividir o problema em partes e resolver primeiro as partes mais fáceis. Mas esse tipo de classificação tem um custo. Você pode acabar gastando muito tempo colocando as peças em ordem.
Este dilema é especialmente relevante para um dos problemas mais emblemáticos da ciência da computação: encontrar o caminho mais curto de um ponto de partida específico em uma rede para todos os outros pontos. É como uma versão aprimorada de um problema que você precisa resolver cada vez que se muda: aprender o melhor caminho da sua nova casa para o trabalho, a academia e o supermercado.
“Os caminhos mais curtos são um belo problema com o qual qualquer pessoa no mundo pode se identificar”, disse Mikkel Thorupcientista da computação da Universidade de Copenhague.
Intuitivamente, deveria ser mais fácil encontrar o caminho mais curto para destinos próximos. Portanto, se você quiser projetar o algoritmo mais rápido possível para o problema dos caminhos mais curtos, parece razoável começar encontrando o ponto mais próximo, depois o próximo mais próximo e assim por diante. Mas para fazer isso, você precisa descobrir repetidamente qual ponto está mais próximo. Você classificará os pontos por distância à medida que avança. Há um limite de velocidade fundamental para qualquer algoritmo que siga esta abordagem: você não pode ir mais rápido do que o tempo necessário para classificar.
Quarenta anos atrás, pesquisadores que projetavam algoritmos de caminhos mais curtos se depararam com essa “barreira de classificação”. Agora, uma equipe de pesquisadores desenvolveu um novo algoritmo que o quebra. Ele não classifica e é executado mais rápido do que qualquer algoritmo que o faça.
“Os autores foram audaciosos ao pensar que poderiam quebrar essa barreira”, disse Roberto Tarjancientista da computação da Universidade de Princeton. “É um resultado incrível.”
A Fronteira do Conhecimento
Para analisar matematicamente o problema dos caminhos mais curtos, os pesquisadores usam a linguagem dos gráficos – redes de pontos, ou nós, conectados por linhas. Cada link entre nós é rotulado com um número chamado peso, que pode representar o comprimento desse segmento ou o tempo necessário para atravessá-lo. Geralmente existem muitas rotas entre dois nós quaisquer, e a mais curta é aquela cujos pesos somam o menor número. Dado um gráfico e um nó “fonte” específico, o objetivo de um algoritmo é encontrar o caminho mais curto para todos os outros nós.
O algoritmo de caminhos mais curtos mais famoso, concebido pelo pioneiro cientista da computação Edsger Dijkstra em 1956, começa na fonte e avança passo a passo. É uma abordagem eficaz, porque conhecer o caminho mais curto para os nós próximos pode ajudá-lo a encontrar os caminhos mais curtos para os nós mais distantes. Mas como o resultado final é uma lista ordenada de caminhos mais curtos, a barreira de ordenação estabelece um limite fundamental para a velocidade de execução do algoritmo.
