Schnellere Alternativen zu Dijkstra-Algorithmus für GPS-System

Question

Ich bin ein echter Geschwindigkeitsfreak, wenn es um Algorithmen geht, und in den Plugins, die ich für ein Spiel gemacht habe.

Die Geschwindigkeit ist .. ein bisschen .. nicht befriedigend. Vor allem während man mit dem Auto herumfährt und man nicht seinem Weg folgt, muss der Weg neu berechnet werden. Und es braucht etwas Zeit. So stapelt das In-Game-GPS viele "falsche" Signale (und stapelt die Signale auf bedeutet mehr Berechnungen danach, für jeden falschen Weg) weil ich ein schnelles, Live-GPS-System haben möchte, das ständig aktualisiert.

änderte ich den alten Algorithmus (einige einfache dijkstra Implementierung) boost :: Dijkstra einen Weg vom Knoten A zum Knoten B um

(Gesamtknotenliste zu berechnen ist ~ 15k Knoten mit ~ 40k-Verbindungen, für neugierige Leute hier ist die Karte: http://gz.pxf24.pl/downloads/prv2.jpg (12 MB), Kanten in den roten Linien sind die Knoten),

, aber es hat nicht wirklich an Geschwindigkeit zu erhöhen. (Zumindest nicht merklich, vielleicht 50 ms).

Die Informationen, die in dem Knoten-Array gespeichert sind:

The ID of the Node, 
The position of the node, 
All the connections to the node (and which way it is connected to the other nodes, TO, FROM, or BOTH) 
Distance to the connected nodes. 

Ich bin neugierig, ob jemand ein paar schnelleren Alternativen in C/C++ kennt? Irgendwelche Vorschläge (+ Codebeispiele?) Werden geschätzt!

---

Wenn jemand an dem Projekt interessiert ist, hier ist es (Quelle + Binärdateien):

https://gpb.googlecode.com/files/RouteConnector_177.zip

In diesem Video können Sie sehen, was das GPS-System ist wie:

http://www.youtu.be/xsIhArstyU8

wie Sie sehen können, die rote Route wird langsam aktualisiert (gut, für uns - Gamer - es ist langsam).

(Bytheway: die Lücken zwischen den roten Linien haben vor langer Zeit fest: p)

Answer 1

Da dies ein GPS ist, muss es ein festes Ziel hat. Anstatt den Pfad von Ihrem aktuellen Knoten zum Ziel jedes Mal zu berechnen, wenn Sie den aktuellen Knoten ändern, können Sie stattdessen die kürzesten Pfade von Ihrem Ziel zu allen Knoten finden: Führen Sie Dijkstra einmal vom Ziel aus aus. Dies dauert ungefähr so ​​lange, wie ein Update jetzt dauert.

Dann behalten Sie in jedem Knoten prev = the node previous to this on the shortest path to this node (von Ihrem Ziel). Sie aktualisieren dies, während Sie die kürzesten Pfade berechnen. Oder Sie können ein prev[] Array außerhalb der Knoten verwenden - grundsätzlich sollte die Methode, die Sie zur Rekonstruktion des Pfads verwenden, jetzt noch funktionieren.

Wenn Sie Ihr Auto bewegen, wird Ihr Pfad durch currentNode.prev -> currentNode.prev.prev -> ... angegeben.

Dies wird die Aktualisierungsverzögerung lösen und Ihren Pfad optimal halten, aber Sie werden immer noch eine leichte Verzögerung haben, wenn Sie Ihr Ziel eingeben.

Sie sollten diesen Ansatz prüfen, auch wenn Sie sich mit A * oder andere Heuristik planen, die zumindest nicht immer die optimale Antwort geben, wenn Sie noch Verzögerung mit diesen Ansätzen bekommen.

Zum Beispiel, wenn Sie diese Grafik:

1 - 2 cost 3 
1 - 3 cost 4 
2 - 4 cost 1 
3 - 4 cost 2 
3 - 5 cost 5 

Die prev Array würde wie folgt aussehen (berechnet, wenn Sie die Abstände d[] berechnen):

 1 2 3 4 5 
prev = 1 1 1 2 3 

Bedeutung:

shortest path FROM TO 
       1 2 = prev[2], 2 = 1, 3 
       1 3 = prev[3], 3 = 1, 3 
       1 4 = prev[ prev[4] ], prev[4], 4 = 1, 2, 4 (fill in right to left) 
       1 5 = prev[ prev[5] ], prev[5], 5 = 1, 3, 5 
       etc. 

Answer 2

Um den Start sofort zu machen, können Sie im folgenden w betrügen ja.

Haben Sie eine ziemlich kleine Reihe von "Hauptdurchgangsknoten". Definieren Sie für jeden Knoten seine "Nachbarschaft" (alle Knoten innerhalb einer bestimmten Entfernung). Speichern Sie die kürzesten Routen von jedem Hauptverkehrsknotenpunkt zu jedem anderen. Speichern Sie die kürzesten Routen zu/von jedem Knoten zu seinen Hauptverkehrsstraßen.

Wenn sich die zwei Knoten in derselben Nachbarschaft befinden, können Sie die beste Antwort im laufenden Betrieb berechnen. Sonst bedenken Sie nur die Wege der Form, "hier zum Hauptdurchgangsknoten neben mir zur Hauptverkehrsstraße in der Nähe davon". Da Sie diese bereits vorausberechnet haben und eine begrenzte Anzahl von Kombinationen haben, sollten Sie sehr schnell in der Lage sein, eine Route im laufenden Betrieb zu berechnen.

Dann wird die Herausforderung eine Reihe von Hauptdurchgangsknoten auswählen. Es sollte eine ziemlich kleine Menge von Knoten sein, die die meisten guten Routen durchlaufen sollten - wählen Sie daher regelmäßig Knotenpunkte entlang der Hauptstraßen. Eine Liste von ein paar hundert sollte mehr als gut genug für Ihre Karte sein.