正在加载图片...
第3期 王景存等：一种基于Dijkstra算法的启发式最优路径搜索算法 ·349 6 图2 Dijkstra算法(a)和HOPA算法(b)搜索区域分布 Fig.2 Searching area distribution of Dijkstra (a)and HOPA algorithm (b) 2.2实际情况实验数据对比 3 采用某城市5km×5km的一块区域内的城市 结论 交通网作为验证网络，其网络规模为：2008个节点， 本文提出的HOPA算法，其主要思想是借助AI 3167条边；实验平台：P42.6G,1GDDR.表1中的 的决策机制，将每个节点到达终点的代价估计引入 每组数据是随机抽取2O08对点进行运算后得 到算法中来，将传统的均等式宽度优先搜索机制改 出的 进成带有方向性的深度优先搜索机制，以减少搜索 表1实验数据 的节点数，为了进一步减少搜索时间，在搜索过程 Table 1 Test data 中采用二叉堆这一数据结构，随后的实验证明了本 使用 总耗费 平均每次 与最短 文中的定义和结论的正确性，以及该算法在实际应 烫 代价 放缩 二叉 时间/ 寻径耗费 路径切 用中的优越性， 法 函数 堆 系数 ms 时间/ms合度 1 13532 6.74 94.28% 参考文献 否 2 12703 6.33 78.70% [I】唐文武，施晓东，朱大奎.GIS中使用改进的Dkta算法实现 最短路径的计算.中国图像图形学报，2000,5A(12):1019 3 12375 6.16 40.13% 式(3) [2] Agrawal R.Jagadish H V.Materialization and incremental update 1 9969 4.96 94.28% of path information//Proceedings of the 5th International Confer- 是 2 9609 4.79 78.70% ence on Data Engineering.Los Angeles,1989:374 9228 4.60 40.13% [3]吴京，景宁，陈宏盛。最佳路径的层次编码及查询算法，计算 HOPA 1 14359 7.15 100% 机学报，2000,23(2)：184 [4]严寒冰，刘迎春.基于GIS的城市道路网最短路径算法探讨 213063 6.51 89.68% 计算机学报，2000,23(2)：210 312735 6.34 81.17% 式(1) [5]Aleksandrow J.Matheshwari A.Sack J R.Approximation algo 1 11312 5.63 100% rithms for geometrie shortest path problems//Proceedings of the 是 2 10516 5.24 89.687% Thirty second Annual ACM Symposium on Theory of Computing 3 10250 5.10 81.17% 2000.Portland,2000:286 [6]Elkin M.Computing almost shortest paths//Annual ACM Sym Dijkstra 68921 34.32 100可% posium on Principles of Distributed Computing Newport.2001:53 [7]Jacob R,Marathe M.Nagel K.A computational study of routing 由表1可以看出：Dijkstra算法每次寻径耗费的 algorithms for realistic transportation networks/2nd Workshop 时间为35ms左右：而HOPA算法在能确保所有解 on Algorithm Engineering.Saarbrucken.1998:168 为最佳的情况下，耗费的时间也不超过8ms,效率提 [8]Imielinski T.Julio C N.GPS-based Geographie Addressing 高近4倍多.随着D值的增加，时间耗费能进一步 Routing and Resource Discovery.New York:ACM Press,1999 [9]毕军，付梦印，周培德，等.基于城市道路网的快速路径寻优算 减少，但不能保证所有解都为最佳，其中代价函数采 法.计算机工程，2002,28(12)：36 取式(2)其准确率随D值增加降低较快.通过表1 [10]谭国真，高文.时间依赖的网络中最小时间路径算法，计算 亦可看出，使用二叉堆能进一步提高算法效率. 机学报，2002,25(2)：165图2 Dijkstra 算法（a）和 HOPA 算法（b）搜索区域分布 Fig．2 Searching area distribution of Dijkstra （a） and HOPA algorithm （b） 2∙2 实际情况实验数据对比 采用某城市5km×5km 的一块区域内的城市 交通网作为验证网络其网络规模为：2008个节点 3167条边；实验平台：P42∙6G1G DDR．表1中的 每组数据是随机抽取 2008 对点进行运算后得 出的． 表1 实验数据 Table1 Test data 算 法 代价 函数 使用 二叉 堆 放缩 系数 总耗费 时间／ ms 平均每次 寻径耗费 时间／ms 与最短 路径切 合度 1 13532 6∙74 94∙28％ 否 2 12703 6∙33 78∙70％ 式（3） 3 12375 6∙16 40∙13％ 1 9969 4∙96 94∙28％ 是 2 9609 4∙79 78∙70％ HOPA 3 9228 4∙60 40∙13％ 1 14359 7∙15 100％ 否 2 13063 6∙51 89∙68％ 式（1） 3 12735 6∙34 81∙17％ 1 11312 5∙63 100％ 是 2 10516 5∙24 89∙68％ 3 10250 5∙10 81∙17％ Dijkstra － － － 68921 34∙32 100％ 由表1可以看出：Dijkstra 算法每次寻径耗费的 时间为35ms 左右；而 HOPA 算法在能确保所有解 为最佳的情况下耗费的时间也不超过8ms效率提 高近4倍多．随着 D 值的增加时间耗费能进一步 减少但不能保证所有解都为最佳其中代价函数采 取式（2）其准确率随 D 值增加降低较快．通过表1 亦可看出使用二叉堆能进一步提高算法效率． 3 结论 本文提出的 HOPA 算法其主要思想是借助 AI 的决策机制将每个节点到达终点的代价估计引入 到算法中来将传统的均等式宽度优先搜索机制改 进成带有方向性的深度优先搜索机制以减少搜索 的节点数．为了进一步减少搜索时间在搜索过程 中采用二叉堆这一数据结构．随后的实验证明了本 文中的定义和结论的正确性以及该算法在实际应 用中的优越性． 参 考 文 献 ［1］ 唐文武施晓东朱大奎．GIS 中使用改进的 Dijkstra 算法实现 最短路径的计算．中国图像图形学报20005A （12）：1019 ［2］ Agrawal RJagadish H V．Materialization and incremental update of path information∥Proceedings of the5th International Conference on Data Engineering．Los Angeles1989：374 ［3］ 吴京景宁陈宏盛．最佳路径的层次编码及查询算法．计算 机学报200023（2）：184 ［4］ 严寒冰刘迎春．基于 GIS 的城市道路网最短路径算法探讨． 计算机学报200023（2）：210 ［5］ Aleksandrow JMatheshwari ASack J R．Approximation algorithms for geometric shortest path problems∥Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing 2000．Portland2000：286 ［6］ Elkin M．Computing almost shortest paths∥Annual ACM Symposium on Principles of Distributed Computing．Newport2001：53 ［7］ Jacob RMarathe MNagel K．A computational study of routing algorithms for realistic transportation networks∥2nd Workshop on Algorithm Engineering．Saarbrucken1998：168 ［8］ Imielinski TJulio C N．GPS-based Geographic Addressing Routing and Resource Discovery．New York：ACM Press1999 ［9］ 毕军付梦印周培德等．基于城市道路网的快速路径寻优算 法．计算机工程200228（12）：36 ［10］ 谭国真高文．时间依赖的网络中最小时间路径算法．计算 机学报200225（2）：165 第3期 王景存等： 一种基于 Dijkstra 算法的启发式最优路径搜索算法 ·349·