全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

基于分层网络拓扑结构的最优路径算法

DOI: 10.11834/jig.200607172

Keywords: 最优路径算法,层次网络拓扑结构,双向路径搜索

Full-Text   Cite this paper   Add to My Lib

Abstract:

由于Dijkstra算法的基础是平面网络拓扑模型,因此当计算网络的节点数目较大时,计算的时间将急剧膨胀。为了快速地搜索到最优路径,基于分层网络拓扑结构(HiTopo),提出了双向分层搜索最优路径算法(BHWA);该算法对现有分层路径算法进行了以下两点改进:(1)将分级网络的局部连通性作为划分子图的指标;(2)在路径计算过程中,使用弧段作为搜索目标,并采取了双向搜索策略。通过北京道路数据的实验表明:该算法在保持分层路径算法高效性的基础上,还提高了路径搜索结果的准确性;通过进一步研究表明,如果使用启发式搜索来对算法进行优化,则可以使算法的速度有更大的提升。

References

[1]  Goldbergav M.Expected performance of Dijkstra\'s shortest path algorithm[D].Princeton,NJ,USA:Princeton University,1996.
[2]  Wang Kai-yi,Zhao Chun-jiang.A High efficiency Realization Way of the Shortest Path Search Problem in GIS Field[J].Journal of Image and Graphics,2003,8(8):951~956.[王开义,赵春江.GIS领域最短路径搜索问题的一种高效实现[J].中国图象图形学报,2003,8(8):951~956.]
[3]  Jing N,Huang Y.Hierarchical encoded path views for path query processing:An optimal model and its performance evaluation[J].IEEE Transaction.Knowledge and Data Engineering,1998,10 (3):409 ~ 432.
[4]  Jung Sungwon.An efficient path computation model for hierarchically structured topographical road maps[J].IEEE Transactions on Knowledge and Data Engineering,2002,14 (5):1029 ~ 1046.
[5]  Lu Feng,Zhou Cheng-hu.An optimum velicular path algorithm for traffic network based on hierarchical spatial reasoning[J].Journal of Wuhan Technical University of Surveying and Mapping,2002,25(3):226-232.[陆锋,周成虎.基于空间层次推理的城市交通网络最短路径算法[J].武汉测绘科技大学学报,2000,25(3):226-232.]
[6]  Muralidharan S.The origin-destination shortest path problem[D].AT & T Bell Laboraties,Holmdel,NJ,USA,1993:16 ~ 22.
[7]  Yan Han-bing,Liu Ying-chun.A new algorithm for finding shortcut in a city\'s road net based on GIS technology[J].Chinese Journal of Computers,2000,23(2):210 ~215.[严寒冰,刘迎春.基于 GIS城市道路网最短路径算法探讨[J].计算机学报,2000,23(2):210~215.]
[8]  Car A.Hierarchical spatial reasoning:theoretical consideration and its application to modeling wayfinding[D].Geoinfo Series,Department of Geoinformation,Technical University Vienna,Vienna,Austria,1997.
[9]  Easasm S M.shortest route algorithm with movement prohibition[J].Transportation Research,1985,19B (3):197 ~ 208.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133