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

Ich habe noch nie mit 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 Anwendung zur Planung und Routenplanung für die LKW-Flotte umfasste. Unsere Kriterien für die Routenplanung waren jedoch weitaus geschäftsspezifischer als die Frage, wo es Baustellen, Verkehrsbehinderungen oder Fahrbahnsperrungen gibt.

Wir haben eine Technik namens ACO (Ameisenkolonie-Optimierung) zur Planung und Routenplanung von Lkw eingesetzt. Dabei handelt es sich um eine KI-Technik, die zur Lösung von Routenplanungsproblemen auf das Travelling-Salesman-Problem angewendet wurde. Der Trick bei ACO besteht darin, eine Fehlerberechnung auf der Grundlage bekannter Fakten der Routenplanung zu erstellen, damit das Modell zur Lösung des Graphen weiß, wann es aufhören muss (wenn 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, kann also keines empfehlen (obwohl ich gehört habe, dass SWARM ziemlich umfassend ist).

Answer 2

Graph-Algorithmen wie der Dijkstra-Algorithmus funktionieren nicht, weil der Graph riesig ist.

Dieses Argument ist nicht unbedingt stichhaltig, da Dijkstra in der Regel nicht den gesamten Graphen betrachtet, sondern nur eine sehr kleine Teilmenge (je besser der Graph miteinander verbunden ist, desto kleiner ist diese Teilmenge).

Dijkstra kann bei gut funktionierenden Graphen sogar recht gut funktionieren. Andererseits wird A* bei sorgfältiger Parametrisierung immer genauso gut oder sogar besser abschneiden. Haben Sie schon ausprobiert, wie es bei Ihren Daten funktionieren würde?

Ich würde mich aber auch sehr für die Erfahrungen anderer interessieren. Natürlich sind prominente Beispiele wie die Google Map-Suche besonders interessant. Ich könnte mir so etwas wie eine gerichtete Nearest Neighbour Heuristik vorstellen.

Answer 3

Ich bin ein wenig überrascht, dass ich nicht sehe Der Algorithmus von Floyd Warshall hier erwähnt. Dieser Algorithmus funktioniert sehr ähnlich wie der von Dijkstra. Er hat auch eine sehr nette Eigenschaft, nämlich die, dass er es erlaubt, so lange zu rechnen, wie man möchte, und dabei mehr Zwischenpunkte zuzulassen. So findet er natürlich die Routen, die Autobahnen oder Schnellstraßen benutzen, ziemlich schnell.

Answer 4

Ich habe das schon sehr oft gemacht und dabei verschiedene Methoden ausprobiert. Je nach (geografischer) Größe der Karte können Sie die Haversinus-Funktion als Heuristik verwenden.

Die beste Lösung, die ich gefunden habe, war die Verwendung von A* mit einem geraden Abstand als heuristische Funktion. Aber dann braucht man eine Art von Koordinaten für jeden Punkt (Schnittpunkt oder Scheitelpunkt) auf der Karte. Sie können auch verschiedene Gewichtungen für die heuristische Funktion ausprobieren, z. B.

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

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

Answer 5

Wahrscheinlich ähnelt dies der Antwort auf die Frage nach den vorberechneten Routen zwischen wichtigen Orten und den übereinanderliegenden Karten, aber ich habe es so verstanden, dass man in Spielen, um A* zu beschleunigen, eine sehr grobe Karte für die Makronavigation und eine feinkörnige Karte für die Navigation an der Grenze der Makrorichtungen hat. Man hat also 2 kleine Pfade zu berechnen, und damit ist der Suchraum viel kleiner als bei einem einzigen Pfad zum Ziel. Und wenn Sie dies häufig tun, haben Sie viele dieser Daten bereits vorberechnet, so dass zumindest ein Teil der Suche eine Suche nach vorberechneten Daten ist, und nicht eine Suche nach einem Pfad.