versão original de esta história apareceu em Revista Quanta.
Quando você quer resolver um problema difícil, a organização geralmente ajuda. Por exemplo, você pode dividir o problema em partes e resolver primeiro a parte mais fácil. No entanto, este tipo de classificação é caro. Pode demorar muito para organizar as peças.
Este dilema é particularmente relevante para um dos problemas mais emblemáticos da ciência da computação: encontrar o caminho mais curto de um determinado ponto de partida para todos os outros pontos de uma rede. É como uma versão melhorada do problema que você precisa resolver sempre que se move. Trata-se de aprender o melhor caminho da sua nova casa para o trabalho, a academia e o supermercado.
“O caminho mais curto é um belo problema com o qual todas as pessoas no mundo podem se identificar”, disse ele. Mikkel Thorupcientista da computação da Universidade de Copenhague.
Intuitivamente, é mais fácil encontrar o caminho mais curto para destinos próximos. Portanto, se você deseja projetar o algoritmo mais rápido possível para um problema de caminho mais curto, parece razoável começar encontrando o ponto mais próximo, depois o próximo ponto mais próximo e assim por diante. No entanto, isso requer uma determinação iterativa de quais pontos estão mais próximos. Classifique os pontos por distância conforme você se move. Algoritmos que seguem esta abordagem têm um limite de velocidade fundamental. Não pode ser mais rápido do que o tempo necessário para classificar.
Quarenta anos atrás, pesquisadores que projetavam algoritmos de caminho mais curto atingiram essa “parede de classificação”. Atualmente, uma equipe de pesquisadores desenvolveu Um novo algoritmo para superá-lo. Ele não realiza nenhuma classificação e é executado mais rapidamente do que os algoritmos que o fazem.
“Os autores foram ousados o suficiente para pensar que poderiam romper esta barreira.” Roberto Tarjancientista da computação da Universidade de Princeton. “Esse é um ótimo resultado.”
fronteira do conhecimento
Para analisar matematicamente problemas de caminho mais curto, os pesquisadores usam a linguagem de 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 rota mais curta é aquela com a menor soma de pesos. Dado um grafo e um determinado nó “fonte”, o objetivo do algoritmo é encontrar o caminho mais curto para todos os outros nós.
de O algoritmo de caminho mais curto mais famoso, concebido Criado pelo pioneiro cientista da computação Edgar Dijkstra em 1956, esse método começa na fonte e funciona em etapas. Esta é uma abordagem eficaz porque conhecer o caminho mais curto para nós próximos ajuda a encontrar o caminho mais curto para nós mais distantes. No entanto, 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.
