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
摘要: 分析Dijikstra算法、限制区域搜索算法以及A*算法的时间复杂度和空间复杂度,提出一种最短路径搜索算法。将静态存储和动态搜索相结合,以限定区域搜索算法为主、A*算法为辅,并根据港区路况实现该算法。实验结果表明,在区域路网结构相对比较规则的情况下,该算法能够提高路径搜索的效率。
关键词:
最短路径搜索算法,
静态存储,
动态搜索,
限定区域搜索算法,
A*算法
CLC Number:
LIU Lin, LI Shi-Jie, WANG Gui-Fu, MIN Xin-Li, ZHANG Tu, GAO Shan. Shortest Route Search Algorithm in Harbor Guided System[J]. Computer Engineering, 2011, 37(17): 279-281,285.
陆檩, 李世杰, 王贵甫, 闵新力, 张余, 高珊. 港区导航系统中最短路径搜索算法[J]. 计算机工程, 2011, 37(17): 279-281,285.