摘要: 针对分层路径规划算法对上下层道路的对应关系存储耗费大量存储空间的问题,提出一种适合嵌入式环境的改进分层算法。通过在各个层次内部引入道路等级信息提高计算速度,在运算过程中动态切换搜索层次和等级达到减少分层数和数据量的目的。对比实验表明,改进算法在扩展节点数和路径规划时间方面均优于其他3种算法,且能满足嵌入式环境中高效路径规划的需求。
关键词:
嵌入式系统,
分层路径规划算法,
Dijkstra算法
Abstract: Aiming at the problem that hierarchical path planning algorithm always has to store the correspondence between roads of different hierarchies which makes the storage efficiency critical, this paper proposes an improved hierarchical path planning algorithm which is suitable for embedded system. This algorithm enhances computing speed by importing road class information into every road hierarchy, and dynamically switches searching hierarchy and class to reduce hierarchy number and the amount of data. Comparison experiment shows the improved algorithm has better performance than other three kinds of algorithms on the aspects of extended node number and path planning time, and it can satisfy the need of efficient path planning in embedded system.
Key words:
embedded system,
hierarchical path planning algorithm,
Dijkstra algorithm
中图分类号:
苗洋, 陈奇. 嵌入式环境中分层路径规划算法的改进[J]. 计算机工程, 2010, 36(14): 243-245.
MIAO Xiang, CHEN Ai. Improvement of Hierarchical Path Planning Algorithm in Embedded Environment[J]. Computer Engineering, 2010, 36(14): 243-245.