VC出租车路线规划算法Dijkstra设计(6)
时间:2017-01-10 10:59 来源:毕业论文 作者:毕业论文 点击:次
3.1.2 算法思想 首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。 迪杰斯特拉算法描述如下： 1）arcs表示弧上的权值。若不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[Locate Vex(G,v),i] vi∈V 2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。 3.1.3 算法具体步骤 如图3-1，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等） 图3-1 初始状态 算法执行步骤如图3-2 图3-2 过程图 3.2人工智能寻路 3.2.1 可行性探讨 所谓最短路径，在这里指的是满足用户约束条件的最短路径：用户的约束条件是：给定起始结点(Start)与目标结点 (Goa1)以及该路径的必经结点序列，I=(I1，I2，…，In)和避开结点序列0=(01 ，O2，…，0n )。这里假设必经结点序列是顺序给出的，表示该路径的第 i个必经结点是Ii (1≤ i≤n)；而避开结点序列中的结点没有顺序规定。产生的最短路径是由若干个结点组成的序列，即：P：｛Pl，P2 ，…，Pk }其中：P1=Start，Pk：Goal Ii (1≤i≤n) Oi∉ P(1≤ i≤m)那么，P是一条满足上述条件的最短路径。 3.2.2 最短路径规划算法设计 该算法分为两个主要阶段，首先在路段空间数据基础上建立搜索图，该搜索图一旦建成，保持相对稳定。然后在该搜索图中进行最短路径查找。 3.2.3 建立搜索图 在GIS中，公路或街道都是以线实体的形式存储，这里采用如下数据结构存储公路或街道空间数据：Road={Name,( x1,y1;x2,y2;...;xn ,ym)}其中，Name表示该公路或街道的名称，(xi , yi)表示组成该公路或街道的结点。由此看到，每一条公路或街道就是一条线，每条线是由若干个直线段构成。Road表是由所有公路或街道表示的线组成的。 搜索图采用邻接表进行存储，其结构定义如下： struet node f／／每个邻接表头结构 int Nid：／／结点编号 float x，Y：／／结点坐标 struet vnode link；／／指向下一个相邻结点 } stmct vnode {／／每个相邻结点结构 int Nid；／／相邻结点的编号 struct vnode*next；／／指向下一个相邻结点 } struct node adjlist[MAX—NODE】；／／定义邻接表 (责任编辑：qin) |