一种适于车辆导航系统的快速路径规划算法

被引：9

作者：

毕军

付梦印

周培德

机构：

[1] 北京理工大学自动控制系

[2] 北京理工大学计算机科学与工程系北京

[3] 北京

来源：

北京理工大学学报 | 2002年 / 02期

关键词：

最短路径; 路径规划; 车辆导航;

D O I：

10.15918/j.tbit1001-0645.2002.02.015

中图分类号：

U463.6 [电气设备及附件];

学科分类号：

080204 ; 082304 ;

摘要：

针对城市道路网图节点数较多 ,经典的求解最短路径的 Dijkstra算法存在计算时间较长的问题 .对矢量化的城市道路网图的特点进行分析 ,给出了道路网图的计算机存储结构 ,提出一种快速求解城市道路网两节点间的最短路径近似算法 .算法的实现采用双向式搜索法、投影法和夹角最小的方法 .理论分析和实验结果表明 ,和Dijkstra算法相比 ,该算法尽管有时得不到最优解 ,但能大大减小搜索空间 ,提高搜索速度 ,时间复杂性不超过O( N ) ,适用于车辆导航系统

引用

页码：188 / 191

页数：4