首页 | 本学科首页   官方微博 | 高级检索  
     

基于分层网络拓扑结构的最优路径算法
引用本文:李楷,钟耳顺,曾志明,曹国峰. 基于分层网络拓扑结构的最优路径算法[J]. 中国图象图形学报, 2006, 11(7): 1004-1009
作者姓名:李楷  钟耳顺  曾志明  曹国峰
作者单位:中国科学院地理科学与资源研究所,北京100101
摘    要:由于Dijkstra算法的基础是平面网络拓扑模型,因此当计算网络的节点数目较大时,计算的时间将急剧膨胀。为了快速地搜索到最优路径,基于分层网络拓扑结构(HiTopo),提出了双向分层搜索最优路径算法(BHWA);该算法对现有分层路径算法进行了以下两点改进:(1)将分级网络的局部连通性作为划分子图的指标;(2)在路径计算过程中,使用弧段作为搜索目标,并采取了双向搜索策略。通过北京道路数据的实验表明:该算法在保持分层路径算法高效性的基础上,还提高了路径搜索结果的准确性;通过进一步研究表明,如果使用启发式搜索来对算法进行优化,则可以使算法的速度有更大的提升。

关 键 词:最优路径算法  层次网络拓扑结构  双向路径搜索
文章编号:1006-8961(2006)07-1004-06
收稿时间:2005-04-21
修稿时间:2005-04-212005-09-01

An Optimal Path Algorithm Based on Hierarchically Structured Topographical Network
LI Kai,ZHONG Er-shun,ZENG Zhi-ming and CAO Guo-feng,LI Kai,ZHONG Er-shun,ZENG Zhi-ming and CAO Guo-feng,LI Kai,ZHONG Er-shun,ZENG Zhi-ming and CAO Guo-feng and LI Kai,ZHONG Er-shun,ZENG Zhi-ming and CAO Guo-feng. An Optimal Path Algorithm Based on Hierarchically Structured Topographical Network[J]. Journal of Image and Graphics, 2006, 11(7): 1004-1009
Authors:LI Kai  ZHONG Er-shun  ZENG Zhi-ming  CAO Guo-feng  LI Kai  ZHONG Er-shun  ZENG Zhi-ming  CAO Guo-feng  LI Kai  ZHONG Er-shun  ZENG Zhi-ming  CAO Guo-feng  LI Kai  ZHONG Er-shun  ZENG Zhi-ming  CAO Guo-feng
Affiliation:Institute of Geographical Sciences and Natural Resources Research, Chinese Academy of Sciences, Beijing 100101
Abstract:The classic Dijkstra algorithm is based on the planar topographical network,the expanding time for searching Optimal Path will increase sharply when the number of network nodes enlarges. In this paper,a path algorithm,namely bidirectional hierarchical wayfinding algorithm(BHWA )which is based on hierarchically structured topographical network(HiTopo) has been developed to speed up searching path. BHWA has two novel features which distinguish itself from existing method. Firstly,structure HiTopo is based on local connectivity of the classified network other than spatial distance. Secondly,it searches arc from two directions which improves upon search node along one direction. An experimental work has been done with BHWA using the map of Beijing,which shown BHWA speeds up computation efficiently while keeps up low error. By farther research,another fact is noted. If the algorithm is optimized by heuristic search,its search speed can be accelerated three times at least.
Keywords:optimal path algorithm   hierarchically structured topographical network   bidirectional search path
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《中国图象图形学报》浏览原始摘要信息
点击此处可从《中国图象图形学报》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号