第三章 路径规划的分析及设计 17 TC(Pab)=∑c(vi,vi+1) (i=1,2,?,n-1) （3-1）
所谓最短路径问题是指，在带权的有向图中寻找从指定起点到终点的一条权值总和最小路径。如果把权值看成弧的长度（即距离），则目标路径就是起点到终点的距离最短的路径。
为说明求解给定两点间最短路径的算法，我们先来讨论单源点的路径问题，即给定带权的有向图G=(V,E)和原点v，求从v到G中其余各节点的最短路径。为了求解这一问题，Dijkstra提出了一种按路径长度递增次序来产生最短路径的Dijkstra算法，其原理如下：
首先，引进一个辅助向量D，它的每个分量D(i)表示当前所找到的从起始点v到每个重点vi的最短路径的长度。D的初始状态为：若从v到vi有弧，则D(i)为弧上的权值；否则令D(i)为∞。显然，长度为D(i)=Min{ D(i)|vi∈V}的路径就是从v出发的长度最短的一条路径，记为(v,vi)。假设S为已求得最短路径的终点的集合，则下一条最短路径（设其终点为x）或者是弧〈v,x〉，或者是中间只经过S中的节点而最后到达节点x的路径。这可用反证法来证明：假设此路径上有一个节点不在S中，则说明存在一条终点不在S而长度比路径更短的路径。事实上这是不可能的。因为我们是按路径长度递增的次序来产生各条最短路径的，故长度比此路径短的所有路径均已产生，它们的终点必定是在S中，即假设不成立。因此，在一般情况下，下一条长度次短的最短路径的长度必须是
D(j)=Min{ D(i)|vi∈V-S} (3-2)
其中，D(i)或者是弧〈v,vi〉上的权值，或者是D(k)(vk∈S)和弧〈vk,vi〉上的权值之和。
从以上对Dijkstra算法原理分析可以看出，其最大特点是在最短路径的求解过程中搜索算法具有很大的盲目性，随时准备向其四面八方展开，最终的搜索区域基本上是以起始点为原点，以起始点与目标点的连线长度为半径的一个圆。
2.算法实现 （1）邻接矩阵法
根据上面对算法原理的分析，可以得到如下描述的单源点最短路径算法： 步骤一，假设用带权的邻接矩阵cost来表示带权有向图，cost(i,j)表示弧〈vi,vj〉上的权值，其中，1≤i≤n,1≤j≤n。若〈vi,vj〉不存在，则置cost(i,j)为∞。S的初状态为空集。从v出发到图上其余各节点（终点）vi可能达到的最短
18 GPS车载导航仪的路径规划研究 路径长度D(i)的初始值为
D(i)=cost(v,vi) vi∈V (3-3)
步骤二，选择vj，使得
D(j)=Min{ D(i)|vi∈V-S} (3-4)
vj就是当前求得的从v出发的最短路径的终点，令
S=S∪{vj} (3-5) 步骤三，修改从v出发到集合V-S上任一节点vk可达的最短路径长度，如果 D(j)+cost(j,k)＜D(k) (3-6) 则修改D(k)为
D(k)= D(j)+cost(j,k) (3-7) 步骤四，重复操作步骤二、步骤三共n-1次，由此求得按路径长度递增次序排列的从v出发到图上其余各节点的最短路径。
以上算法求解的是从源点出发到其余各节点的最短路径。但是车辆导航系统的路径规划只需要求解出从源点到指定终点的一条最短路径，并且要记下并在地图上显示该路径，因此要对以上算法做适当的修改。设指定终点为t,在步骤二中，如果发现vj=t，则算法终止，D(t)的值就是从源点v到终点t的最短路径的距离。为了能记下路径，设置一个路径向量P，其中P(i)表示从源点到达i节点的最短路径上该点的前趋节点。算法结束前，可根据P找到从源点到终点t的最短路径上每个节点的前趋节点，从而得到从源点到终点t的最短路径。
由于采用邻接矩阵法在解算最短路径时，搜索算法假设道路网络中的任意一个节点都和其他所有节点相邻接，因此导致其时间复杂度为O(n2),其中n为道路网络的节点总数。
（2）邻接节点法
邻接矩阵法的不足是邻接矩阵cost中存在大量的无效的0元素和∞元素，这不仅占用大量的存储空间，而且也使得基于矩阵运算的Dijkstra算法效率大为降低。为了弥补邻接矩阵法的这种不足，下面给出Dijkstra算法的另一种实现算法——邻接节点法。
邻接节点法的基本思想是：先求出道路网络中各节点直接相邻节点的最大个数（简称为最大邻接点数，用变量MaxNum表示），然后以MaxNum作为矩阵的列数，以道路网络中的节点总数n作为矩阵的行数，构造邻接节点矩阵J来描述道路网
第三章 路径规划的分析及设计 19 络中节点间的邻接关系。J的行按节点号从小到大顺序排列，与节点i邻接的节点号卸载矩阵的第i行，如果节点i的邻接节点个数小于MaxNum，则以0填充第i行直到填满。构造与J结构相同的初始判断矩阵DJ，同时将J中个元素邻接关系对应的边的权值填在同一位置上（∞对应0元素）。即J(i,j)表示第j个与节点i邻接的节点编号，相应的，DJ(i,j)表示节点i与其邻接节点J(i,j)连线的权值，其中，1≤i≤n,1≤j≤MaxNum。这样，邻接节点法便用维数相对较低的矩阵J和DJ取代了邻接矩阵法中维数较高的矩阵cost，从而有效地改善了算法的存储效率和运算效率。
为了能够应用邻接节点法解算任意指定两点间的最短路径，程序首先需要完成以下3项预处理工作，以便得到初始化矩阵J和DJ：
①装载道路网络数据，获得道路网络中的节点和边的内部序号。需要说明的是，道路网络节点和边的内部序号与实际编号可以不相同。为了增加算法的灵活性，算法使用内部编号参数运算（这里假设内部序号和实际编号相同）。
②计算道路网络的最大邻接节点数MaxNum。
③构造邻接节点矩阵J，各行中的节点序号可以前后随意放置。对应邻接节点矩阵J的各元素，构造初始判断矩阵DJ。
有了邻接节点矩阵J和初始判断矩阵DJ以后，就可以对网络中任意给定两点进行最短路径规划。下面给出邻接节点法的具体实现步骤：
输入：道路网络的邻接节点矩阵J和初始判断矩阵DJ，以及路径规划的起点S和终点D。
输出：起点S到终点D的一条最短路径MinWay及相应的最短距离MinDist。 步骤一，初始化标记向量Mark，Mark(i)=—1，其中，i=1,2，?，MaxNum。 步骤二，根据起始点S，标记初始判断矩阵DJ的第s行，Mark(s)=0，记最短距离 MinDist=0。
步骤三，根据终点D，判断DJ的第d行是否已经标记，是则转步骤五；否则继续。
步骤四，在DJ已标记的行中，求所有元素的最小值dmin，若dmin=∞，说明不存在最短路径，程序退出；否则MinDist=dmin，记录最小值元素所在的行di、列dj。然后再J中取(di,dj)元素，记为w，若第w行尚未标记，则将DJ的第w行标记，Mark(w)=di；并在J的第w行寻找值为di的元素，记录该元素的行ri、列
20 GPS车载导航仪的路径规划研究 rj。将DJ刚获得标记的行中各元素值均加上MinDist，并使DJ的(di,dj)和(ri,rj)元素为∞。然后转步骤三。
步骤五，从终点D开始，由标记向量Mark的分量寻前点，知道起始点S，查得最短路径MinWay，MinDist即为相应的最短路径距离。
与邻接矩阵法相比，邻接节点法不仅将道路网络的存储空间降低到原来的MaxNum/n，而且也将搜索算法的时间复杂度降低到O(MaxNum·n)，由于MaxNum＜＜n，因此采用邻接节点法时算法的时间复杂度实质上是O(n)。
为方便起见，我们将不加任何启发式搜索策略的经典Dijkstra算法简称为算法RP0。
3.3.2 限制搜索区域的路径规划算法
针对Dijkstra算法搜索过程中无方向性的缺点，本节利用道路网络特有的空间分布特性够早了一种方向搜索策略，并给出利用该搜索策略合理限制算法搜索区域的具体方法，从而降低了算法搜索空间，提高了算法搜索效率。
1.算法原理
（1）道路网络特有的空间分布特性
与普通的平面网络图相比，描述实际城市道路网络的拓扑图通常具有以下特点：
①多为大规模的稀疏网络，点多边少（网络的节点通常成千上万，甚至更多，而每个节点相连的路段一般不超过5，多为2、3或4）。
②网络结构相对比较规则，即网中的节点分布比较均与（特别是经过规划的现代大都市）。
③网络通常是（或近似是）完全连通图，即网络中的任意两点都可以相互到达。
④网络中有表示供智能车辆掉头的换向节点，而且一般距当前路口500m左右。 （2）方向搜索策略的构造与应用
受几何学中“两点之间直线距离最短”的启发，在对实际城市道路网络中的给定两点进行最短路径规划时，起点到终点的连线方向基本上代表了最短路径的大致走向。在进行最短路径搜索时，我们可以利用该启发式信息来构造方向启发式搜索方法，合理缩小算法的空间，提高算法的搜索效率。
相关推荐：
loading