第41卷 第2期 电 子 科 技 大 学 学 报 Vol.41 No.2 最短路径算法加速技术研究综述
宋 青,汪小帆
(上海交通大学电子信息与电气工作学院 上海 闵行区 200240)
【摘要】最短路径的快速有效计算研究具有重要的实际意义。经典算法的高计算复杂度制约了其在大规模网络中的应用。该文从以优先队列为代表的基本加速技术、目标引导技术以及分层技术3个方面综述了该领域最新、最具代表性的一些算法,包括作者在网络分层模型的构造及其分层搜索算法设计方面的最新成果。最后展望了该领域的未来研究方向。
关 键 词 启发式; 分层; 大规模网络; 最优化; 最短路径
中图分类号 TP393;U491 文献标识码 A doi:10.3969/j.issn.1001-0548.2012.02.002
Survey of Speedup Techniques for Shortest Path Algorithms
SONG Qing and WANG Xiao-fan
(School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University Minhang Shanghai 200240)
Abstract The problem of efficient path computation arises in many domains of practical importance. Classical algorithms failed to apply to large-scale networks due to their heavy computational complexity. This paper reviews some latest representative results classified according to the underlying speedup techniques, including basic speedup techniques like priority queues, goal-directed techniques, and hierarchical approaches. Moreover, the paper introduces the most recent achievement of the authors on network hierarchy construction and hierarchical algorithm design. Finally, some future directions are discussed.
Key words heuristics; hierarchical; large-scale networks; optimization; shortest paths
最短路径问题一直是运筹学、计算机科学、地断发展完善的计算机数据结构及各类加速技术的有理信息科学、交通运输等领域的一个研究热点[1-2]。效结合使得新的最短路径算法不断涌现。它们在空很多实际问题都可以通过抽象进而转化为网络中的间复杂度、时间复杂度、易实现性及应用范围等方最短路径计算问题,如道路交通网络中的出行路线面各具特色[8-12]。 选取问题,计算机网络中信息流在路由器间的最佳传输问题,以及社会关系网络中两个陌生人之间的联系紧密度计算问题等。因此,针对网络中最短路径的有效计算问题研究具有重要的理论和现实意义。继文献[3]针对Dijkstra算法的开创性工作之后,大量专家学者围绕该问题进行了深入研究。特别是近年来伴随着大规模动态网络数据的出现,最短路径的实时计算面临着新一轮的挑战。很多实际系统(如GPS导航系统以及消防、救灾等应急系统)都要求在尽可能短的时间内获取最佳路径,以更好地应对网络动态等方面的影响,为用户提供快速决策。所有这些都依赖于更高性能的最短路径算法。受人工智能等领域一些思想的启发,一系列针对最短路径求解的启发式加速方案应运而生,经典算法与不收稿日期: 2011 08 04;修回日期:2011 12 27
基金项目:国家自然科学基金(61074125);国家973计划(2010CB731400)
作者简介:宋青(1983 ),女,博士生,主要从事复杂系统建模与优化方面的研究.
[4-7]
本文首先简单回顾了以标号算法为代表的经典最短路径算法的基本思想及其具体实现,然后根据使用的加速技术的不同对现有的最短路径算法研究进行了系统分类和详细评述。最后,针对最短路径算法的发展方向进行了探讨。
1 最短路径问题及经典算法
实际网络在数学上可以抽象成一个图G=(V, E, W),其中V为节点集合,E为边集合,W为边的权重集合。每个节点代表系统中的一个确定目标,如道路交通网络中的某个道路交叉口,因特网中的某一路由器等。连边e=(i, j)表征节点i、j对应的网络目标之间的连接关系,可以是有向的或无向的,其权重wij∈W刻画了该连边上某种属性的强度。以道路交
2012 最短路径算法加速技术研究综述宋 青,汪小帆 (上海交通大学电子信息与电气工作学院 上海 闵行区 200240) 【摘要】最短路径的快速有效计算研究具有重要的实际...
K最短路径算法综述_信息与通信_工程科技_专业资料。201 3年11月 计算机 工程... 最短路径算法加速技术研... 28人阅读 9页 2.00 同时送取货车辆路径...
交通网络最短路径并行算法研究综述_IT/计算机_专业资料。交通网络中关于最短..., 并对这两种方法进行了对比 , 但却没有测试 它们相对于串行算法的加速比 ....
交通网络最短路径并行算法研究综述_专业资料。首先回顾了最短路径并行算法的国内外研究进展,对当前的最短路径并行算法进行分类。接着讨论了交通网络分析中最短路径...
stra算法的搜索效率,从而提出了采用多层地图和分级搜索技术来实现对最短路径搜索... 维普资讯 http://www.cqvip.com 基于 I S的加速最短路径搜索算法研究 T ...
地图中最短路径的搜索算法研究综述_学习总结_总结/汇报_应用文书。关于深度优先... 最短路径算法加速技术研... 9页 免费 基于数字地图的多属性最... 3页 ...
3. 3 实现技术 另一种最短路径算法分类方法是按实现技术 分类。 分类方法如图 3 所示。 其中路径搜索技术 中的通用技术是最短路径算法研究的重点所在。 路径...
3. 3 实现技术另一种最短路径算法分类方法是按实现技术 分类。分类方法如图 3 所示。其中路径搜索技术 中的通用技术是最短路径算法研究的重点所在。 路径搜索...
最短路径的并行算法综述 最短路径的并行算法综述 最...图论的研究得到广泛重视,最短路径问题 是图论中的一...PRAW 上,算法的第(3)到(5)步采用分组技术,每个...
热门文档