论文部分内容阅读
现如今,城市规模扩大,汽车数量增多,交通拥堵问题成我国亟需解决的重要问题之一。解决城市路网交通拥堵问题的关键技术在于最短路径的研究。因此,基于城市路网的最短路径算法研究具有重要意义。本课题重点研究了求解城市路网最短路径的Dijkstra算法以及求解K最短路径的Yen算法,主要工作如下:(1)在存储城市路网图方面,邻接矩阵存储稀疏图时,存在数据冗余度大的问题,本文提出用邻接表数据结构存储城市路网图,降低Dijkstra算法的空间复杂度。(2)在搜索范围优化方面,Dijkstra算法存在搜索范围广、遍历节点多,耗时长的问题,本文对椭圆搜索算法、矩形搜索算法优化Dijkstra算法的问题进行深入的分析,结合路网特征给出两种算法的具体搜索范围和面积公式。并通过实验对比分析,证明了采用矩形算法优化Dijkstra算法的可行性和高效性。(3)针对Yen算法在求解K最短路径计算比较复杂,时间复杂度高的问题,对Yen算法做了改进。通过引入估价函数,求解最短路径时只选取估价值最小的节点作为最终的偏离节点,降低了算法的复杂度。并通过实验,从算法寻路时间、算法所求的路径长度及寻路过程中产生的候选路径数目方面对比分析了两种算法,验证了算法的有效性。(4)基于unity3d和3ds Max,利用了模型优化技术设计实现了虚拟城市路网寻路系统,将矩形搜索算法和基于启发式搜索改进的Yen算法应用到虚拟城市路网寻路系统中,并验证了本文所提观点在具体应用中的高效性和可行性,达到了预期的寻路效果。