Algoritmo de Dijkstra em grandes gráficos

Eu estou muito familiarizado com Dijkstra e tenho uma pergunta específica sobre o algoritmo. Se eu tiver um gráfico enorme, por exemplo, 3,5 bilhões de nós (todos os dados do OpenStreetMap), claramente não seria capaz de ter o gráfico na memória; portanto, o gráfico é armazenado em disco em um banco de dados.

Existem bibliotecas disponíveis para calcular os caminhos mais curtos nesses gráficos. Como eles fazem isso? Mais especificamente, como eles carregam a parte necessária do gráfico para executar o algoritmo de Dijkstra?

Buscar a lista de adjacências de cada vértice visitado exigiria cerca de 1.500 consultas ao banco de dados por 10.000 nós, de acordo com meus dados estatísticos, de modo que claramente não é assim que eles fazem isso. Isso seria muito lento.

Como eles fazem isso? Eu estou tentando implementá-lo eu mesmo.

Existem bibliotecas disponíveis para calcular os caminhos mais curtos nesses gráficos. Como eles fazem isso? Mais especificamente, como eles carregam a parte necessária do gráfico para executar o algoritmo de Dijkstra?

Você pode usar um banco de dados, um formato de arquivo personalizado para ser lido do disco e uma configuração na memória.

Mas, pela minha experiência em usar um banco de dados, é aproximadamente 5 a 10 vezes mais lento e muito mais memória intenso do que gravar seu próprio formato de arquivo com base em um formato de lista vinculada "simples".

O bom é que existem várias estruturas de software usando OSM, que são de código aberto, para que você possa olhar diretamente para o código, por exemplo, veja aqui . No mecanismo de roteamento de código aberto GraphHopper , é muito fácil alternar de uma configuração mapeada na memória (baseada em disco) para a configuração na memória - ambas usando o mesmo formato. A configuração "mmap" ainda permite o uso em dispositivos móveis com restrição de memória e o último executa muito mais rápido se você tiver a RAM necessária, por exemplo, em um servidor. Por exemplo, para um gráfico mundial (> 100 milhões de nós), você precisará de cerca de 8 a 10 GB de RAM, além de muito mais RAM, se quiser acelerar ainda mais, por exemplo, com as Hierarquias de Contração - cerca de 5-8 GB a mais para todos os veículos que desejar.

O formato é muito simplista e basicamente armazena apenas os dados necessários com alguns truques para torná-los compactos. Leia mais sobre isso aqui . Disclaimer: Eu sou o autor de GraphHopper.

Em relação às outras respostas:

O algoritmo de Dijkstras, enquanto aplicável, é considerado não ideal para este problema

O Dijkstra 'normal' pode ter um desempenho bastante razoável (<1s para consultas em todo o país, como no exemplo dos nós de 3 milhões) e é ideal no 'sentido da teoria', mas precisa de um pouco de ajuste para acelerar os cenários de produção. E técnicas como as Hierachies de Contração usam uma modificação bidirecional e têm um desempenho muito bom.

redes rodoviárias são hierárquicas e planas.

as redes rodoviárias são hierárquicas apenas para carros e não planares (pontes, túneis, ...)

Você não precisa colocar todas as arestas adjacentes na fila de prioridade. "Mentira" ao algoritmo de Dijkstra e dê a ele apenas o menor vértice v, incidente no vértice, digamos w, retirado da pilha. Então, quando v é puxado da fila, você diz "oops" Eu cometi um erro e deveria ter lhe dado esse vértice também, que é o próximo mais próximo do vértice w. É fácil perceber que dessa maneira você terá uma solução correta e o tamanho da fila é reduzido drasticamente para um vértice incidente apenas em vez de muitos. No entanto, é necessário acompanhar as incidências para sempre fornecer o próximo vértice mais próximo - quando necessário. Um dos comentários alegados é que as redes rodoviárias são planares incorretas. De fato, um estudo mostrou que eles são altamente não-planos. Pense em todas as rodovias que atravessam pontes por uma cidade induzindo muitas não-planaridades.

O algoritmo de Dijkstras, quando aplicável, é considerado não ideal para esse problema, embora variantes mais eficientes possam ser consideradas "semelhantes". existem várias simplificações. redes rodoviárias são hierárquicas e planas . Aqui estão as abordagens básicas. a área é geralmente conhecida como "planejamento de rotas em redes rodoviárias".

• uma estrutura gráfica pode ser "compilada" a partir dos dados da lista de adjacências. esta é a abordagem na biblioteca que você cita , SpatiaLite. essas estruturas gráficas são armazenadas em um formato binário compactado, em que as localizações dos gráficos são representadas por números inteiros codificados em binário, etc. parece que o algoritmo SpatiaLite não está "online" e é executado inteiramente na memória.

• existem algoritmos paralelos / distribuídos. veja, por exemplo, gráfico de GPU escalável Traversal / Merrill, Garland, Grimshaw.

• a pergunta usa a terminologia cliente-servidor, ou seja, "consultas". os algoritmos não são executados "consultando" o banco de dados no sentido cliente-servidor. linguagens de consulta de nível superior, como SQL, são uma interface para o banco de dados e podem ser usadas para transmitir a solicitação para calcular as rotas mínimas, mas não são usadas internamente pelo algoritmo. geralmente o algoritmo é executado "dentro do banco de dados", ou seja, inteiramente do lado do servidor. portanto, escrever um algoritmo de caminho mais curto em consultas de banco de dados é viável para redes pequenas, mas não para médias / grandes.

• existe outra abordagem em que estimativas dentro de pequenas porcentagens podem ser aceitáveis. a idéia básica é manter um índice de distâncias entre os nós. veja, por exemplo, estimativa rápida e precisa dos caminhos mais curtos em gráficos grandes / Gubichev, Bedathur, Seufert, Weikum

• esta tese de doutorado (235p!) é especialmente aplicável. Planejamento de rotas em redes de estradas / Schultes

• alguns algoritmos usam muitas dessas idéias e outras, são altamente afinados e proprietários e estão à beira de segredos comerciais competitivos. por exemplo, do Google. pode haver alguma mídia enganosa sobre esse assunto. por exemplo , o algoritmo simples e elegante que torna possível o Google Maps, o que afirma / implica que o Google usa o algoritmo Dijkstras sem nenhuma citação.

Em conjuntos de dados extremamente grandes como esse, para obter resultados tão rápidos, acho melhor usar uma estrutura de dados de localização de união com compactação de caminho. No entanto, se você deseja usar apenas o algoritmo do Djikstra e otimizar isso, ele se resume às informações de cada nó no gráfico. Você provavelmente não precisará fazer todas as 1.500 consultas.

Por exemplo, considere o seguinte exemplo. Digamos que estou tentando encontrar os graus de separação entre dois atores (o número de Bacon) e quero encontrar o caminho menos ponderado (caminho usando os filmes mais recentes possíveis). Agora, digamos que eu tenho uma função chamada shortestPath(actor A, actor B);. Considere o seguinte cenário.

Se o Ator A estiver atuando desde 1970 e o Ator B estiver atuando desde 2000, então, dada essa informação, seria muito mais lógico encontrar um caminho a partir do primeiro filme do Ator B e, em seguida, percorrendo seu caminho até o Ator A. em vez de repetir todos os filmes em que o ator A atuou.

Portanto, o ponto principal é que a otimização do algoritmo do Djikstra realmente depende do seu conjunto de dados. Você precisaria fornecer mais informações sobre o que seu conjunto de dados implica para nós, para ajudá-lo a otimizar seu algoritmo.

EDIT: Digamos que você esteja tentando encontrar o caminho mais curto entre duas cidades no mesmo país e, se esse país for mais longo do que mais amplo, por exemplo, Argentina, você poderá fazer suas consultas com base na longitude e latitude dos países. limites. Em seguida, você pode começar a percorrer verticalmente (usando longitude), em vez de horizontalmente. Ofc, seria necessário um tratamento de exceção, mas você entendeu a ideia geral.