第5章 路径规划

1、第五章第五章 路径规划路径规划5.1 引言1 路径规划：帮助司机在旅行前或旅行中规划行驶路线的过程。多车路径规划和单车路径规划2 相关知识：动态规划，运筹学，数据结构和算法3 路径优化标准 距离、旅行时间、旅行速度、拐弯和交通灯的数目和动态交通信息。旅行费用4 算法性能时间分析：程序的运行时间被定义为输入函数。空间分析：存储空间。5.2 最短路径5.2.1迪杰斯特拉最短路径算法（Dijkstra） 图5.1 带费用权的有向图（必要条件：有向先端来说费用必须是非负的）OPEN表：已经产生但还没扩展的节点表（未扩展节点表）。CLOSE表：已经扩展的节点表。产生：创建一个对应于特定节点的数据结构。扩

2、展：产生一个节点的所有后继节点（孩子节点）。S：起始节点图5.2 Dijkstra算法（宽度优先）5.2.2 改进的最短路径算法1设初始OPEN表仅含原节点，其费用为0（g值），CLOSE为空表；设其他节点的费用为0。2如果OPEN表为空，则出错，否则，选择OPEN B表中具有最小费用（g值）节点，设其为BEST。从OPEN表中移出节点BEST加入CLOSE表中，确认BEST是否是目标节点，如果是转步骤3，否则，根据其在地图数据库包含的连接线段属性生成节点BEST的后继，对每一后继节点n完成例：2a: g(n)=BEST的费用从BEST到n的费用2b: 如果节点n已和OPEN表中的一个节点相匹

3、配，检查节点n是否具有较低的费用（g值），如果节点n的费用较低，则用节点n的费用代替匹配节点的费用，然后设置匹配节点的后向指针指向BEST节点。2c: 如果n已和CLOSE表中的一个节点相匹配，检查节点n是否具有较低的费用（g值）。如果n节点的费用较低，则用节点n的费用代替匹配节点的费用，然后设置匹配节点的后向指针指向BEST节点并把匹配节点移到OPEN表中。2d: 如果节点n既没有在OPEN表中，也没有在CLOSE表中，设置节点n的后向指针指向BEST节点，然后将节点n放入OPEN表中，重复步骤2。3从BEST节点，遍历后向指针到原节点，报告路径解。5.3 启发式搜索（Heuristical

4、ly search）最佳优先搜索、存储限界搜索和迭代渐进算法5.3.1 A*算法(最佳优先搜索) 引入启发式信息会提高效率。采用启发式的目的是提供一个节点距离目标节点有多远的统计，即使系统能够确定特定节点处于最佳路径解上的可能性。实现途径：计算启发式函数，该函数估价每一生成节点以确定它的优或劣。用这种方式，启发式函数决定在诸多路径中首先遍历哪条路径以便搜索过程更为有效。启发式估价函数使算法首先搜索最有希望的节点。节点n的估价函数为：( )( )( )fng nh n其中， 是原节点到当前节点的实际费用； 是从当前节点n到目标节点最小费用路径的估计。 选择最短旅行时间，启发式估价函数：其中， 为

5、旅行时间， 是路段的旅行距离， 是该路段的最大旅行速度。( )g n( )h n1( )( )( )( )( )( )( )niiid nd nfnt ng nh nV nV( )t n( )id n( )iV nv实际度量函数 是以原节点到当前节点所经过的所有路段的旅行时间总和。v每一路段的旅行时间：由路段的实际距离 除以最大旅行速度 。v估计项 是当前点n和给定的子点之间的欧氏距离除以估计的最大旅行速度 。vA*算法：( )gn( )id n( )iV n( )h nVv图5.3 一个简单的道路网v假设原节点在m，目标节点为g，搜索树如图5.5所示。v图5.4 A*算法的最终搜索树v5.4

6、 双向搜索v 最短路径算法和启发式搜索算法总假定算法从给定原节点到目标节点搜索最小费用路径。前向搜索v从目标节点到原节点进行后向搜索应该产生同样结果。后向搜索v图5.5 由改进最短路径算法和双向搜索算法所检查的空间v双向搜索算法的定理的两个附加条件：1.需要一个停止搜索的标准，2.前向和后向搜索的转换标准。图5.6 单向和双向启发式搜索的搜索条件双向搜索方法和双向启发式搜索算法（自学）双向启发式搜索算法：终止标准和启发式估价函数的选择对于正确执行双向启发式搜索很重要。例如，一个仅考虑旅行费用的启发式估价函数的不正确终止标准，可能导致双向启发式搜索工作量为单向启发式搜索的2倍。v5.5 分层搜索v基本思想：首先进行抽象空间的搜索，即不是在整个原问题空间搜索。v抽象空间：问题空间的简化，即忽略了不需要的细节。然后在搜索抽象空间获得结果的基础上再添上原有空间的细节。选择简化的表达可以导致问题求解能力和效率的提高。v多层抽象可以把指数复杂性减少到线性复杂性。v分层搜索有潜力降低搜索算法的时间复杂性v对于车辆导航来说，用道路级别为路径规划定义一个分层结构是很自然的。v5.6 其他算法v分治法v 把道路网分割成区域（块），对每个区域预先计算出最