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

An Optimal Path Algorithm Based on Hierarchically Structured Topographical Network

作　　者：李楷[1] 钟耳顺[1] 曾志明[1] 曹国峰[1] 

机构地区：[1]中国科学院地理科学与资源研究所,北京100101

出　　处：《中国图象图形学报》2006年第7期1004-1009,共6页Journal of Image and Graphics

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

关 键 词：最优路径算法 层次网络拓扑结构 双向路径搜索 

分 类 号：P208[天文地球—地图制图学与地理信息工程]