最短路径算法加速技术研究综述

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

最短路径算法加速技术研究综述

宋青, 汪小帆

文章导航 > 电子科技大学学报 > 2012 > 41(2): 176-184

宋青, 汪小帆. 最短路径算法加速技术研究综述[J]. 电子科技大学学报, 2012, 41(2): 176-184. doi: 10.3969/j.issn.1001-0548.2012.02.002

引用本文:

宋青, 汪小帆. 最短路径算法加速技术研究综述[J]. 电子科技大学学报, 2012, 41(2): 176-184. doi: 10.3969/j.issn.1001-0548.2012.02.002

SONG Qing, WANG Xiao-fan. Survey of Speedup Techniques for Shortest Path Algorithms[J]. Journal of University of Electronic Science and Technology of China, 2012, 41(2): 176-184. doi: 10.3969/j.issn.1001-0548.2012.02.002

Citation:

SONG Qing, WANG Xiao-fan. Survey of Speedup Techniques for Shortest Path Algorithms[J]. Journal of University of Electronic Science and Technology of China, 2012, 41(2): 176-184. doi: 10.3969/j.issn.1001-0548.2012.02.002

最短路径算法加速技术研究综述

doi: 10.3969/j.issn.1001-0548.2012.02.002

宋青,
汪小帆

1.
上海交通大学电子信息与电气工作学院上海闵行区 200240

基金项目:

国家自然科学基金(61074125);国家973计划(2010CB731400)

作者简介:
宋青(1983-),女,博士生,主要从事复杂系统建模与优化方面的研究.

中图分类号: TP393;U491

Survey of Speedup Techniques for Shortest Path Algorithms

1.
School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University Minhang Shanghai 200240

摘要: 最短路径的快速有效计算研究具有重要的实际意义。经典算法的高计算复杂度制约了其在大规模网络中的应用。该文从以优先队列为代表的基本加速技术、目标引导技术以及分层技术3个方面综述了该领域最新、最具代表性的一些算法,包括作者在网络分层模型的构造及其分层搜索算法设计方面的最新成果。最后展望了该领域的未来研究方向。
- 启发式 /
- 分层 /
- 大规模网络 /
- 最优化 /
- 最短路径
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.
- heuristics /
- hierarchical /
- large-scale networks /
- optimization /
- shortest paths

[1]	张辰逸, 尚涛, 刘建伟. 基于交换门的前瞻启发式量子线路映射算法 . 电子科技大学学报, 2023, 52(4): 489-497. doi: 10.12178/1001-0548.2022339
[2]	马闯, 杨晓龙, 张海峰, 李春春. 基于最少边的最短路径扰动 . 电子科技大学学报, 2023, 52(2): 271-279. doi: 10.12178/1001-0548.2022177
[3]	何选森, 徐丽, 许莹. 启发式联合PCD快速降噪算法 . 电子科技大学学报, 2021, 50(3): 360-367. doi: 10.12178/1001-0548.2020053
[4]	马慧, 汤庸, 傅瑜, 易锋. 时间依赖图下的最小费用路径搜索 . 电子科技大学学报, 2020, 49(3): 458-466. doi: 10.12178/1001-0548.2019002
[5]	李吉良, 张文, 刘强, 汪文勇. 一种大规模时间触发确定性网络 . 电子科技大学学报, 2019, 48(6): 815-822. doi: 10.3969/j.issn.1001-0548.2019.06.003
[6]	王建伟, 张海林. 全双工大规模MIMO网络中最优天线分配 . 电子科技大学学报, 2018, 47(5): 660-664. doi: 10.3969/j.issn.1001-0548.2018.05.004
[7]	吴亚东, 蒋宏宇, 赵思蕊, 李波. 网络安全数据3D可视化方法 . 电子科技大学学报, 2015, 44(4): 594-598. doi: 10.3969/j.issn.1001-0548.2015.04.020
[8]	陈卓, 冯钢, 周江. 分层P2P点播系统中优化的带宽资源分配策略 . 电子科技大学学报, 2014, 43(3): 443-449. doi: 10.3969/j.issn.1001-0548.2014.03.022
[9]	刘贵松, 解修蕊, 黄海波, 屈鸿. 基于最短路径信任关系的推荐项目计算方法 . 电子科技大学学报, 2014, 43(2): 162-166. doi: 10.3969/j.issn.1001-0548.2014.02.001
[10]	唐聃, 黄健. 流水车间调度问题的启发式算法研究 . 电子科技大学学报, 2013, 42(6): 921-925. doi: 10.3969/j.issn.1001-0548.2013.06.021
[11]	梁瑞仕, 姜云飞, 杨会志. 基于有序爬山法的前向启发式搜索规划 . 电子科技大学学报, 2013, 42(3): 464-469. doi: 10.3969/j.issn.1001-0548.2013.03.028
[12]	景振海, 白宝明, 马啸. 干扰信道中容量可达的率分裂方案 . 电子科技大学学报, 2011, 40(6): 855-859. doi: 10.3969/j.issn.1001-0548.2011.06.009
[13]	闫维新, 马文涛, 付庄, 赵言正, 周晓燕. 烹饪机器人翻锅运动最优化设计 . 电子科技大学学报, 2011, 40(3): 476-480. doi: 10.3969/j.issn.1001-0548.2011.03.029
[14]	宋现锋, 刘军志. QoS支持下的GIS服务链最优化问题研究 . 电子科技大学学报, 2010, 39(2): 298-301,315. doi: 10.3969/j.issn.1001-0548.2010.02.031
[15]	史亮, 王备战, 姜青山, 陈黎飞. 面向大规模网络应用的移动主体系统安全机制 . 电子科技大学学报, 2007, 36(6): 1202-1205,1218.
[16]	张晓琴, 黄玉清. 基于禁忌搜索的启发式求解背包问题算法 . 电子科技大学学报, 2005, 34(3): 359-362.
[17]	赵建宏, 杨建宇, 雷维礼. 一种新的最短路径算法 . 电子科技大学学报, 2005, 34(6): 778-781.
[18]	虞红芳, 詹柔莹, 李乐民. 一种启发式的计算机局域网故障诊断方法 . 电子科技大学学报, 2002, 31(2): 151-155.
[19]	卢军, 陈凌虎, 卢显良. 一种适应WAN的新型分层缓存管理机制 . 电子科技大学学报, 2002, 31(3): 275-280.
[20]	王光泰, 周先敏, 徐继麟. 多传感器信息最优融合 . 电子科技大学学报, 1997, 26(5): 465-467.

WeChat

点击查看大图

计量

文章访问数: 4747
HTML全文浏览量: 159
PDF下载量: 96
被引次数: 0

最短路径算法加速技术研究综述

doi: 10.3969/j.issn.1001-0548.2012.02.002

宋青,
汪小帆

1. 上海交通大学电子信息与电气工作学院上海闵行区 200240

基金项目:

国家自然科学基金(61074125);国家973计划(2010CB731400)

作者简介:
宋青(1983-),女,博士生,主要从事复杂系统建模与优化方面的研究.

收稿日期: 2011-08-04
修回日期: 2011-12-27
刊出日期: 2012-04-15

中图分类号: TP393;U491

关键词:

摘要: 最短路径的快速有效计算研究具有重要的实际意义。经典算法的高计算复杂度制约了其在大规模网络中的应用。该文从以优先队列为代表的基本加速技术、目标引导技术以及分层技术3个方面综述了该领域最新、最具代表性的一些算法,包括作者在网络分层模型的构造及其分层搜索算法设计方面的最新成果。最后展望了该领域的未来研究方向。

English Abstract

宋青, 汪小帆. 最短路径算法加速技术研究综述[J]. 电子科技大学学报, 2012, 41(2): 176-184. doi: 10.3969/j.issn.1001-0548.2012.02.002

引用本文:

宋青, 汪小帆. 最短路径算法加速技术研究综述[J]. 电子科技大学学报, 2012, 41(2): 176-184. doi: 10.3969/j.issn.1001-0548.2012.02.002

SONG Qing, WANG Xiao-fan. Survey of Speedup Techniques for Shortest Path Algorithms[J]. Journal of University of Electronic Science and Technology of China, 2012, 41(2): 176-184. doi: 10.3969/j.issn.1001-0548.2012.02.002

Citation:

SONG Qing, WANG Xiao-fan. Survey of Speedup Techniques for Shortest Path Algorithms[J]. Journal of University of Electronic Science and Technology of China, 2012, 41(2): 176-184. doi: 10.3969/j.issn.1001-0548.2012.02.002

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

期刊在线

编辑办公

友情链接

电子科技大学

版权所有 © 《电子科技大学学报》编辑部

地址: 成都市建设北路二段四号电子科技大学主楼中350室电话: 028-83202308,83207559 Email: xuebao@uestc.edu.cn

本系统由北京仁和汇智信息技术有限公司开发