L'algorithme de Dijkstras est-il utilisé dans les systèmes modernes de recherche d'itinéraire?

10

L'algorithme de Dijkstra est-il utilisé dans les systèmes modernes de recherche d'itinéraire tels que Google Maps ou le GPS dans votre voiture? Sinon, qu'est-ce que c'est?

algorithms graphs shortest-path applied-theory chopper dessiner lion4
la source
Je suppose que vous voulez dire le composant de routage qui trouve votre chemin, une fois que le GPS, qui est principalement un Global Positionning Syatem, a déterminé où vous êtes . Encore un autre cas de queue qui remue un chien.
babou
1
Je ne peux pas donner de source pour cela, mais mon professeur actuel d'algorithmes travaille dans l'industrie et dit que est beaucoup utilisé dans la pratique, en particulier pour le GPS. Si vous utilisez la distance euclidienne comme heuristique, vous avez tendance à obtenir des améliorations par rapport à Dijstra en ignorant les chemins qui n'ont pas de sens dans la vie réelle. Vous le savez peut-être déjà, mais Dijkstra peut être décrit comme avec une heuristique . UNE∗UNE∗h(X)=0
jmite

Réponses:

8

Google Maps en 2009 a utilisé les hiérarchies de contraction - voir cet exposé technique .

Depuis lors, certaines méthodes époustouflantes ont été découvertes, capables de faire du routage à travers les pays en quelques millisecondes fractionnaires - les soi-disant «oracles de distance d'étiquetage à deux sauts». Voir ici , ou rechercher «Étiquetage du hub» ou «Chemins les plus courts pour les masses». Je pense avoir entendu Bing utiliser celui-ci. Il a également des applications comme la capacité de trouver le point d'intérêt le plus proche (par exemple la station-service la plus proche) avec une complexité indépendante du nombre de stations-service.

jkff
la source
2
Cela semble être des références utiles. Cependant, pouvez-vous a) donner des références citées et / ou b) brosser un tableau général de leur fonctionnement? En particulier, résolvent-ils exactement le problème?
Raphael