小编drs*_*a44的帖子

我正在OpenStreetMap地图上写一个快递/物流模拟,并且已经意识到如下图所示的基本A*算法对于大型地图(如大伦敦)来说不够快.

绿色节点对应于放置在开放集/优先级队列中的绿色节点,并且由于数量巨大(整个地图大约为1-2百万),需要5秒左右才能找到所示的路线.不幸的是,每条路线100毫秒是我的绝对限制.

目前,节点存储在邻接列表和空间100×100 2D阵列中.

我正在寻找可以在预处理时间,空间和路线最佳性能之间进行权衡的方法,以便更快地进行查询.根据剖析器,启发式成本的直线Haversine公式是最昂贵的函数 - 我尽可能地优化了我的基本A*.

例如,我在想是否从2D阵列的每个象限中选择一个任意节点X并在每个象限之间运行A*,我可以将路径存储到磁盘以供后续模拟.查询时,我只能在象限中​​运行A*搜索,以便在预先计算的路径和X之间进行搜索.

是否有我上面所描述的更精致的版本,或者我应该追求的另一种方法.非常感谢!

为了记录,这里有一些基准测试结果,用于任意加权启发式成本并计算10对随机选取的节点之间的路径:

Weight // AvgDist% // Time (ms)
1       1       1461.2
1.05    1       1327.2
1.1     1       900.7
1.2     1.019658848     196.4
1.3     1.027619169     53.6
1.4     1.044714394     33.6
1.5     1.063963413     25.5
1.6     1.071694171     24.1
1.7     1.084093229     24.3
1.8     1.092208509     22
1.9     1.109188175     22.5
2       1.122856792     18.2
2.2     1.131574742     16.9
2.4     1.139104895     15.4
2.6     1.140021962     16
2.8     1.14088128      15.5
3       1.156303676     16
4       1.20256964      13
5       1.19610861      12.9

令人惊讶的是,将系数增加到1.1几乎将执行时间减半,同时保持相同的路线.