第5章-路径规划分析优秀PPT.ppt

《第5章-路径规划分析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第5章-路径规划分析优秀PPT.ppt（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章 路径规划路径规划5.1 5.1 引言引言1 1 路径规划：帮助司机在旅行前或旅行中规划路径规划：帮助司机在旅行前或旅行中规划行驶路途的过程。行驶路途的过程。多车路径规划和单车路径规划多车路径规划和单车路径规划2 2 相关学问：动态规划，运筹学，数据结构和相关学问：动态规划，运筹学，数据结构和算法算法3 3 路径优化标准路径优化标准 距离、旅行时间、旅行速度、拐弯和交通灯的距离、旅行时间、旅行速度、拐弯和交通灯的数目和动态交通信息。数目和动态交通信息。旅行费用旅行费用4 4 算法性能算法性能时间分析：程序的运行时间被定义为输入函数。时间分析：程序的运行时间被定义为输入函数。空间分析

2、：存储空间。空间分析：存储空间。5.2 最短路径5.2.1迪杰斯特拉最短路径算法（Dijkstra）图5.1 带费用权的有向图（必要条件：有向先端来说费用必需是非负的）OPEN表：已经产生但还没扩展的节点表（未扩展节点表）。CLOSE表：已经扩展的节点表。产生：创建一个对应于特定节点的数据结构。扩展：产生一个节点的全部后继节点（孩子节点）。S：起始节点图5.2 Dijkstra算法（宽度优先）5.2.2 改进的最短路径算法1设初始OPEN表仅含原节点，其费用为0（g值），CLOSE为空表；设其他节点的费用为0。2假如OPEN表为空，则出错，否则，选择OPEN B表中具有最小费用（g值）节点，设

3、其为BEST。从OPEN表中移出节点BEST加入CLOSE表中，确认BEST是否是目标节点，假如是转步骤3，否则，依据其在地图数据库包含的连接线段属性生成节点BEST的后继，对每一后继节点n完成例：2a:g(n)=BEST的费用从BEST到n的费用2b:假如节点n已和OPEN表中的一个节点相匹配，检查节点n是否具有较低的费用（g值），假如节点n的费用较低，则用节点n的费用代替匹配节点的费用，然后设置匹配节点的后向指针指向BEST节点。2c:假如n已和CLOSE表中的一个节点相匹配，检查节点n是否具有较低的费用（g值）。假如n节点的费用较低，则用节点n的费用代替匹配节点的费用，然后设置匹配节点的

4、后向指针指向BEST节点并把匹配节点移到OPEN表中。2d:假如节点n既没有在OPEN表中，也没有在CLOSE表中，设置节点n的后向指针指向BEST节点，然后将节点n放入OPEN表中，重复步骤2。3从BEST节点，遍历后向指针到原节点，报告路径解。5.3 启发式搜寻（Heuristically search）最佳优先搜寻、存储限界搜寻和迭代渐进算法5.3.1 A*算法(最佳优先搜寻)引入启发式信息会提高效率。接受启发式的目的是供应一个节点距离目标节点有多远的统计，即使系统能够确定特定节点处于最佳路径解上的可能性。实现途径：计算启发式函数，该函数估价每一生成节点以确定它的优或劣。用这种方式，启发

5、式函数确定在诸多路径中首先遍历哪条路径以便搜寻过程更为有效。启发式估价函数使算法首先搜寻最有希望的节点。节点n的估价函数为：其中，是原节点到当前节点的实际费用；是从当前节点n到目标节点最小费用路径的估计。选择最短旅行时间，启发式估价函数：其中，为旅行时间，是路段的旅行距离，是该路段的最大旅行速度。v实际度量函数 是以原节点到当前节点所经过的全部路段的旅行时间总和。v每一路段的旅行时间：由路段的实际距离 除以最大旅行速度 。v估计项 是当前点n和给定的子点之间的欧氏距离除以估计的最大旅行速度 。vA*算法：v图5.3 一个简洁的道路网v假设原节点在m，目标节点为g，搜寻树如图5.5所示。v图5.

6、4 A*算法的最终搜寻树v5.4 双向搜寻v 最短路径算法和启发式搜寻算法总假定算法从给定原节点到目标节点搜寻最小费用路径。前向搜寻v从目标节点到原节点进行后向搜寻应当产生同样结果。后向搜寻v图5.5 由改进最短路径算法和双向搜寻算法所检查的空间v双向搜寻算法的定理的两个附加条件：v1.须要一个停止搜寻的标准，v2.前向和后向搜寻的转换标准。图5.6 单向和双向启发式搜寻的搜寻条件双向搜寻方法和双向启发式搜寻算法（自学）双向启发式搜寻算法：终止标准和启发式估价函数的选择对于正确执行双向启发式搜寻很重要。例如，一个仅考虑旅行费用的启发式估价函数的不正确终止标准，可能导致双向启发式搜寻工作量为单向

7、启发式搜寻的2倍。v5.5 分层搜寻v基本思想：首先进行抽象空间的搜寻，即不是在整个原问题空间搜寻。v抽象空间：问题空间的简化，即忽视了不须要的细微环节。然后在搜寻抽象空间获得结果的基础上再添上原有空间的细微环节。选择简化的表达可以导致问题求解实力和效率的提高。v多层抽象可以把指数困难性削减到线性困难性。v分层搜寻有潜力降低搜寻算法的时间困难性v对于车辆导航来说，用道路级别为路径规划定义一个分层结构是很自然的。v5.6 其他算法v分治法v 把道路网分割成区域（块），对每个区域预先计算出最优局部路径，然后找寻并把这些局部最优路径贯穿一条完整的从原节点到目标节点的路径。v实时启发式搜寻算法v 时间约束限制搜寻节点的数目。v动态在线算法v遗传算法、Tabu搜寻、鲁棒性算法最近流行，有爱好的同学自己学。