限制搜索区域的距离最短路径规划算法

摘要：

提出一种时间复杂度为O(n)的限制搜索区域距离最短路径规划算法(n为路网节点数).算法设计的基础是,经典Dijkstra算法搜索时的无方向性及实际城市道路网络特有的空间分布特性.算法实现采用邻接表数据结构和限制搜索区域的搜索机制,即利用实际城市道路网络的空间分布特性,合理限制算法的搜索区域.结合路径规划算法在实时车辆导航系统中的实际应用,给出了该算法的应用实例,实验结果表明,该算法能将路网中任意两点间的最短路径解算时间控制在3 s以内.

关键词：车辆导航系统、路径规划、道路网络、限制搜索区域

所属期刊栏目：24

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家部委预研基金2040501

在线出版日期：2004-12-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：881-884