Algorithme de Dijkstra sur d'énormes graphes

15

Je connais très bien Dijkstra et j'ai une question spécifique sur l'algorithme. Si j'ai un énorme graphique, par exemple 3,5 milliards de nœuds (toutes les données OpenStreetMap), je ne pourrais clairement pas avoir le graphique en mémoire, donc le graphique est stocké sur disque dans une base de données.

Il existe des bibliothèques pour calculer les chemins les plus courts sur ces graphiques. comment font-ils ça? Plus précisément, comment chargent-ils la partie requise du graphique pour exécuter l'algorithme de Dijkstra?

La récupération de la liste de contiguïté de chaque sommet visité nécessiterait environ 1 500 requêtes de base de données pour 10 000 nœuds selon mes données statistiques, de sorte que ce n'est clairement pas la façon dont elles le font. Ce serait beaucoup trop lent.

Comment font-ils? J'essaie de le mettre en œuvre moi-même.

dimitris93
la source
2
Êtes-vous sûr qu'ils utilisent Dijkstra? Il existe de nombreux autres algorithmes de chemin le plus court qui peuvent être mieux adaptés à la situation que vous décrivez.
David Richerby
1
Avez-vous regardé le code? Comment faut-il savoir? "requêtes de base de données" - J'espère que vous n'utilisez pas de SGBD pour stocker des graphiques?
Raphael
@DavidRicherby oui je suis sûr, regardez ce lien
dimitris93
2
"[I] t serait un processus extrêmement fastidieux d'examiner le code C pur." Mais c'est la seule façon de savoir ce que fait le code. Vous nous demandez donc de faire votre tâche fastidieuse, ce qui n'est pas la meilleure annonce pour votre question ...
David Richerby
1
@Shiro Vous demandez explicitement: "Comment font-ils cela?" Si ce n'est pas vraiment la question que vous voulez poser, vous devez reformuler.
Raphael

Réponses:

6

Il existe des bibliothèques pour calculer les chemins les plus courts sur ces graphiques. comment font-ils ça? Plus précisément, comment chargent-ils la partie requise du graphique pour exécuter l'algorithme de Dijkstra?

Vous pouvez utiliser une base de données, un format de fichier personnalisé à lire à partir du disque et un paramètre en mémoire.

Mais d'après mon expérience, l'utilisation d'une base de données est environ 5 à 10 fois plus lente et beaucoup plus intense en mémoire que l'écriture de votre propre format de fichier basé sur un format de liste liée «simple».

La bonne chose est qu'il existe plusieurs frameworks logiciels utilisant OSM qui sont open source afin que vous puissiez regarder directement dans le code, par exemple voir ici . Dans le moteur de routage open source GraphHopper, il est très facile de passer d'un paramètre mappé en mémoire (sur disque) au paramètre en mémoire - les deux utilisant le même format. Le paramètre "mmap" permet même une utilisation sur des appareils mobiles à mémoire limitée et ce dernier fonctionne beaucoup plus rapidement si vous avez la RAM nécessaire, par exemple sur un serveur. Par exemple, pour un graphique mondial (> 100 millions de nœuds), vous avez alors besoin d'environ 8 à 10 Go de RAM, ainsi que beaucoup plus de RAM si vous souhaitez accélérer tout, par exemple avec les hiérarchies de contraction - environ 5 à 8 Go de plus pour chaque véhicule que vous voulez.

Le format est très simpliste et ne stocke essentiellement que les données dont vous avez besoin avec quelques astuces pour le rendre compact. En savoir plus ici . Avertissement: je suis l'auteur de GraphHopper.

Concernant les autres réponses:

L'algorithme de Dijkstras, s'il est applicable, est considéré comme non optimal pour ce problème

Le Dijkstra `` normal '' peut fonctionner très raisonnablement (<1s pour les requêtes à l'échelle nationale comme votre exemple de 3 millions de nœuds) et est optimal dans le `` sens théorique '' mais a besoin d'un peu de réglage pour accélérer dans les scénarios de production. Et des techniques comme les Hiérachies de Contraction en utilisent une modification bidirectionnelle et fonctionnent très bien.

les réseaux routiers sont hiérarchiques et plans.

les réseaux routiers sont hiérarchiques pour la voiture uniquement et non planaires (ponts, tunnels, ...)

Karussell
la source
J'ai une autre question. Comment trouvez-vous NodeIDle nœud le plus proche du latitude/longitude? Cela est nécessaire pour calculer le chemin le plus court A-> B. Et nous devons également garder à l'esprit que A et B peuvent ne pas exister en tant que nœuds, car tous les mètres carrés ne contiennent pas de nœud. Nous devons donc trouver les 2 NodeID les plus proches de A et B.
dimitris93
Cela se fait dans le LocationIndexTree qui est une sorte de quadruple arbre stockant efficacement les NodeIDs dans une cellule qui a par exemple pour GraphHopper un rayon de ~ 500m. Si rien n'est trouvé, il élargit le rayon jusqu'à un certain degré. Cela semble simple en théorie mais est très complexe car vous pouvez avoir des bords traversant la zone, vous devez être efficace lors de la création et de l'interrogation et bien plus encore.
Karussell
Les arbres KD ne sont-ils pas plus efficaces pour rechercher le plus proche voisin? Pourquoi avez-vous choisi QuadTrees plutôt que KD-Trees? J'implémente KD-Trees pour mon moteur de routage en ce moment. J'ai commencé à implémenter QuadTrees mais je me suis arrêté parce que je pensais que KD-Trees était la même chose, mais plus facile à coder et plus rapide à interroger le plus proche voisin. Ai-je tort ?
dimitris93
Lors de l'utilisation de quadtrees, il n'est pas nécessaire de stocker explicitement la boîte englobante, ce qui lui donne un avantage de stockage, ce qui était plus critique pour mon cas d'utilisation (je trouve également les quadtrees plus faciles;)). La vitesse de requête n'est pas un problème. En fait, quelqu'un a étudié de tels essais et il a surpassé toutes les autres implémentations incl. Arbres KD, mais je suppose que tout dépend de la mise en œuvre spécifique ...
Karussell
Si vous regardez la page 9 de ce pdf de stanford, la recherche du plus proche voisin dans KD-Trees ne vous oblige pas du tout à connaître les cadres de délimitation. Et une autre chose est que parce que nous connaissons tous les points à l'avance, nous pouvons créer un arbre équilibré de hauteur de connexion. Êtes-vous toujours convaincu que les quadtrees ont un avantage sur les arbres kd?
dimitris93
2

Vous n'avez pas besoin de placer tous les bords adjacents dans la file d'attente prioritaire. "Lie" à l'algorithme de Dijkstra et ne lui donne que le sommet le plus court, v, incident au sommet, disons w, retiré de la pile. Ensuite, lorsque v est retiré de la file d'attente, vous dites "oups", j'ai fait une erreur et j'aurais dû vous donner également ce sommet, qui est le prochain plus proche du sommet w. On voit facilement que de cette façon, vous aurez une solution correcte et la taille de la file d'attente est considérablement réduite à un seul sommet incident au lieu de plusieurs. Vous devez cependant garder une trace des incidences pour toujours donner le prochain sommet le plus proche - si nécessaire. L'un des commentaires prétend que les réseaux routiers sont plans, ce qui est incorrect. En fait, une étude a montré qu'ils sont très non plans. Pensez à toutes les autoroutes traversant des ponts à travers une ville induisant de nombreuses non planarités.

user49040
la source
0

L'algorithme de Dijkstras, bien qu'applicable, est considéré comme non optimal pour ce problème, bien que des variantes plus efficaces puissent être considérées comme "similaires". il existe différentes simplifications. les réseaux routiers sont hiérarchiques et plans . voici les approches de base. la zone est généralement connue sous le nom de "planification d'itinéraire dans les réseaux routiers".

  • une structure de graphe peut être "compilée" à partir des données de la liste d'adjacence. c'est l'approche de la bibliothèque que vous citez , SpatiaLite. ces structures de graphiques sont stockées dans un format binaire compressé où les emplacements de graphiques sont représentés par des entiers codés binaires, etc., de sorte que la représentation et la manipulation des graphiques prennent beaucoup moins de place que le stockage de tous les noms de routes, etc. il semble que l'algorithme SpatiaLite ne soit pas "en ligne" et fonctionne entièrement en mémoire.

  • il existe des algorithmes parallèles / distribués. voir par exemple le graphique GPU évolutif Traversal / Merrill, Garland, Grimshaw.

  • la question utilise la terminologie client-serveur, c'est-à-dire "requêtes". les algorithmes ne s'exécutent pas en "interrogeant" la base de données au sens client-serveur. les langages de requête de niveau supérieur tels que SQL sont une interface avec la base de données et peuvent être utilisés pour transmettre la demande de calcul des routes minimales mais ne sont pas utilisés par l'algorithme en interne. généralement, l'algorithme s'exécute "à l'intérieur de la base de données", c'est-à-dire entièrement "côté serveur". il est donc possible d'écrire un algorithme de chemin le plus court dans les requêtes de base de données pour les petits réseaux mais pas pour les réseaux à moyenne / grande échelle.

  • il existe une autre approche où des estimations à l'intérieur de petits pourcentages peuvent être acceptables. l'idée de base est de garder un index des distances entre les nœuds. voir par exemple Estimation rapide et précise des chemins les plus courts dans les grands graphiques / Gubichev, Bedathur, Seufert, Weikum

  • cette thèse (235p!) est particulièrement applicable. Planification d'itinéraire dans les réseaux routiers / Schultes

  • certains algorithmes utilisent bon nombre de ces idées et d'autres, sont hautement adaptés et exclusifs et frôlent les secrets commerciaux concurrentiels. par exemple Google. il peut y avoir des médias trompeurs à ce sujet. Par exemple , l'algorithme simple et élégant qui rend possible Google Maps qui prétend / implique que Google utilise l'algorithme de Dijkstras sans aucune citation.

vzn
la source
1
Google Maps est certainement passé à quelque chose de mieux que Dijskstra. Chaque développeur compétent à mi-chemin utiliserait A * pour les cartes routières, mais lors de mon travail précédent, nous avons découvert que le moteur de Google pouvait replanifier des itinéraires de 2500 km via un waypoint en <100 ms. C'est trop rapide pour A *, il est donc probable qu'ils utilisent quelque chose comme ArcFlags.
MSalters
La réponse de Karussell remet en question cette phrase d'ouverture "L'algorithme de Dijkstras, s'il est applicable, est considéré comme non optimal pour ce problème", ce qui ne devrait pas être controversé. il y a un très fort soutien pour l'affirmation dans la thèse de Schultes (au début) qui est également une étude très complète / récente de la région, et explique également les "approximations" "hiérarchiques et planes". malheureusement, il ne semble pas y avoir d'indication des algorithmes google réels dans la littérature ouverte sur la recherche superficielle.
vzn
-2

Sur des ensembles de données extrêmement volumineux comme celui-ci, pour obtenir des résultats aussi rapides, je trouve préférable d'utiliser une structure de données de type union avec compression de chemin. Cependant, si vous cherchez à utiliser uniquement l'algorithme de Djikstra et à l'optimiser, cela se résume à quelles informations chaque nœud du graphique possède. Vous n'avez probablement pas besoin de faire toutes les 1 500 requêtes.

Par exemple, considérons l'exemple suivant. Disons que j'essaie de trouver les degrés de séparation entre 2 acteurs (le numéro de Bacon) et que je veux trouver le chemin le moins pondéré (chemin utilisant les films les plus récents possibles). Maintenant, disons que j'ai une fonction appelée shortestPath(actor A, actor B);. Considérez le scénario suivant.

Si l'acteur A a agi depuis 1970 et l'acteur B a agi depuis 2000, alors étant donné cette information, il serait beaucoup plus logique de trouver un chemin à partir du premier film de l'acteur B, puis en traversant votre chemin vers l'acteur A. Comme plutôt que d'itérer à travers chaque film, l'acteur A a joué.

Ainsi, le point principal est que l'optimisation de l'algorithme de Djikstra dépend vraiment de ce qu'est votre ensemble de données. Vous devrez fournir plus d'informations sur ce que votre ensemble de données implique pour nous afin de vous aider à optimiser votre algorithme.

EDIT: Disons que vous essayez de trouver le chemin le plus court entre 2 villes dans le même pays et si ce pays est plus long que plus large, par exemple l'Argentine, alors vous pouvez faire vos requêtes en fonction de la longitude et de la latitude des pays limites. Ensuite, vous pouvez commencer à traverser verticalement (en utilisant la longitude) plutôt qu'horizontalement. Ofc, il devrait y avoir une gestion des exceptions, mais vous avez l'idée générale.

Jonathan
la source
1
Comment utilisez-vous Union-Find à Dijkstra?
Raphael
Les données sont des données spatiales, la latitude et la longitude. Je pensais que c'était clair.
dimitris93