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

543

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

Ich meine, sie haben wahrscheinlich reale Daten in irgendeiner Form, sicherlich einschließlich Entfernungen, aber vielleicht auch Dinge wie Fahrgeschwindigkeit, Vorhandensein von Gehwegen, Zugfahrplänen usw. Aber nehmen wir an, die Daten hätten ein einfacheres Format, sagen wir einen sehr großen gerichteten Graphen mit Kantengewichten, die Abstände widerspiegeln. Ich möchte in der Lage sein, schnell Richtungen von einem beliebigen Punkt zum anderen zu berechnen. Manchmal liegen diese Punkte nahe beieinander (innerhalb einer Stadt), manchmal sind sie weit voneinander entfernt (Cross-Country).

Graph-Algorithmen wie der Dijkstra-Algorithmus funktionieren nicht, da der Graph enorm ist. Glücklicherweise werden heuristische Algorithmen wie A * wahrscheinlich funktionieren. Unsere Daten sind jedoch sehr strukturiert, und vielleicht könnte ein abgestufter Ansatz funktionieren? (Speichern Sie beispielsweise vorberechnete Richtungen zwischen bestimmten "Schlüssel" -Punkten weit voneinander entfernt sowie einige lokale Richtungen. Dann umfassen Richtungen für zwei weit entfernte Punkte lokale Richtungen zu einem Schlüsselpunkt, globale Richtungen zu einem anderen Schlüsselpunkt und dann lokale wieder Richtungen.)

Welche Algorithmen werden in der Praxis tatsächlich verwendet?

PS. Diese Frage wurde durch das Auffinden von Macken in Online-Mapping-Richtungen motiviert. Im Gegensatz zur Dreiecksungleichung glaubt Google Maps manchmal, dass XZ länger dauert und weiter entfernt ist als die Verwendung eines Zwischenpunkts wie in XYZ . Aber vielleicht optimieren sich ihre Laufrichtungen auch für einen anderen Parameter?

PPS. Hier ist eine weitere Verletzung der Dreiecksungleichung, die (für mich) darauf hindeutet, dass sie einen abgestuften Ansatz verwenden: XZ gegen XYZ . Ersterer scheint den prominenten Boulevard de Sebastopol zu benutzen, obwohl er etwas abgelegen ist.

Bearbeiten : Keines dieser Beispiele scheint mehr zu funktionieren, aber beide haben es zum Zeitpunkt des ursprünglichen Beitrags getan.

A. Rex
quelle
3
Übrigens, der A * -Algorithmus "ist eine Verallgemeinerung des Dijkstra-Algorithmus, der die Größe des zu untersuchenden Teilgraphen verringert, wenn zusätzliche Informationen verfügbar sind, die eine Untergrenze für die" Entfernung "zum Ziel liefern"
Mitch Wheat
Zu A *: Ja, in der Tat. Glücklicherweise sind in unserem Fall diese "zusätzlichen Informationen" beispielsweise über den geradlinigen Abstand verfügbar. Wenn ich oben "Dijkstra" sage, meine ich Vanille Dijkstra.
A. Rex
Wegbeschreibung? Keine Ahnung von irgendwo anders, aber hier (Hampshire, UK) hat Big G keine Fußgängerdaten - es leitet mich entlang der Straßen um Fußgängerzonen usw. Das einzige, wofür es gut ist, ist die Änderung der geschätzten Zeit, die für die Route benötigt wird :)
jTresidder
Es ist mir egal, ob die Anweisungen zum Fahren oder Gehen sind. Ich möchte nur wissen, wie sie funktionieren! Der Grund, warum ich dort Wanderverbindungen habe, ist, dass ich einen Weg berechnet habe, um durch Paris zu laufen und alle 66 Wallace-Brunnen zu sehen. (Die Endpunkte dieser Karten sollten Wallace-Brunnen sein.)
A. Rex
Die Prämie für diese Frage besteht darin, mehr und bessere Antworten zu fördern, insbesondere von Menschen, die bei einem der wichtigsten Anbieter arbeiten. Kommentare zu Datenstrukturen, Algorithmen, wie viel vorberechnet usw. sind willkommen.
A. Rex

Antworten:

526

Als jemand zu sprechen, der 18 Monate bei einer Kartierungsfirma gearbeitet hat, einschließlich der Arbeit am Routing-Algorithmus ... Ja, Dijkstra funktioniert mit ein paar Modifikationen:

  • Anstatt Dijkstra zu machen einmal von der Quelle zum Ziel zu machen, beginnen Sie an jedem Ende und erweitern beide Seiten, bis sie sich in der Mitte treffen. Dies eliminiert ungefähr die Hälfte der Arbeit (2 * pi * (r / 2) ^ 2 vs pi * r ^ 2).
  • Um zu vermeiden, dass Sie die Seitengassen jeder Stadt zwischen Ihrer Quelle und Ihrem Ziel erkunden, können Sie mehrere Ebenen mit Kartendaten verwenden: Eine Ebene "Autobahnen", die nur Autobahnen enthält, eine Ebene "Sekundär", die nur Nebenstraßen enthält, usw. Anschließend untersuchen Sie nur kleinere Abschnitte der detaillierteren Ebenen und erweitern sie nach Bedarf. Natürlich lässt diese Beschreibung viele Details aus, aber Sie bekommen die Idee.

Mit Änderungen in dieser Richtung können Sie sogar Cross-Country-Routing in einem sehr vernünftigen Zeitrahmen durchführen.

Nick Johnson
quelle
29
Jemand, der in der realen Welt daran gearbeitet hat, großartig! Haben Sie eine Vorstellung davon, wie viel Vorberechnung möglich ist, wie in dem Artikel über Google, der in einem anderen Kommentar erwähnt wurde?
A. Rex
10
Wir haben keine Vorverarbeitung dieser Art durchgeführt, aber es scheint sicherlich eine interessante Optimierung zu sein.
Nick Johnson
29
"Es wird nur garantiert, dass eine Lösung entsteht, nicht unbedingt die effizienteste." Das ist falsch. Solange die verwendete Heuristik zulässig ist, erzeugt der A * -Algorithmus den kostengünstigsten Pfad. Zulässig bedeutet, dass die Kosten niemals überschätzt werden, aber möglicherweise unterschätzt werden (aber schlechte Schätzungen verlangsamen den Algorithmus). Die Verwendung von Daten aus der Vorverarbeitung trägt wahrscheinlich dazu bei, eine besser zulässige Heuristik zu erstellen und damit A * schneller arbeiten zu lassen.
a1kmm
6
Bei weiterer Überlegung haben Sie völlig Recht. Sie können einen vorhandenen Algorithmus erweitern, um dies zu nutzen, indem Sie einfach den Großkreisabstand zwischen dem Zielknoten und dem Ziel zu den Kosten der zu bewertenden Kante hinzufügen. Ich bin mir eigentlich nicht sicher, ob unser Algorithmus das getan hat - aber es ist eine sehr vernünftige Optimierung.
Nick Johnson
11
A * ist im schlimmsten Fall (eine Heuristik, die besagt, dass alle Pfade gleich sind) genau gleich Djikstra.
Tordek
111

Diese Frage war in den letzten Jahren ein aktives Forschungsgebiet. Die Hauptidee ist es, eine zu tun Vorverarbeitung auf dem Graphen einmal , zu beschleunigen alle folgenden Abfragen . Mit diesen zusätzlichen Informationen können Reiserouten sehr schnell berechnet werden. Der Dijkstra-Algorithmus ist jedoch die Grundlage für alle Optimierungen.

Arachnid beschrieb die Verwendung der bidirektionalen Suche und des Kantenschneidens basierend auf hierarchischen Informationen. Diese Beschleunigungstechniken funktionieren recht gut, aber die neuesten Algorithmen übertreffen diese Techniken auf jeden Fall. Mit aktuellen Algorithmen können kürzeste Wege in einem kontinentalen Straßennetz in erheblich kürzerer Zeit als einer Millisekunde berechnet werden. Eine schnelle Implementierung des unveränderten Algorithmus von Dijkstra benötigt ca. 10 Sekunden .

Der Artikel Engineering Fast Route Planning Algorithms gibt einen Überblick über den Fortschritt der Forschung auf diesem Gebiet. Weitere Informationen finden Sie in den Referenzen dieses Dokuments.

Die schnellsten bekannten Algorithmen verwenden keine Informationen über den hierarchischen Status der Straße in den Daten, dh wenn es sich um eine Autobahn oder eine lokale Straße handelt. Stattdessen berechnen sie in einem Vorverarbeitungsschritt eine eigene Hierarchie, die optimiert wurde, um die Routenplanung zu beschleunigen. Diese Vorberechnung kann dann verwendet werden, um die Suche zu beschneiden: Weit entfernt von Start und Ziel müssen langsame Straßen während des Dijkstra-Algorithmus nicht berücksichtigt werden. Die Vorteile sind eine sehr gute Leistung und eine Korrektheitsgarantie für das Ergebnis.

Die ersten optimierten Routenplanungsalgorithmen befassten sich nur mit statischen Straßennetzen, dh eine Kante in der Grafik hat einen festen Kostenwert. Dies trifft in der Praxis nicht zu, da wir dynamische Informationen wie Staus oder fahrzeugabhängige Einschränkungen berücksichtigen möchten. Neueste Algorithmen können sich auch mit solchen Problemen befassen, aber es sind noch Probleme zu lösen, und die Forschung geht weiter.

Wenn Sie die kürzesten Pfadentfernungen benötigen, um eine Lösung für den TSP zu berechnen , sind Sie wahrscheinlich an Matrizen interessiert, die alle Entfernungen zwischen Ihren Quellen und Zielen enthalten. Zu diesem Zweck können Sie in Betracht ziehen, viele zu viele kürzeste Pfade mithilfe von Autobahnhierarchien zu berechnen . Beachten Sie, dass dies in den letzten 2 Jahren durch neuere Ansätze verbessert wurde.

SebastianK
quelle
1
In der Tat aufschlussreich. Was sind die neueren Ansätze, die Sie erwähnen?
Tomas Pajonk
1
Insbesondere Kontraktionshierarchien. Mehr dazu finden Sie hier: algo2.iti.kit.edu/routeplanning.php . Es gibt auch ein Google Tech-Gespräch darüber: youtube.com/watch?v=-0ErpE8tQbw
SebastianK
19

Wenn wir uns nur mit den Verstößen gegen die Dreiecksungleichheit befassen, ist der gesunde Menschenverstand hoffentlich der zusätzliche Faktor, für den sie optimieren. Sie wollen nicht unbedingt den kürzesten oder schnellsten Weg, da dies zu Chaos und Zerstörung führen kann . Wenn Sie möchten, dass Ihre Wegbeschreibung die Hauptstrecken bevorzugt, die lkw-freundlich sind und damit fertig werden, dass jeder Fahrer, der einem Navigationsgerät folgt, diese herunterschickt, verwerfen Sie schnell die Dreiecksungleichung [1].

Wenn Y eine schmale Wohnstraße zwischen X und Z ist, möchten Sie die Verknüpfung wahrscheinlich nur über Y verwenden, wenn der Benutzer explizit nach XYZ fragt. Wenn sie nach XZ fragen, sollten sie auf Hauptstraßen bleiben, auch wenn es etwas weiter ist und etwas länger dauert. Es ist ähnlich wie Braess 'Paradoxon Wenn jeder versucht, den kürzesten und schnellsten Weg zu nehmen, bedeutet die daraus resultierende Überlastung, dass es für niemanden mehr der schnellste Weg ist. Von hier aus wandern wir von der Graphentheorie zur Spieltheorie.

[1] Tatsächlich stirbt jede Hoffnung, dass die erzeugten Entfernungen eine Entfernungsfunktion im mathematischen Sinne sind, wenn Sie Einbahnstraßen zulassen und die Symmetrieanforderung verlieren. Wenn Sie auch die Ungleichung des Dreiecks verlieren, reiben Sie nur Salz in die Wunde.

Stevemegson
quelle
14

Hier sind die weltweit schnellsten Routing-Algorithmen, die verglichen und auf ihre Richtigkeit geprüft wurden:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

Hier ist ein Google Tech-Vortrag zu diesem Thema:

http://www.youtube.com/watch?v=-0ErpE8tQbw

Hier ist eine Implementierung des Algorithmus für Autobahnhierarchien, wie er von Schultes diskutiert wird (derzeit nur in Berlin, ich schreibe die Schnittstelle und eine mobile Version wird ebenfalls entwickelt):

http://tom.mapsforge.org/

Eikes
quelle
9

Ich habe noch nie an Google, Microsoft oder Yahoo Maps gearbeitet, daher kann ich Ihnen nicht sagen, wie sie funktionieren.

Ich habe jedoch ein kundenspezifisches System zur Optimierung der Lieferkette für ein Energieunternehmen entwickelt, das eine Planungs- und Routing-Anwendung für die LKW-Flotte enthielt. Unsere Kriterien für das Routing waren jedoch weitaus unternehmensspezifischer als bei Bau- oder Verkehrsverlangsamungen oder Fahrbahnsperrungen.

Wir verwendeten eine Technik namens ACO (Ant Colony Optimization), um LKWs zu planen und zu routen. Diese Technik ist eine KI-Technik, die auf das Problem des Handlungsreisenden angewendet wurde, um Routingprobleme zu lösen. Der Trick bei ACO besteht darin, eine Fehlerberechnung basierend auf bekannten Fakten des Routings zu erstellen, damit das Diagrammlösungsmodell weiß, wann es beendet werden muss (wann der Fehler klein genug ist).

Sie können ACO oder TSP googeln, um mehr über diese Technik zu erfahren. Ich habe jedoch keines der Open-Source-KI-Tools dafür verwendet und kann daher keines vorschlagen (obwohl ich gehört habe, dass SWARM ziemlich umfassend ist).

Rechnung
quelle
4
Routing! = TL. In TL kennen Sie alle Entfernungen und optimieren die Stoppreihenfolge - dies ist kein Punkt-zu-Punkt-Algo.
Karussell
8

Graph-Algorithmen wie der Dijkstra-Algorithmus funktionieren nicht, da der Graph enorm ist.

Dieses Argument gilt nicht unbedingt, da Dijkstra normalerweise nicht das gesamte Diagramm betrachtet, sondern nur eine sehr kleine Teilmenge (je besser das Diagramm miteinander verbunden ist, desto kleiner ist diese Teilmenge).

Dijkstra kann für gut erzogene Diagramme tatsächlich eine ziemlich gute Leistung erbringen. Andererseits ist A * bei sorgfältiger Parametrisierung immer genauso gut oder besser. Haben Sie bereits versucht, wie sich dies auf Ihre Daten auswirken würde?

Trotzdem wäre ich auch sehr interessiert, von den Erfahrungen anderer Leute zu hören. Besonders interessant sind natürlich prominente Beispiele wie die Suche von Google Map. Ich könnte mir so etwas wie eine Heuristik für den nächsten Nachbarn vorstellen.

Konrad Rudolph
quelle
2
Angenommen, Sie versuchen, Richtungen von Punkt A nach B zu finden, deren optimale Entfernung d ist. Der Dijkstra-Algorithmus untersucht zumindest alle Punkte in einer Entfernung von höchstens d von A. Wenn A San Francisco und B Boston ist, bedeutet dies, dass er den größten Teil der USA untersucht. N'est-ce pas?
A. Rex
2
Ja, so ist es. Was ich erreichen wollte, ist, dass stattdessen A * verwendet werden kann und dass es immer eine optimale Lösung findet (obwohl es eine Heuristik verwendet)!
Konrad Rudolph
Ja natürlich. Nachdem ich meinen ursprünglichen Beitrag geschrieben hatte, dachte ich über das Wort "Heuristik" nach, das ich verwendet hatte. Es ist hier etwas ungenau, weil es eine optimale Lösung findet.
A. Rex
2
Nun, ist der Punkt , dass A * verwendet eine heuristische (im Gegensatz zu sein eins) den nächsten Schritt zu bestimmen. Diese eine Entscheidung kann tatsächlich suboptimal sein. Es wirkt sich jedoch nur auf die Laufzeit aus, nicht auf das Ergebnis, da nur bestimmt wird, wie viel besser als Dijstra vermutet wird.
Konrad Rudolph
8

Der aktuelle Stand der Technik in Bezug auf Abfragezeiten für statische Straßennetze ist der von Abraham et al. Vorgeschlagene Hub-Markierungsalgorithmus. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . Eine ausführliche und hervorragend geschriebene Übersicht über das Gebiet wurde kürzlich als technischer Microsoft-Bericht http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf veröffentlicht .

Die Kurzversion ist ...

Der Hub-Kennzeichnungsalgorithmus bietet die schnellsten Abfragen für statische Straßennetze, erfordert jedoch eine große Menge an RAM (18 GiB).

Das Transitknoten-Routing ist etwas langsamer, benötigt jedoch nur etwa 2 GiB Speicher und hat eine schnellere Vorverarbeitungszeit.

Kontraktionshierarchien bieten einen guten Kompromiss zwischen schnellen Vorverarbeitungszeiten, geringem Platzbedarf (0,4 GiB) und schnellen Abfragezeiten.

Kein Algorithmus ist vollständig dominiert ...

Dieser Google Tech Talk von Peter Sanders könnte von Interesse sein

https://www.youtube.com/watch?v=-0ErpE8tQbw

Auch dieser Vortrag von Andrew Goldberg

https://www.youtube.com/watch?v=WPrkc78XLhw

Eine Open-Source-Implementierung von Kontraktionshierarchien ist auf der Website der Peter Sanders-Forschungsgruppe am KIT verfügbar. http://algo2.iti.kit.edu/english/routeplanning.php

Auch ein leicht zugänglicher Blog-Beitrag von Microsoft über die Verwendung des CRP-Algorithmus ... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/

Barnaby Hussey-Yeo
quelle
7

Ich bin ein wenig überrascht, den hier erwähnten Algorithmus von Floyd Warshall nicht zu sehen . Dieser Algorithmus ist dem von Dijkstra sehr ähnlich. Es hat auch eine sehr schöne Funktion, mit der Sie rechnen können, solange Sie weitere Zwischenscheitelpunkte zulassen möchten. So findet es natürlich ziemlich schnell die Routen, die Autobahnen oder Autobahnen benutzen.

dennisjtaylor
quelle
6

Ich habe das ziemlich oft gemacht und verschiedene Methoden ausprobiert. Abhängig von der Größe (geografisch) der Karte sollten Sie die Haversine-Funktion als Heuristik verwenden.

Die beste Lösung, die ich gemacht habe, war die Verwendung von A * mit einem geraden Abstand als heuristische Funktion. Dann benötigen Sie jedoch eine Art Koordinaten für jeden Punkt (Schnittpunkt oder Scheitelpunkt) auf der Karte. Sie können auch verschiedene Gewichtungen für die heuristische Funktion ausprobieren, d. H.

f(n) = k*h(n) + g(n)

wobei k eine Konstante ist, die größer als 0 ist.

Pål GD
quelle
4

Wahrscheinlich ähnlich der Antwort auf vorberechneten Routen zwischen Hauptstandorten und Karten mit Ebenen, aber ich verstehe, dass Sie in Spielen zur Beschleunigung von A * eine Karte haben, die für die Makronavigation sehr grob ist, und eine feinkörnige Karte für Navigation zur Grenze der Makrorichtungen. Sie müssen also zwei kleine Pfade berechnen, und daher ist Ihr Suchraum viel kleiner als nur ein einzelner Pfad zum Ziel. Und wenn Sie dies häufig tun, müssen Sie viele dieser Daten vorberechnet haben, sodass zumindest ein Teil der Suche eine Suche nach vorberechneten Daten und keine Suche nach einem Pfad ist.

Marcin
quelle
3

Dies ist reine Spekulation meinerseits, aber ich nehme an, dass sie eine Einflusskartendatenstruktur verwenden, die die gerichtete Karte überlagert, um die Suchdomäne einzugrenzen. Dies würde es dem Suchalgorithmus ermöglichen, den Pfad zu Hauptrouten zu lenken, wenn die gewünschte Reise lang ist.

Da es sich um eine Google-App handelt, ist es auch vernünftig anzunehmen, dass ein Großteil der Magie über umfangreiches Caching erfolgt. :) Es würde mich nicht wundern, wenn beim Zwischenspeichern der 5% häufigsten Google Map-Routenanfragen ein großer Teil (20%? 50%?) Der Anfragen durch eine einfache Suche beantwortet werden könnte.

Parappa
quelle
Haben Sie eine gute Referenz für "eine Einflusskartendatenstruktur"? Vielen Dank!
A. Rex
3

Ich hatte noch einige Gedanken dazu:

1) Denken Sie daran, dass Karten eine physische Organisation darstellen. Speichern Sie den Breiten- / Längengrad jeder Kreuzung. Sie müssen nicht viel über die Punkte hinaus überprüfen, die in Richtung Ihres Ziels liegen. Nur wenn Sie blockiert sind, müssen Sie darüber hinausgehen. Wenn Sie eine Überlagerung überlegener Verbindungen speichern, können Sie diese noch weiter einschränken. Normalerweise werden Sie eine dieser Verbindungen nie auf eine Weise überqueren, die von Ihrem endgültigen Ziel abweicht.

2) Teilen Sie die Welt in eine ganze Reihe von Zonen auf, die durch eingeschränkte Konnektivität definiert sind, und definieren Sie alle Konnektivitätspunkte zwischen den Zonen. Finden Sie heraus, in welchen Zonen sich Ihre Quelle und Ihr Ziel befinden, für die Start- und Endzonenroute von Ihrem Standort zu jedem Verbindungspunkt, für die Zonen zwischen einfachem Zuordnen zwischen Verbindungspunkten. (Ich vermute, dass ein Großteil davon bereits vorberechnet ist.)

Beachten Sie, dass Zonen kleiner als ein Ballungsraum sein können. Jede Stadt mit Geländemerkmalen, die sie aufteilen (z. B. ein Fluss), besteht aus mehreren Zonen.

Loren Pechtel
quelle
3

Ich war sehr neugierig auf die verwendeten Heuristiken, als wir vor einiger Zeit Routen vom selben Startort in der Nähe von Santa Rosa zu zwei verschiedenen Campingplätzen im Yosemite-Nationalpark bekamen. Diese unterschiedlichen Ziele ergaben ganz unterschiedliche Routen (über die I-580 oder CA-12), obwohl beide Routen auf den letzten 100 Meilen (entlang der CA-120) konvergierten, bevor sie am Ende wieder um einige Meilen auseinander gingen. Das war ziemlich wiederholbar. Die beiden Routen waren ungefähr 100 Meilen voneinander entfernt, aber die Entfernungen / Zeiten waren ziemlich nahe beieinander, wie Sie es erwarten würden.

Leider kann ich das nicht reproduzieren - die Algorithmen müssen sich geändert haben. Aber ich war neugierig auf den Algorithmus. Ich kann nur spekulieren, dass es einen Richtungsschnitt gab, der äußerst empfindlich auf den winzigen Winkelunterschied zwischen den Zielen aus der Ferne reagierte, oder dass verschiedene vorberechnete Segmente durch die Wahl des endgültigen Ziels ausgewählt wurden.

Zhahai
quelle
3

Apropos GraphHopper , ein schneller Open Source-Routenplaner, der auf OpenStreetMap basiert. Ich habe ein bisschen Literatur gelesen und einige Methoden implementiert. Die einfachste Lösung ist eine Dijkstra und eine einfache Verbesserung ist eine bidirektionale Dijkstra, die ungefähr nur die Hälfte der Knoten untersucht. Mit der bidirektionalen Dijkstra dauert eine Route durch ganz Deutschland bereits 1 Sekunde (für den Automodus), in C wären es wahrscheinlich nur 0,5 Sekunden oder so;)

Ich habe eine Animation eines echten Wegsuche mit bidirektionaler Dijkstra erstellt hier . Es gibt auch einige weitere Ideen, um Dijkstra schneller zu machen, wie A *, eine "zielorientierte Dijkstra". Außerdem habe ich eine GIF-Animation dafür erstellt.

Aber wie geht das (viel) schneller?

Das Problem ist, dass für eine Pfadsuche alle Knoten zwischen den Standorten erkundet werden müssen und dies sehr kostspielig ist, da es bereits in Deutschland mehrere Millionen davon gibt. Ein zusätzlicher Schmerzpunkt von Dijkstra usw. ist, dass solche Suchen viel RAM verbrauchen.

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

Für GraphHopper habe ich mich für die Verwendung von Kontraktionshierarchien entschieden, da die Implementierung relativ einfach ist und die Erstellung des Diagramms nicht lange dauert. Dies führt immer noch zu sehr schnellen Antwortzeiten, wie Sie sie in unserer Online-Instanz GraphHopper Maps testen können . ZB von Südafrika nach Ostchina, was zu einer Entfernung von 23000 km und einer Fahrzeit von fast 14 Tagen für das Auto führt und nur ~ 0,1 Sekunden auf dem Server benötigt.

Karussell
quelle
Bidirektionale Dijkstra, die Orientierungspunkte verwendet, um eine zielgerichtete Suche durchzuführen, ist effizienter als Bidirektionale Dijkstra allein. Siehe www14.informatik.tu-muenchen.de/lehre/2010SS/sarntal/… Dieses Dokument ist jedoch nicht detailliert genug, um die potenzielle Funktion zu berechnen, die etwas schwierig ist, oder um die Orientierungspunkte auszuwählen.
Paul Chernoch
2

Ich habe einige Jahre am Routing gearbeitet, wobei die Aktivitäten meiner Kunden in jüngster Zeit zu zahlreichen Aktivitäten geführt haben, und ich habe festgestellt, dass A * 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, ob sich das gesamte Routing-Netzwerk im Speicher befindet, womit ich den gerichteten Graphen von Bögen und Knoten meine, die Routensegmente bzw. Kreuzungen darstellen. Der Hauptzeitaufwand ist die Zeit, die zum Erstellen dieses Netzwerks benötigt wird. Einige grobe Zahlen, die auf einem normalen Laptop mit Windows und Routing in ganz Spanien basieren: Zeitaufwand für die Erstellung des Netzwerks: 10-15 Sekunden; Zeitaufwand für die Berechnung einer Route: zu kurz zum Messen.

Die andere wichtige Sache ist, das Netzwerk für beliebig viele Routing-Berechnungen wiederverwenden zu können. Wenn Ihr Algorithmus die Knoten auf irgendeine Weise markiert hat, um die beste Route aufzuzeichnen (Gesamtkosten zum aktuellen Knoten und bester Bogen dazu) - wie in A * -, müssen Sie diese alten Informationen zurücksetzen oder löschen. Anstatt Hunderttausende von Knoten zu durchlaufen, ist es einfacher, ein Generationsnummernsystem zu verwenden. Markieren Sie jeden Knoten mit der Generierungsnummer seiner Daten. Erhöhen Sie die Generierungsnummer, wenn Sie eine neue Route berechnen. Jeder Knoten mit einer älteren Generationsnummer ist veraltet und seine Informationen können ignoriert werden.

Graham Asher
quelle
1

Ich sehe, was mit den Karten im OP los ist:

Sehen Sie sich die Route mit dem angegebenen Zwischenpunkt an: Die Route verläuft aufgrund der nicht geraden Straße leicht rückwärts.

Wenn ihr Algorithmus nicht zurückverfolgt wird, wird die kürzere Route nicht angezeigt.

Loren Pechtel
quelle
Interessante Idee. Ich habe dem OP einen weiteren Verstoß in meinem PPS hinzugefügt. Bitte schauen Sie nach, ob Sie dort eine Erklärung finden.
A. Rex
Zoom WAY nach unten auf Punkt A - ein Klick von max. Beachten Sie, wie die Dreipunktroute nach Westen, Süden und Osten verläuft. Ich denke, wir sehen uns einen Algorithmus an, der nicht gerne zurückverfolgt wird, es sei denn, es war notwendig, einen Chokepoint zu durchlaufen.
Loren Pechtel
Ändern Sie in meinem PPS-Beispiel die Startadresse in "10 Avenue de Flandre, 75019 Paris". Dies entfernt den kleinen Backtrack, von dem Sie sprechen, aber das Problem ist immer noch da. Ich denke, das Hauptproblem ist, dass es wirklich auf diesem Haupt-Boulevard bleiben will ...
A. Rex
1
Ich denke, ich habe es in diesem Fall gefunden: Machen Sie diese mit dem Auto und die Zeiten machen Sinn. Wahrscheinlich sieht es die große Straße als schneller an und die Wanderroute drosselt sie nicht.
Loren Pechtel
1
PS: Das anfängliche Problem macht auch nach diesem Standard Sinn, es ist möglicherweise nicht der Backtrack, der es verursacht hat.
Loren Pechtel
0

Ein All-Pair-Algorithmus für den kürzesten Pfad berechnet die kürzesten Pfade zwischen allen Scheitelpunkten in einem Diagramm. Auf diese Weise können Pfade vorberechnet werden, anstatt dass jedes Mal ein Pfad berechnet werden muss, wenn jemand den kürzesten Pfad zwischen einer Quelle und einem Ziel finden möchte. Der Floyd-Warshall-Algorithmus ist ein All-Pair-Algorithmus für den kürzesten Weg.

J. Michael Wuerth
quelle
-4

Karten berücksichtigen niemals die gesamte Karte. Meine Vermutung ist: 1. Je nach Ihrem Standort laden sie einen Ort und die Sehenswürdigkeiten auf diesen Ort. 2. Wenn Sie das Ziel suchen, laden sie den anderen Teil der Karte, erstellen aus zwei Stellen ein Diagramm und wenden dann die Algorithmen für den kürzesten Pfad an.

Es gibt auch eine wichtige Technik Dynamische Programmierung, von der ich vermute, dass sie bei der Berechnung kürzester Wege verwendet wird. Darauf können Sie auch verweisen.

Yogesh Kumar
quelle