c++ - 用于 GPS 系统的 Dijkstra 算法的更快替代方案

Question

如果涉及到算法，以及我为游戏制作的插件，我是一个真正的速度狂。

速度是..有点..不满意。尤其是当你驾车四处行驶并且你没有按照你的路径行驶时，必须重新计算路径..这需要一些时间，所以游戏中的 GPS 正在叠加许多“错误的方向”信号(并叠加信号意味着以后要进行更多的计算，对于每一个错误的移动方式)因为我想要一个快速的实时 gps 系统，它会不断更新。

我将旧算法(一些简单的 dijkstra 实现)更改为 boost::dijkstra 来计算从节点 A 到节点 B 的路径

(总节点列表大约有 15k 个节点和 40k 个连接，对于好奇的人，这里是 map :http://gz.pxf24.pl/downloads/prv2.jpg(12 MB)，红线中的边是节点)，

但它并没有真正提高速度。 (至少不明显，可能是 50 毫秒)。

Node数组中存储的信息是:

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.

我很好奇是否有人知道 C/C++ 中一些更快的替代方案？任何建议(+代码示例？)表示赞赏!

---

如果有人对该项目感兴趣，请看这里(源代码+二进制文件):

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

在此视频中，您可以看到 gps 系统是什么样的:

http://www.youtu.be/xsIhArstyU8

如您所见，红色路线更新缓慢(好吧，对于我们 - 游戏玩家 - 它很慢)。

( ByTheWay: 红线之间的缝隙早就修好了 :p )

Answer 1

既然是GPS，肯定有固定的目的地。您不必在每次更改当前节点时都计算从当前节点到目的地的路径，而是可以找到从目的地到所有节点的最短路径:只需从目的地开始运行一次 Dijkstra。这将花费与现在更新一样长的时间。

然后，在每个节点中，prev = 到此节点的最短路径上的前一个节点(从您的目的地)。在计算最短路径时更新它。或者您可以在节点外使用 prev[] 数组 - 基本上，无论您使用什么方法重建路径，现在都应该仍然有效。

移动汽车时，路径由 currentNode.prev -> currentNode.prev.prev -> ... 给出。

这将解决更新滞后问题并使您的路径保持最佳状态，但您在进入目的地时仍然会有轻微的滞后。

即使您计划使用 A* 或其他并不总能给出最佳答案的启发式方法，您也应该考虑这种方法，至少在您仍然落后于这些方法的情况下。

例如，如果您有此图表:

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

prev 数组看起来像这样(在计算距离 d[] 时计算):

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

含义:

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.