[1]王海梅,周献中.一种限制搜索区域的最短路径改进算法[J].南京理工大学学报(自然科学版),2009,(05):638-642.
 WANG Hai-mei,ZHOU Xian-zhong.Improved Shortest Path Algorithm for Restricted Searching Area[J].Journal of Nanjing University of Science and Technology,2009,(05):638-642.
点击复制

一种限制搜索区域的最短路径改进算法
分享到:

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

卷:
期数:
2009年05期
页码:
638-642
栏目:
出版日期:
2009-10-30

文章信息/Info

Title:
Improved Shortest Path Algorithm for Restricted Searching Area
作者:
王海梅 1 周献中 2
1.南京理工大学自动化学院, 江苏南京210094; 2.南京大学控制与系统工程系,江苏南京210093
Author(s):
WANG Hai-mei1ZHOU Xian-zhong2
1.School of Automation,NUST,Nanjing 210094,China;2.Department of Control and Systems Engineering,Nanjing University,Nanjing 210093,China
关键词:
最短路径 Dijkstra算法 矩形限制搜索区域 比值系数
Keywords:
shortest path Dijkstra algorithm restricted rectangle searching area ratio coefficients
分类号:
TP301.6
摘要:
最短路径算法效率是许多应用领域普遍关注和迫切需要解决的问题。该文在深入分析经典Dijkstra最短路径算法优化途径的基础上,从控制路网规模入手,提出了矩形限制搜索区域的最短路径算法。根据路网分布的特点,采取比值系数分段取值的方法,进一步提高了算法效率。原型系统实验显示了改进算法的高效性和可行性。
Abstract:
Algorithmic efficiency of the shortest path searching is a problem which has brought wide attention and needs to be resolved urgently in many application fields.Based on the classical Dijkstra’s shortest path algorithm,the optimization means is analyzed.A restricted rectangle searching area algorithm is proposed to reduce the searching area.In order to improve the running efficiency,variational ratio coefficients are used during path searching to adapt the characteristic of the road network path searching.The experiment on the prototype system shows that the algorithm presented here is highly effective and feasible.

参考文献/References:

[ 1] 乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[ J]. 武汉测绘科技大学学报, 1999, 24( 3): 209-212.
[ 2] 王开义, 赵春江, 胥桂仙, 等. GIS领域最短路径搜索问题的一种高效实现[ J]. 中国图象图形学报, 2003, 8( 8): 951- 956.
[ 3] 陆锋, 卢冬梅, 崔伟宏. 交通网络限制搜索区域时间最短路径算法[ J]. 中国图象图形学报, 1999, 4( 10): 849-853.
[ 4] 陈则王, 袁信. 基于分层分解的一种实时车辆路径规划算法[ J]. 南京航空航天大学学报, 2003, 35( 2): 193-197.
[ 5] Hart P, NilssonN, PaphaelB. A formal basis for the heuristic determination of minimum cost path[ J]. IEEETransactions onSystemsScience andCyberne-t ics, 1968, 4( 2): 100-107.
[ 6] 陆锋, 周成虎, 万庆. 基于层次空间推理的交通网络行车最优路径算法[ J]. 武汉测绘科技大学学报, 2000, 25(3): 226- 232.
 [ 7] Fisher PF. Aprimer ofgeographic searchusing artif-i cial intelligence[ J]. Computers and Geosciences, 1990, 16( 6): 753-776.
[ 8] 严寒冰,刘迎春. 基于GIS的城市道路网最短路径算法探讨[ J]. 计算机学报, 2000, 23( 2): 210-215.
[ 9] 陆锋, 卢冬梅,崔伟宏. 基于四叉堆优先级队列及逆邻接表的改进型Dijkstra算法[ J]. 中国图象图形学报, 1999, 4( 12): 1044-1050.
[ 10] 唐文武, 施晓东, 朱大奎. GIS中使用改进的Dijk-stra算法实现最短路径的计算[ J]. 中国图象图形学报, 2000, 5( 12): 1019-1023.
[ 11] StigN, BengtR. Computer cartography shortest route program[M]. Sweden: TheRoyalUniversity ofLund, 1969.
[ 12] 崔伟宏. 空间数据结构研究[M]. 北京: 中国科学技术出版社, 1995.
[ 13] 陈行星, 崔伟宏. 城市快速反应系统实验研究[ J]. 环境遥感, 1995, 11( 3): 227- 233.
[ 14] 王海梅, 周献中. 网络系统中的最短路径分析及其应用研究[ J]. 兵工学报, 2006, 27(3): 515- 518.

备注/Memo

备注/Memo:
作者简介: 王海梅( 1968- ),女, 博士,副教授, 主要研究方向:过程控制、智能信息处理, E-mail: whm163mail@ 163. com。
更新日期/Last Update: 2012-11-19