作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (17): 279-281,285. doi: 10.3969/j.issn.1000-3428.2011.17.094

• 开发研究与设计技术 • 上一篇    下一篇

港区导航系统中最短路径搜索算法

陆 檩,李世杰,王贵甫,闵新力,张 余,高 珊   

  1. (上海申腾信息技术有限公司,上海 200040)
  • 收稿日期:2011-04-07 出版日期:2011-09-05 发布日期:2011-09-05
  • 作者简介:陆 檩(1974-),男,高级工程师,主研方向:无线定位算法;李世杰,硕士;王贵甫、闵新力,高级工程师、博士;张 余,工程师;高 珊,硕士
  • 基金资助:
    上海市科学技术委员会重点攻关专项基金资助项目(08DZ 1500900)

Shortest Route Search Algorithm in Harbor Guided System

LU Lin, LI Shi-jie, WANG Gui-fu, MIN Xin-li, ZHANG Yu, GAO Shan   

  1. (Shanghai Shenteng Information Technology Co., Ltd., Shanghai 200040, China)
  • Received:2011-04-07 Online:2011-09-05 Published:2011-09-05

摘要: 分析Dijikstra算法、限制区域搜索算法以及A*算法的时间复杂度和空间复杂度,提出一种最短路径搜索算法。将静态存储和动态搜索相结合,以限定区域搜索算法为主、A*算法为辅,并根据港区路况实现该算法。实验结果表明,在区域路网结构相对比较规则的情况下,该算法能够提高路径搜索的效率。

关键词: 最短路径搜索算法, 静态存储, 动态搜索, 限定区域搜索算法, A*算法

Abstract: Analysing the time complexity and space complexity of Dijkstra Algorithm, restricted area search algorithm and A* algorithm, on the bases this, the paper proposes a shortest route search algorithm. The algorithm makes the static memory and dynamic search combined, uses the restricted area research algorithm as the main algorithm, is supplemented by A* algorithm, according to the port road condition to realize the algorithm. Experimental results show that the algorithm can enhance the route searching efficiency in the occasion of regular road network structure.

Key words: shortest route search algorithm, static store, dynamic search, limited area search algorithm, A* algorithm

中图分类号: