| 一种适于车辆导航系统的快速路径规划算法 |
| |
| 引用本文： | 毕军,付梦印,周培德. 一种适于车辆导航系统的快速路径规划算法[J]. 北京理工大学学报, 2002, 22(2): 188-191. DOI: 10.3969/j.issn.1001-0645.2002.02.015 |
| |
| 作者姓名： | 毕军 付梦印 周培德 |
| |
| 作者单位： | 1. 北京理工大学,自动控制系,北京,100081;2. 北京理工大学,计算机科学与工程系,北京,100081 |
| |
| 摘 要： | 针对城市道路网图节点数较多,经典的求解最短路径的Dijkstra算法存在计算时间较长的问题.对矢量化的城市道路网图的特点进行分析,给出了道路网图的计算机存储结构,提出一种快速求解城市道路网两节点间的最短路径近似算法.算法的实现采用双向式搜索法、投影法和夹角最小的方法.理论分析和实验结果表明,和Dijkstra算法相比,该算法尽管有时得不到最优解,但能大大减小搜索空间,提高搜索速度,时间复杂性不超过O(N),适用于车辆导航系统.
|
| 关 键 词： | 最短路径 路径规划 车辆导航 |
| 文章编号： | 1001-0645(2002)02-0188-04 |
| 收稿时间： | 2001-09-19 |
| 修稿时间： | 2001-09-19 |
A Quick Path-Planning Algorithm for Vehicle Navigation System |
| |
| BI Jun,FU Meng yin and ZHOU Pei de. A Quick Path-Planning Algorithm for Vehicle Navigation System[J]. Journal of Beijing Institute of Technology(Natural Science Edition), 2002, 22(2): 188-191. DOI: 10.3969/j.issn.1001-0645.2002.02.015 |
| |
| Authors: | BI Jun FU Meng yin ZHOU Pei de |
| |
| Affiliation: | BI Jun 1,FU Meng yin 1,ZHOU Pei de 2 |
| |
| Abstract: | The computing time of the Dijkstra algorithm which is considered a typical algorithm for the shortest path computation is relatively long, if a city's road net map has many nodes. To improve the situation, the characteristics and data structure of the vector map of a city's road net are discussed, and then a quick approximate algorithm for the shortest path between two nodes in a city's road net is proposed. The algorithm takes advantage of the methods of bidirection, projection and minimum angle. Analysis in theory and experimental results show that compared with the Dijkstra algorithm, although the new algorithm cannot reach the optimum occasionally, it can greatly reduce the seeking space and increase the seeking speed. Its time complexity can not exceed O(N) , and can well be applied to vehicle navigation systems. |
| |
| Keywords: | shortest path path planning vehicle navigation |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《北京理工大学学报》浏览原始摘要信息 |
|
点击此处可从《北京理工大学学报》下载全文 |
|
