Wird der Dijkstras-Algorithmus in modernen Routenfindungssystemen verwendet?

10

Wird der Dijkstra-Algorithmus in modernen Routenfindungssystemen wie Google Maps oder dem Navigationssystem in Ihrem Auto verwendet? Wenn nicht, was dann?

algorithms graphs shortest-path applied-theory Chopper Draw Lion4
quelle
Ich denke, Sie meinen die Routing-Komponente, die Ihren Weg findet, sobald das GPS, das in erster Linie ein Global Positionning Syatem ist, bestimmt hat, wo Sie sich befinden . Noch ein Fall von einem Schwanz, der mit einem Hund wedelt.
Babou
1
Ich kann keine Quelle dafür angeben, aber mein aktueller Dozent für Algorithmen arbeitet in der Industrie und sagt, dass in der Praxis häufig verwendet wird, insbesondere für GPS. Wenn Sie Euklidische Distanz als Heuristik verwenden, erhalten Sie Verbesserungen gegenüber Dijstra, indem Sie Pfade ignorieren, die im wirklichen Leben unsinnig sind. Sie wissen es vielleicht schon, aber Dijkstra kann als A ∗ mit heuristischer h ( x ) = 0 beschrieben werden . EIN∗EIN∗h(x)=0
Jmite

Antworten:

8

Google Maps verwendete 2009 Kontraktionshierarchien - siehe diesen technischen Vortrag .

Seitdem wurden einige umwerfende Methoden entdeckt, mit denen Cross-Country-Routing in Bruchteilen von Millisekunden durchgeführt werden kann - die sogenannten "Two-Hop-Labeling-Distance-Orakel". Sehen Sie hier oder suchen Sie nach "Hub-Kennzeichnung" oder "Kürzeste Wege für die Massen". Ich glaube, ich habe gehört, dass Bing diesen benutzt. Es hat auch Anwendungen wie die Fähigkeit, den nächstgelegenen Punkt von Interesse (z. B. die nächste Tankstelle) mit einer Komplexität zu finden, die von der Anzahl der Tankstellen unabhängig ist.

jkff
quelle
2
Dies scheinen nützliche Referenzen zu sein. Können Sie jedoch a) zitierfähige Referenzen angeben und / oder b) ein umfassendes Bild davon zeichnen, wie diese funktionieren? Lösen sie insbesondere das Problem genau?
Raphael