Map Routing hat mich schon immer fasziniert, aber ich habe noch nie eine gute Einführung (oder gar ein Tutorial für Fortgeschrittene!) dazu gefunden. Hat jemand irgendwelche Hinweise, Tipps, etc?
Aktualisierung: Ich suche vor allem nach Hinweisen darauf, wie ein Kartensystem implementiert ist (Datenstrukturen, Algorithmen usw.).
Ich habe noch kein gutes Tutorial zum Thema Routing gefunden, aber es gibt jede Menge Code zu lesen:
Es gibt GPL-Routing-Anwendungen, die Openstreetmap-Daten verwenden, z. B. Gosmore das unter Windows (+ Mobile) und Linux funktioniert. Es gibt eine Reihe interessanter [Anwendungen, die die gleichen Daten verwenden, aber gosmore hat einige coole Anwendungen z. B. Schnittstelle zu Websites .
Das größte Problem beim Routing sind schlechte Daten, und man bekommt nie genug Daten. Wenn Sie es also versuchen wollen, halten Sie Ihren Test sehr lokal, damit Sie die Daten besser kontrollieren können.
Stellen Sie sich vor, Sie lassen einen Stein in einen Teich fallen und beobachten das Plätschern. Die Routen würden den Teich darstellen und der Stein Ihre Ausgangsposition.
Natürlich müsste der Algorithmus mit zunehmender Entfernung n einen gewissen Anteil von n^2 Pfaden suchen. Man nimmt die Ausgangsposition und prüft alle verfügbaren Pfade von diesem Punkt aus. Dann wird rekursiv nach den Punkten am Ende dieser Pfade gesucht und so weiter.
Sie können die Leistung steigern, indem Sie einen Weg nicht doppelt zurücklegen, die Routen an einem Punkt nicht erneut überprüfen, wenn dieser bereits zurückgelegt wurde, und indem Sie Wege aufgeben, die zu lange dauern.
Eine andere Möglichkeit ist die Verwendung des Ameisenpheromon-Ansatzes, bei dem die Ameisen von einem Startpunkt aus nach dem Zufallsprinzip krabbeln und eine Duftspur hinterlassen, die sich aufbaut, je mehr Ameisen einen bestimmten Weg überqueren. Wenn man (genügend) Ameisen sowohl vom Start- als auch vom Endpunkt aus losschickt, wird der Weg mit dem stärksten Duft schließlich der kürzeste sein. Das liegt daran, dass der kürzeste Weg in einer bestimmten Zeitspanne öfter besucht wurde, da die Ameisen mit gleichmäßigem Tempo laufen.
EDIT @ Spikie
Zur weiteren Erläuterung, wie der Teichalgorithmus zu implementieren ist, werden mögliche benötigte Datenstrukturen hervorgehoben:
Sie müssen die Karte als Netzwerk speichern. Dies ist einfach ein Satz von nodes y edges zwischen ihnen. Eine Reihe von nodes bilden eine route . Eine Kante verbindet zwei Knoten (möglicherweise beide derselbe Knoten) und hat einen zugehörigen cost wie zum Beispiel distance o time um die Kante zu überqueren. Eine Kante kann entweder bidirektional oder unidirektional sein. Wahrscheinlich ist es am einfachsten, nur unidirektionale Kanten zu haben und eine doppelte Kante für den Verkehr in beide Richtungen zwischen den Knoten (d.h. eine Kante von A nach B und eine andere für B nach A).
Stellen Sie sich zum Beispiel drei Bahnhöfe vor, die in einem gleichseitigen Dreieck angeordnet sind und nach oben zeigen. Drei weitere Bahnhöfe befinden sich jeweils auf halbem Weg zwischen ihnen. Die Kanten verbinden alle benachbarten Bahnhöfe miteinander, so dass das endgültige Diagramm ein auf den Kopf gestelltes Dreieck innerhalb des größeren Dreiecks zeigt.
Beschriften Sie die Knoten von unten links, von links nach rechts und nach oben mit A,B,C,D,E,F (F oben).
Angenommen, die Kanten können in beide Richtungen durchlaufen werden. Jede Kante hat einen Preis von 1 km.
Ok, wir wollen also von der unteren linken Seite A zur oberen Station F. Es gibt viele mögliche Routen, einschließlich solcher, die in sich selbst zurückgehen, z. B. ABCEBDEF.
Wir haben eine Routine zu sagen, NextNode , die eine node und eine cost und ruft sich selbst für jeden Knoten an, zu dem er reisen kann.
Wenn wir diese Routine laufen lassen, wird sie schließlich alle Routen entdecken, auch solche, die potenziell unendlich lang sind (z. B. ABABABAB usw.). Wir verhindern dies, indem wir gegen die cost . Jedes Mal, wenn wir einen Knoten besuchen, der noch nicht besucht wurde, geben wir sowohl die Kosten als auch den Knoten, von dem wir gekommen sind, für diesen Knoten an. Wenn ein Knoten bereits besucht wurde, überprüfen wir die bestehenden Kosten und wenn wir billiger sind, aktualisieren wir den Knoten und fahren fort (Rekursion). Wenn wir teurer sind, lassen wir den Knoten aus. Wenn alle Knoten übersprungen wurden, verlassen wir die Routine.
Wenn wir unseren Zielknoten treffen, verlassen wir die Routine ebenfalls.
Auf diese Weise werden alle in Frage kommenden Strecken geprüft, aber nur die mit den niedrigsten Kosten. Am Ende des Prozesses hat jeder Knoten die niedrigsten Kosten, um zu diesem Knoten zu gelangen, einschließlich unseres Zielknotens.
Um die Route zu ermitteln, arbeiten wir von unserem Zielknoten aus rückwärts. Da wir den Knoten, von dem wir gekommen sind, zusammen mit den Kosten gespeichert haben, hüpfen wir einfach rückwärts, um die Route zu erstellen. Für unser Beispiel würden wir am Ende etwas wie folgt erhalten:
Knoten A - (Gesamt-)Kosten 0 - Von Knoten Keine
Knotenpunkt B - Kosten 1 - Von Knotenpunkt A
Knotenpunkt C - Kosten 2 - Von Knotenpunkt B
Knoten D - Kosten 1 - Von Knoten A
Knoten E - Kosten 2 - von Knoten D / Kosten 2 - von Knoten B (dies ist eine Ausnahme, da es gleiche Kosten gibt)
Knoten F - Kosten 2 - Von Knoten D
Der kürzeste Weg ist also ADF.
Eine weitere Überlegung betrifft die Kosten der einzelnen Durchläufe, würde aber die für die Berechnung erforderliche Zeit und Rechenleistung erhöhen.
例 Laut GoogleMaps gibt es 3 Möglichkeiten, um von Punkt A nach B zu gelangen (wo ich wohne). Garmin-Geräte bieten jeden dieser 3 Wege in der Quickest Routenberechnung. Nachdem ich jede dieser Strecken viele Male durchfahren und den Durchschnitt gebildet habe (natürlich gibt es Fehler, die von der Tageszeit, der Menge an Koffein usw. abhängen), denke ich, dass die Algorithmen die Anzahl der Kurven auf der Straße berücksichtigen könnten, um ein hohes Maß an Genauigkeit zu erreichen, z.B.. eine gerade Straße von 1 Meile ist schneller als eine Straße von 1 Meile mit scharfen Kurven . Das ist zwar kein praktischer Vorschlag, aber einer, mit dem ich die Ergebnisse meines täglichen Pendelns verbessern kann.
Nach meiner Erfahrung in diesem Bereich erfüllt A* die Aufgabe sehr gut. Er ist (wie oben erwähnt) schneller als der Dijkstra-Algorithmus, aber immer noch einfach genug für einen normal kompetenten Programmierer, um ihn zu implementieren und zu verstehen.
Der Aufbau des Streckennetzes ist der schwierigste Teil, kann aber in eine Reihe einfacher Schritte aufgeteilt werden: Erfassen Sie alle Straßen; sortieren Sie die Punkte; bilden Sie Gruppen identischer Punkte auf verschiedenen Straßen zu Kreuzungen (Knoten); fügen Sie Bögen in beide Richtungen hinzu, wenn Knoten miteinander verbunden sind (oder nur in eine Richtung bei einer Einbahnstraße).
Der A*-Algorithmus selbst ist gut dokumentiert auf Wikipedia . Der wichtigste Punkt, den es zu optimieren gilt, ist die Auswahl des besten Knotens aus der offenen Liste, wofür Sie eine leistungsfähige Prioritätswarteschlange benötigen. Wenn Sie C++ verwenden, können Sie den STL priority_queue Adapter benutzen.
Es ist ganz einfach, den Algorithmus so anzupassen, dass er über verschiedene Teile des Netzes (z. B. Fußgänger, Auto, öffentliche Verkehrsmittel usw.) nach bevorzugter Geschwindigkeit, Entfernung oder anderen Kriterien leitet. Dazu schreiben Sie Filter, um zu steuern, welche Routensegmente beim Aufbau des Netzes zur Verfügung stehen und welche Gewichtung den einzelnen Segmenten zugewiesen wird.
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
