O algoritmo de Dijkstras é usado em sistemas modernos de busca de rotas?

10

O algoritmo de Dijkstra é usado em sistemas modernos de busca de rotas, como mapas do Google ou o satélite no seu carro? Se não, então o que é?

algorithms graphs shortest-path applied-theory helicóptero desenhar lion4
fonte
Eu acho que você quer dizer o componente de roteamento que encontra o seu caminho, uma vez que o GPS, que é principalmente um posicionamento global da Syatem, determinou onde você está . Outro caso de rabo balançando um cachorro.
babou
11
Não posso fornecer uma fonte para isso, mas meu atual professor de Algoritmos trabalha na indústria e diz que é muito usado na prática, especialmente para GPS. Se você usa a Distância Euclidiana como uma heurística, tende a obter melhorias sobre as de Dijstra, ignorando caminhos que não fazem sentido na vida real. Você já deve saber, mas o de Dijkstra pode ser descrito como com heurística . A∗A∗h(x)=0
jmite

Respostas:

8

O Google Maps em 2009 usou Hierarquias de Contração - veja esta conversa sobre tecnologia .

Desde então, alguns métodos alucinantes foram descobertos, capazes de realizar rotas através dos países em milissegundos fracionários - os chamados "oráculos à distância de rotulagem de dois saltos". Veja aqui ou pesquise "Rotulagem de hub" ou "Caminhos mais curtos para as massas". Acho que ouvi o Bing usar esse. Também possui aplicativos como a capacidade de encontrar o ponto de interesse mais próximo (por exemplo, posto de gasolina mais próximo) com uma complexidade independente do número de postos de gasolina.

jkff
fonte
2
Isso parece ser uma referência útil. No entanto, você pode: a) fornecer referências citáveis ​​e / ou b) pintar o quadro geral de como elas funcionam? Em particular, eles resolvem o problema exatamente?
Raphael