Welche Algorithmen berechnen die Richtungen von Punkt A nach Punkt B auf einer Karte?

Question

Wie schlagen Kartenanbieter (wie Google oder Yahoo! Maps) Wegbeschreibungen vor?

Ich meine, sie verfügen wahrscheinlich über reale Daten in irgendeiner Form, sicherlich einschließlich Entfernungen, aber vielleicht auch Dinge wie Fahrgeschwindigkeiten, Vorhandensein von Gehwegen, Zugfahrpläne usw. Aber nehmen wir an, die Daten hätten ein einfacheres Format, z. B. einen sehr großen gerichteten Graphen mit Kantengewichten, die die Entfernungen widerspiegeln. Ich möchte in der Lage sein, schnell die Richtung von einem beliebigen Punkt zu einem anderen zu berechnen. Manchmal liegen diese Punkte nahe beieinander (innerhalb einer Stadt), manchmal weit auseinander (quer durchs Land).

Graph-Algorithmen wie der Dijkstra-Algorithmus funktionieren nicht, weil der Graph riesig ist. Glücklicherweise werden heuristische Algorithmen wie A* wahrscheinlich funktionieren. Unsere Daten sind jedoch sehr strukturiert, und vielleicht könnte eine Art von abgestuftem Ansatz funktionieren? (Speichern Sie z. B. vorberechnete Richtungen zwischen bestimmten, weit voneinander entfernten "Schlüsselpunkten" sowie einige lokale Richtungen. Dann werden die Richtungen für zwei weit entfernte Punkte lokale Richtungen zu einem Schlüsselpunkt, globale Richtungen zu einem anderen Schlüsselpunkt und dann wieder lokale Richtungen beinhalten).

Welche Algorithmen werden in der Praxis tatsächlich verwendet?

PS. Diese Frage wurde durch die Entdeckung von Macken in Online-Kartenanleitungen motiviert. Entgegen der Dreiecksungleichung denkt Google Maps manchmal, dass X-Z dauert länger und ist weiter als die Verwendung eines Zwischenpunkts wie in X-Y-Z . Aber vielleicht optimieren sie ihre Laufwege auch für einen anderen Parameter?

PPS. Hier ist ein weiterer Verstoß gegen die Dreiecksungleichheit, der (für mich) darauf schließen lässt, dass sie eine Art abgestuften Ansatz verwenden: X-Z 対 X-Y-Z . Ersterer scheint den prominenten Boulevard de Sebastopol zu nutzen, auch wenn er etwas abgelegen ist.

bearbeiten : Keines dieser Beispiele scheint mehr zu funktionieren, aber zum Zeitpunkt des ursprünglichen Beitrags funktionierten beide.

Answer 1

Dies ist eine reine Spekulation meinerseits, aber ich vermute, dass sie vielleicht eine Einflusskarten-Datenstruktur verwenden, die die gerichtete Karte überlagert, um den Suchbereich einzugrenzen. Dies würde es dem Suchalgorithmus ermöglichen, den Weg auf Hauptrouten zu lenken, wenn die gewünschte Strecke lang ist.

Angesichts der Tatsache, dass es sich um eine Google-App handelt, kann man davon ausgehen, dass ein großer Teil der Magie durch umfangreiches Caching erreicht wird :) Es würde mich nicht überraschen, wenn durch das Zwischenspeichern der 5 % der häufigsten Google Map-Routenanfragen ein großer Teil (20 %? 50 %?) der Anfragen durch einfaches Nachschlagen beantwortet werden könnte.

Answer 2

Ich habe mir dazu noch einige Gedanken gemacht:

1) Denken Sie daran, dass Karten eine physische Organisation darstellen. Speichern Sie den Breitengrad/Längengrad jedes Schnittpunkts. Über die Punkte, die in der Richtung Ihres Ziels liegen, brauchen Sie nicht viel hinauszugehen. Nur wenn Sie sich blockiert fühlen, müssen Sie darüber hinausgehen. Wenn Sie eine Überlagerung von übergeordneten Verbindungen speichern, können Sie die Suche noch weiter einschränken - normalerweise werden Sie nie eine dieser Verbindungen in einer Richtung überqueren, die von Ihrem Ziel abweicht.

2) Unterteilen Sie die Welt in eine ganze Reihe von Zonen, die durch begrenzte Konnektivität definiert sind, und definieren Sie alle Verbindungspunkte zwischen den Zonen. Finden Sie heraus, in welchen Zonen Ihre Quelle und Ihr Ziel liegen, für die Start- und Endzone die Route von Ihrem Standort zu jedem Verbindungspunkt, für die Zonen dazwischen einfach eine Karte zwischen den Verbindungspunkten. (Ich vermute, dass vieles davon bereits vorberechnet ist.)

Beachten Sie, dass Zonen kleiner als ein Ballungsgebiet sein können. Jede Stadt mit Geländemerkmalen, die sie unterteilen (z. B. ein Fluss), würde mehrere Zonen bilden.

Answer 3

Ich war sehr neugierig auf die verwendeten Heuristiken, als wir vor einiger Zeit Routen vom gleichen Startort in der Nähe von Santa Rosa zu zwei verschiedenen Campingplätzen im Yosemite-Nationalpark erhielten. Diese unterschiedlichen Ziele ergaben recht unterschiedliche Routen (über die I-580 oder die CA-12), obwohl beide Routen auf den letzten 100 Meilen (entlang der CA-120) zusammenliefen, bevor sie am Ende wieder um einige Meilen auseinandergingen. Dies war durchaus wiederholbar. Die beiden Routen lagen etwa 100 Meilen lang bis zu 50 Meilen auseinander, aber die Entfernungen/Zeiten lagen erwartungsgemäß ziemlich nahe beieinander.

Leider kann ich das nicht reproduzieren - die Algorithmen müssen sich geändert haben. Aber es hat mich neugierig auf den Algorithmus gemacht. Ich kann nur spekulieren, dass es eine Richtungsbeschneidung gab, die zufällig sehr empfindlich auf den winzigen Winkelunterschied zwischen den Zielen aus der Ferne reagierte, oder dass es verschiedene vorberechnete Segmente gab, die durch die Wahl des Endziels ausgewählt wurden.

Answer 4

Apropos GraphHopper , einem schnellen Open-Source-Routenplaner auf Basis von OpenStreetMap, habe ich ein wenig Literatur gelesen und einige Methoden implementiert. Die einfachste Lösung ist ein Dijkstra und eine einfache Verbesserung ist ein bidirektionaler Dijkstra, der ungefähr nur die Hälfte der Knoten erkundet. Mit bidirektionalem Dijkstra dauert eine Route durch ganz Deutschland bereits 1sec (für den Automodus), in C wären es wahrscheinlich nur 0,5s oder so ;)

Ich habe ein animiertes Gif einer echten Pfadsuche mit bidirektionalem Dijkstra erstellt aquí . Außerdem gibt es einige weitere Ideen zu Dijkstra schneller machen wie A*, das ein "zielorientierter Dijkstra" ist. Außerdem habe ich eine gif-Animation für sie.

Aber wie kann man das (viel) schneller machen?

Das Problem ist, dass für eine Pfadsuche alle Knoten zwischen den Orten untersucht werden müssen, und das ist sehr kostspielig, da es in Deutschland bereits mehrere Millionen davon gibt. Aber ein zusätzlicher Schmerzpunkt von Dijkstra usw. ist, dass solche Suchen viel Arbeitsspeicher verbrauchen.

Es gibt heuristische Lösungen, aber auch exakte Lösungen, die den Graphen (Straßennetz) in hierarchischen Schichten organisieren, beide haben Vor- und Nachteile und lösen hauptsächlich das Geschwindigkeits- und RAM-Problem. Ich habe einige von ihnen aufgelistet in diese Antwort .

Für GraphHopper habe ich mich für die Verwendung von Kontraktionshierarchien weil es relativ "einfach" zu implementieren ist und die Erstellung des Diagramms nicht ewig dauert. Es führt dennoch zu sehr schnellen Antwortzeiten, wie Sie in unserer Online-Instanz testen können GraphHopper Karten . z.B. vom südlichen Afrika bis zum östlichen China was eine Entfernung von 23000 km und fast 14 Tage Fahrzeit für das Auto ergibt und nur ~0,1 s auf dem Server benötigte.

Answer 5

Ich beschäftige mich seit einigen Jahren mit dem Thema Routing und habe festgestellt, dass A* einfach schnell genug ist; es besteht wirklich keine Notwendigkeit, nach Optimierungen oder komplexeren Algorithmen zu suchen. Das Routing über einen riesigen Graphen ist kein Problem.

Die Geschwindigkeit hängt jedoch davon ab, dass das gesamte Routing-Netzwerk, d. h. der gerichtete Graph aus Bögen und Knoten, die Streckenabschnitte bzw. Kreuzungen darstellen, im Speicher vorhanden ist. Der größte Zeitaufwand ist die Zeit, die für die Erstellung dieses Netzes benötigt wird. Einige grobe Zahlen auf der Grundlage eines normalen Laptops mit Windows und Routing über ganz Spanien: Zeit für die Erstellung des Netzes: 10-15 Sekunden; Zeit für die Berechnung einer Route: zu kurz, um sie zu messen.

Wichtig ist auch, dass Sie das Netz für beliebig viele Routing-Berechnungen wiederverwenden können. Wenn Ihr Algorithmus die Knoten auf irgendeine Weise markiert hat, um die beste Route aufzuzeichnen (Gesamtkosten zum aktuellen Knoten und bester Bogen dorthin) - wie es in A* der Fall ist - müssen Sie diese alten Informationen zurücksetzen oder löschen. Anstatt Hunderttausende von Knoten durchzugehen, ist es einfacher, ein Generationennummernsystem zu verwenden. Markieren Sie jeden Knoten mit der Generationsnummer seiner Daten; erhöhen Sie die Generationsnummer, wenn Sie eine neue Route berechnen; jeder Knoten mit einer älteren Generationsnummer ist veraltet und seine Informationen können ignoriert werden.