Un algorithme * pour les très grands graphiques, des reflections sur les raccourcis de mise en cache?

J’écris une simulation de messagerie / logistique sur les cartes OpenStreetMap et j’ai réalisé que l’algorithme de base A *, comme illustré ci-dessous, ne sera pas assez rapide pour les grandes cartes (comme le Grand Londres).

http://i.imgur.com/u2tVpML.jpg

Les nœuds verts correspondent à ceux qui ont été placés dans la queue ouverte / prioritaire et, en raison du nombre énorme (la carte entière est d’environ 1-2 millions), il faut environ 5 secondes pour trouver l’itinéraire illustré. Malheureusement, 100 ms par route sont à peu près ma limite absolue.

Actuellement, les nœuds sont stockés à la fois dans une liste de contiguïté et dans un tableau 2D spatial 100×100.

Je suis à la recherche de méthodes permettant d’échanger du temps de pré-traitement, de l’espace et, si nécessaire, de l’optimalité de la route, pour des requêtes plus rapides. La formule de Haversine en ligne droite pour le coût heuristique est la fonction la plus coûteuse selon le profileur – j’ai optimisé mon A * de base autant que possible.

Par exemple, je pensais que si je choisissais un nœud arbitraire X dans chaque quadrant du tableau 2D et exécutais A * entre eux, je peux stocker les itinéraires sur le disque pour les simulations ultérieures. Lors de l’interrogation, je ne peux lancer une recherche A * que dans les quadrants, pour aller entre la route précalculée et le X.

Existe-t-il une version plus raffinée de ce que j’ai décrit ci-dessus ou peut-être une méthode différente que je devrais suivre? Merci beaucoup!

Pour mémoire, voici quelques résultats de référence pour pondérer arbitrairement le coût heuristique et calculer le chemin entre 10 paires de nœuds choisis au hasard:

Weight // AvgDist% // Time (ms) 1 1 1461.2 1.05 1 1327.2 1.1 1 900.7 1.2 1.019658848 196.4 1.3 1.027619169 53.6 1.4 1.044714394 33.6 1.5 1.063963413 25.5 1.6 1.071694171 24.1 1.7 1.084093229 24.3 1.8 1.092208509 22 1.9 1.109188175 22.5 2 1.122856792 18.2 2.2 1.131574742 16.9 2.4 1.139104895 15.4 2.6 1.140021962 16 2.8 1.14088128 15.5 3 1.156303676 16 4 1.20256964 13 5 1.19610861 12.9 

En augmentant de façon surprenante le coefficient à 1,1, le temps d’exécution a presque été divisé par deux tout en gardant le même itinéraire.

Vous devriez être capable de le rendre beaucoup plus rapide en compensant l’optimalité. Voir Admissibilité et optimalité sur wikipedia.

L’idée est d’utiliser une valeur epsilon qui conduira à une solution pas pire que 1 + epsilon fois le chemin optimal, mais qui entraînera moins de nœuds dans l’algorithme. Notez que cela ne signifie pas que la solution retournée sera toujours 1 + epsilon fois le chemin optimal. C’est juste le pire des cas. Je ne sais pas exactement comment cela se comporterait dans la pratique pour votre problème, mais je pense que cela vaut la peine d’être exploré.

Vous recevez un certain nombre d’algorithmes qui s’appuient sur cette idée sur Wikipedia. Je pense que c’est votre meilleur pari pour améliorer l’algorithme et qu’il a le potentiel de fonctionner dans votre limite de temps tout en conservant de bons chemins.

Puisque votre algorithme traite des millions de nœuds en 5 secondes, je suppose que vous utilisez également des segments binarys pour l’implémentation, n’est-ce pas? Si vous les implémentez manuellement, assurez-vous qu’ils sont implémentés en tant que tableaux simples et qu’ils sont des segments binarys.

Il existe des algorithmes spécialisés pour ce problème qui font beaucoup de pré-calcul. De la mémoire, le pré-calcul ajoute des informations au graphique qu’A * utilise pour produire une heuristique beaucoup plus précise que la distance en ligne droite. Wikipedia donne les noms d’un certain nombre de méthodes sur http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks et indique que Hub Labeling est le leader. Une recherche rapide à ce sujet apparaît http://research.microsoft.com/pubs/142356/HL-TR.pdf . Une version plus ancienne, utilisant A *, se trouve à l’ adresse http://research.microsoft.com/pubs/64505/goldberg-sp-wea07.pdf .

Devez-vous vraiment utiliser Haversine? Pour couvrir Londres, j’aurais pensé que vous auriez pu prendre une terre plate et utiliser Pythagore, ou stocker la longueur de chaque lien dans le graphique.

Il y a un très bon article que Microsoft Research a écrit sur le sujet:

http://research.microsoft.com/en-us/news/features/shortestpath-070709.aspx

Le document original est hébergé ici (PDF):

http://www.cc.gatech.edu/~thad/6601-gradAI-fall2012/02-search-Gutman04siam.pdf

Essentiellement, vous pouvez essayer quelques choses:

  1. Commencez à la fois la source et la destination. Cela permet de minimiser la quantité de travail inutile que vous effectuez lorsque vous parcourez la source vers la destination.
  2. Utilisez des repères et des autoroutes. Essentiellement, trouvez des positions dans chaque carte qui sont généralement empruntées et effectuez des calculs préalables pour déterminer comment naviguer efficacement entre ces points. Si vous pouvez trouver un chemin depuis votre source vers un sharepoint repère, puis vers d’autres points de repère, puis vers votre destination, vous pouvez rapidement trouver un itinéraire viable et optimiser à partir de là.
  3. Explorez des algorithmes comme l’algorithme “atteindre”. Cela permet de minimiser la quantité de travail que vous effectuerez lorsque vous parcourrez le graphique en minimisant le nombre de sumts à prendre en compte pour trouver une route valide.

GraphHopper fait deux choses de plus pour obtenir un routage rapide, sans heuristique et flexible (note: je suis l’auteur et vous pouvez l’essayer en ligne ici )

  1. Une optimisation moins évidente consiste à éviter le mappage 1: 1 des nœuds OSM sur les nœuds internes. Au lieu de cela, GraphHopper utilise uniquement les jonctions en tant que nœuds et enregistre environ 1/8 des nœuds traversés.
  2. Il possède des outils efficaces pour A *, Dijkstra ou, par exemple, Dijkstra un-à-plusieurs. Ce qui rend possible un itinéraire en dessous de 1 dans toute l’Allemagne. La version bidirectionnelle (non-heuristique) de A * accélère le processus.

Donc, il devrait être possible de vous obtenir des itinéraires rapides pour le grand Londres.

De plus, le mode par défaut est le mode de vitesse qui rend tout plus rapide (par exemple 30ms pour les routes européennes), mais moins flexible, car il nécessite un prétraitement ( hiérarchies de contraction ). Si vous n’aimez pas cela, désactivez-le et affinez encore les rues incluses pour la voiture ou créez probablement un nouveau profil pour les camions – par exemple, excluez les rues de service et les pistes qui devraient vous donner 30% supplémentaires. Et comme avec tout algorithme bidirectionnel, vous pouvez facilement implémenter une recherche parallèle.

Je pense que ça vaut la peine de mettre au point votre idée avec des “quadrants”. Plus ssortingctement, je l’appellerais une recherche d’itinéraire à basse résolution.

Vous pouvez sélectionner X nœuds connectés suffisamment proches et les traiter comme un nœud basse résolution unique. Divisez tout votre graphique en de tels groupes et vous obtenez un graphique en basse résolution. Ceci est une étape de préparation.

Afin de calculer un itinéraire de la source à la cible, identifiez d’abord les noeuds basse résolution auxquels ils appartiennent, puis recherchez l’itinéraire à faible résolution. Améliorez ensuite votre résultat en trouvant l’itinéraire sur un graphique haute résolution, en limitant toutefois l’algorithme uniquement aux nœuds appartenant à des nœuds basse résolution de l’itinéraire basse résolution (vous pouvez également envisager des nœuds basse résolution voisins jusqu’à une certaine profondeur). ).

Cela peut également être généralisé à plusieurs résolutions, pas seulement haut / bas.

À la fin, vous devriez avoir un itinéraire suffisamment proche de l’optimum. C’est localement optimal, mais il peut être quelque peu pire qu’optimal dans son ensemble, ce qui dépend du saut de résolution (c’est-à-dire l’approximation que vous faites lorsqu’un groupe de nœuds est défini comme un seul nœud).

Il y a des dizaines de variantes A * qui peuvent correspondre à la facture ici. Vous devez penser à vos cas d’utilisation, cependant.

  • Êtes-vous limité en mémoire (et en cache)?
  • Pouvez-vous paralléliser la recherche?
  • Votre implémentation d’algorithme sera-t-elle utilisée dans un seul endroit (par exemple, le Grand Londres et non NYC ou Mumbai ou ailleurs)?

Nous n’avons aucun moyen de connaître tous les détails auxquels vous et votre employeur avez access. Votre première étape devrait donc être CiteSeer ou Google Scholar: recherchez des articles traitant du cheminement avec le même ensemble général de contraintes que vous.

Ensuite, sélectionnez trois ou quatre algorithmes, effectuez le prototypage, testez leur évolution et optimisez-les. Vous devez garder à l’esprit que vous pouvez combiner différents algorithmes dans la même routine de grand cheminement en fonction de la distance entre les points, du temps restant ou de tout autre facteur.

Comme cela a déjà été dit, en raison de la petite taille de votre zone cible, la chute de Haversine est probablement votre première étape, ce qui vous fait gagner un temps précieux lors d’évaluations sortinggonomésortingques coûteuses. NOTE: Je ne recommande pas d’utiliser la distance euclidienne en lat, les coordonnées lon – reprojetez votre carte dans un Mercator par exemple, près du centre et utilisez les coordonnées cartésiennes en mètres ou en mètres!

La précomputation est la seconde, et changer de compilateur peut être une troisième idée évidente (passer à C ou C ++ – voir https://benchmarksgame.alioth.debian.org/ pour plus de détails).

Des étapes d’optimisation supplémentaires peuvent inclure l’élimination de l’allocation de mémoire dynamic et l’utilisation d’une indexation efficace pour la recherche parmi les nœuds (pensez à R-tree et à ses dérivés / alternatives).

J’ai travaillé dans une grande entreprise de navigation, et je peux donc affirmer que 100 ms devraient vous permettre de vous rendre de Londres à Athènes, même sur un appareil embarqué. Le Grand Londres serait une carte de test pour nous, car il est commodément petit (rentre facilement dans la RAM – ce n’est pas vraiment nécessaire)

Tout d’abord, A * est entièrement obsolète. Son principal avantage est qu’il ne nécessite “pas de prétraitement”. En pratique, vous devez de toute façon pré-traiter une carte OSM, ce qui est un avantage inutile.

Les drapeaux arc sont la technique principale pour vous donner un énorme gain de vitesse. Si vous divisez la carte en sections de 5×6, vous pouvez atsortingbuer une position de 1 bit dans un entier de 32 bits pour chaque section. Vous pouvez maintenant déterminer pour chaque bord s’il est toujours utile lorsque vous voyagez à la section {X,Y} d’une autre section. Très souvent, les routes sont bidirectionnelles, ce qui signifie qu’une seule des deux directions est utile. Donc, l’une des deux directions a ce bit et l’autre l’a effacée. Cela peut ne pas sembler être un réel avantage, mais cela signifie que sur de nombreuses intersections, vous réduisez le nombre de choix à prendre en compte de 2 à 1, et cela ne prend qu’une opération sur un seul bit.

Habituellement, A * s’accompagne d’une consommation de mémoire excessive plutôt que de contraintes temporelles.

Cependant, je pense qu’il pourrait être utile de commencer par calculer uniquement avec des nœuds qui font partie des “grandes rues”, vous choisiriez une autoroute plutôt qu’une minuscule allée.

Je suppose que vous pouvez déjà l’utiliser pour votre fonction de pondération, mais vous pouvez être plus rapide si vous utilisez une queue prioritaire pour décider du nœud à tester pour la suite du voyage.

Vous pouvez également essayer de réduire le graphe à des noeuds faisant partie des arêtes à faible coût, puis à trouver un moyen de commencer / terminer vers le plus proche de ces noeuds. Donc, vous avez deux chemins du début à la “grande rue” et la “grande rue” pour finir. Vous pouvez maintenant calculer le meilleur chemin entre les deux nœuds qui font partie des “grandes rues” dans un graphique réduit.

Ancienne question, mais encore:

Essayez d’utiliser différents tas que “tas binary”. “Le meilleur tas de complexité asymptotique” est sans aucun doute Feaponacci Heap et sa page wiki a un bon aperçu:

https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times

Notez que le tas binary a un code plus simple et qu’il est implémenté sur le tableau et que la traversée du tableau est prévisible, de sorte que le processeur moderne exécute les opérations du tas binary beaucoup plus rapidement.

Cependant, étant donné que le jeu de données est suffisamment grand, d’autres tas gagneront sur le tas binary, en raison de leur complexité …

Cette question semble être un jeu de données assez grand.