论文部分内容阅读
目前,最短路径问题作为地理信息系统、计算机等科学的研究热点之一,是国内外大量学者关注的研究热点问题。Dijkstra算法作为解决最短路径问题的常用算法,一般用于计算单源最小代价路径,有着广泛的应用。本文通过对传统Dijkstra算法的研究与分析,提出Dijkstra算法的几点不足之处,并对算法进行优化,提高其存储和运算效率。并且在此基础上,加入交通因素,提出一种基于城市路网的最优路径规划算法。首先,介绍了最优路径规划算法的相关理论知识。主要包括智能交通系统的介绍,车辆导航系统及其组成,车辆导航系统中的最优路径规划问题,最优路径规划原理。介绍了图的相关概念和最短路径问题描述,分析了最优路径规划和最短路径问题的相关性。其次,提出了Dijkstra算法的优化算法,基于传统的Dijkstra算法,从存储结构和算法结构两个方面对算法进行了改进,并且对空间复杂度和时间复杂度进行了对比,分析得出优化算法的效率明显提高。再次,提出了基于城市路网的最优路径规划算法。分析了影响路径规划的优化标准,提出了影响路径规划的三个交通因素,即城市道路车辆限速,交通拥挤造成的延误时间和是否单行道。该算法是在基本最短路径算法的基础上加入三个交通因素,考虑城市道路等级和路段顶点权重的基础上提出的。最后,是最优路径规划仿真系统设计与实现,根据本文提出的基于城市路网的最优路径规划算法,搭建最优路径规划仿真系统,仿真实现最短路程路径规划和最短时间路径规划,拟为用户提供最优路径方案。目前,最短路径问题作为地理信息系统、计算机等科学的研究热点之一,是国内外大量学者关注的研究热点问题。Dijkstra算法作为解决最短路径问题的常用算法,一般用于计算单源最小代价路径,有着广泛的应用。本文通过对传统Dijkstra算法的研究与分析,提出Dijkstra算法的几点不足之处,并对算法进行优化,提高其存储和运算效率。并且在此基础上,加入交通因素,提出一种基于城市路网的最优路径规划算法。首先,介绍了最优路径规划算法的相关理论知识。主要包括智能交通系统的介绍,车辆导航系统及其组成,车辆导航系统中的最优路径规划问题,最优路径规划原理。介绍了图的相关概念和最短路径问题描述,分析了最优路径规划和最短路径问题的相关性。其次,提出了Dijkstra算法的优化算法,基于传统的Dijkstra算法,从存储结构和算法结构两个方面对算法进行了改进,并且对空间复杂度和时间复杂度进行了对比,分析得出优化算法的效率明显提高。再次,提出了基于城市路网的最优路径规划算法。分析了影响路径规划的优化标准,提出了影响路径规划的三个交通因素,即城市道路车辆限速,交通拥挤造成的延误时间和是否单行道。该算法是在基本最短路径算法的基础上加入三个交通因素,考虑城市道路等级和路段顶点权重的基础上提出的。最后,是最优路径规划仿真系统设计与实现,根据本文提出的基于城市路网的最优路径规划算法,搭建最优路径规划仿真系统,仿真实现最短路程路径规划和最短时间路径规划,拟为用户提供最优路径方案。