计算机工程 ›› 2010, Vol. 36 ›› Issue (22): 34-36.doi: 10.3969/j.issn.1000-3428.2010.22.012

• 博士论文 • 上一篇    下一篇

基于分块路径缓存的在线路径搜索算法

胡庆武,周 洋   

  1. (武汉大学遥感信息工程学院,武汉 430079)
  • 出版日期:2010-11-20 发布日期:2010-11-20
  • 作者简介:胡庆武(1975-),男,副教授、博士,主研方向:GPS,GIS,RS集成和应用;周 洋,硕士研究生
  • 基金项目:

    国家“863”计划基金资助项目(2008AA121305)

On-line Path Search Algorithm Based on Spatial Block Path Cache

HU Qing-wu, ZHOU Yang   

  1. (School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China)
  • Online:2010-11-20 Published:2010-11-20

摘要:

为建立一个高效的互联网在线地图服务路径搜索引擎,提出一种基于分块路径缓存的最短路径算法。对路网重采样得到路网密集度图像,提出路网分块算法ISODATA。根据路网子块构建路径缓存设计缓存路径索引算法,提出基于子块缓存路径与节点间动态路径结合的双向路径搜索算法。实验结果表明,该算法可将城市级在线路径搜索时间控制在0.2 s以内,降低网络地图服务路径计算服务器负荷。

关键词: 在线路径搜索, 路径缓存, 出入度, 影像城市

Abstract:

In order to construct a high efficiency path finding engine for the on-line map service, a shortest path search algorithm based on spatial block path cache and index is presented. A road network resample processing is proposed to obtain a road network density image and a block algorithm based on ISODATA clustering is presented to calculate the road network spatial block region. The path cache between road network block regions is calculated to reduce the path finding node number between block regions. An index algorithm to the path cache is designed. A bi-direction path search algorithm based on the path cache and path search in block region is presented. Experimental result of on-line path search shows higher efficiency comparing with the traditional path search algorithms which can reduce the on-line path calculation time less than 0.2 s for a city level road network. It can also obtain load balance of the map application server.

Key words: on-line path search, path cache, out-in degree, image city

中图分类号: