《最优路径规划算法设计报告》由会员分享，可在线阅读，更多相关《最优路径规划算法设计报告（24页珍藏版）》请在金锄头文库上搜索。
1、1 最优路径规划算法设计一、问题概述兵力机动模型的功能是支持实施机动的实体按照指定路线，由作战空间的一点向另外一点的位置移动，并带入实体在移动过程中发生变化的状态信息。兵力机动模型包括行军模型、 战斗转移模型、 机动能力评估模型。 涉及的关键算法包括最优路径规划、行军长径计算、行军时间计算、行军所需油料计算、行军方案评估与优选等。最优路径问题又称最短路问题。是网络优化中的基本问题，如TSP问题等。下面先举例说明该问题。最短路问题（ SPP shortest path problem ）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错， 因此有多种行车路线，
2、 这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的， 那么这一问题相当于需要找到一条从甲地到乙地的最短路。旅行商问题（ TSPtraveling salesman problem ）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地？）最短路问题是组合优化中的经典问题，它是通过数学方法寻找离散时间的最优编排、分组、次序、或筛选等，这类问题可用数学模型描述为min)(xf.ts0)(xgDx. 其中，)(xf为目标函数，)(xg为约束函数，x为决策变量，D表示有限个点组成的集合。一个组合最优化问题可用三个参数),(fFD
3、表示，其中D表示决策变量的定义域，F表示可行解区域0)(,|xgDxxF，F中的任何一个元素称为该问2 题的可行解， f 表示目标函数，满足|)(min)(*Fxxfxf的可行解*x 称为该问题的最优解。 组合最优化的特点是可行解集合为有限点集。由直观可知， 只要将D中有限个点逐一判别是否满足0)(xg的约束并比较目标值的大小，就可以得到该问题的最优解。以上述 TSP问题为例，具体阐述组合优化问题：此模型研究对称 TSP问题, 一个商人欲到n个城市推销产品，两个城市i和j之间的距离jiijdd，用数学模型描述为jiijijxdmin1.1njijxtsni, 2, 1，1.1niijxtsnj
4、, 2, 1，, 2, 1, 2|2, 1|,nsnssxsjiijjinjixij,2, 1,1 , 0约束条件决策变量1ijx表示商人行走的路线包含从城市i到j的路，而0ijx表示商人没有选择走这条路；ji的约束可以减少变量的个数，使得模型中共有) 1(nn个决策变量。每一个组合优化问题都可以通过完全枚举的方法求得最优解。枚举是以时间为代价的，在 TSP问题中，用n个城市的一个排列表示商人按这个排列序推销并返回起点。 若固定一个城市为起终点， 则需要)!1(n个枚举。以计算机s1可以完成24个城市所有路径枚举为单位，则25个城市的计算时间为：以第1个城市为起点，第2个到达城市有可能是第2个
5、、第3个、 、第25个城市。决定前两个城市的顺序后， 余下是23个城市的所有排列， 枚举这23个城市的排列需要s1，所以，25个城市的枚举需要24s。类似地归纳，城市数与计算时间的关系如表1 所示。3 表 1 枚举时城市数与计算时间的关系城市数24 25 26 27 28 29 30 31 计算时间1s24s10minh3.49.4天5.136天8.10年325年通过表 1 可以看出， 随着城市数的增加， 计算时间增加非常之快， 当城市数增加到 30 时， 计算时间约为 10.8 年， 实际计算中已无法承受。 在城市数较多时，枚举已不可取，我们可以采用一些别的方法缩短计算时间。TSP问题是 N
6、P难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难求出其最优解， 因而一般是找出其有效的近似求解算法。遗传算法可以用来解决一些较为复杂的系统问题，显然旅行商问题是需要编码运算的，而遗传算法本身的特征正好为解决这一问题提供了很好的途径。NP问题：是指非确定多项式问题类。若存在一个多项式函数)(xg和一个验证算法H，使得：判定问题A的任何一个实例I为“是”实例当且仅当存在一个验证字符串S， 满足其输入长度)(Sd不超过)(Idg， 其中)(Id为I的输入长度，且算法H验证实例I为“是”实例的计算时间)(Hf不超过)(Idg, 则称判定问题A是非确定多项式的。对于判定问题A，若 N
7、P中的任何一个问题可在多项式时间内归约为判定问题A，则称A为 NP难问题。二、知识准备根据实际需求， 本文拟给出三种算法针对不同的情况做出解答。分别是基于图论和网络优化的Dijkstra 和 FloydWarshall算法。这两种算法用来解决起点与终点不重合的问题。 最后根据现有智能优化计算中的遗传算法计算哈密尔顿回路问题，即起点与终点重合问题。1、 图论基本知识有向图的定义：一个有向图G是由一个非空有限集合)(GV和)(GV中某些元素 的 有 序 对 集 合)(GE构 成 的 二 元 组 ， 记 为)(),(GEGVG。 其 中, . . . ,)(21nvvvGV称为图G的顶点集，)(GV
8、中的每一个元素),.,2, 1(nivi，称4 为该图的一个顶点；,.,)(21meeeGE称为图G的弧集，记为),(jikvve，记有向图),(EVG（a） 和（c）是无向图，（b）是有向图2、 邻接矩阵表示法图),(EVG的邻接矩阵C是如下定义的：C是一个nn的 0-1 矩阵，即nn nnijcC 1 ,0)(，AjiAjicij),( , 1),( ,0，也就是说，如果两节点之间有一条弧，则邻接矩阵中对应元素为1，否则为 0. 图（a）和图（ b）的邻接表矩阵即为3、0001000100100010000100110yxwvuyxwvu在计算机中用二维数组表示，两节点之间有弧相应的元素为
9、1. 必须指出的是：目前为止，一切最短路算法都只对不含负有向圈的网络有效。实际上，对于含负有向圈的网络，其最短路问题是NP-hard。因此，除非特别说明，一律假定网络不包含负有向圈。 此外在实际问题中也会遇到无向网络上的最短路问题，这时原问题一般可以转化为有向网络中上的最短路问题。如果所有弧上的权ijw 全为非负数，只需将无向图的一条边代之以两条对称的有向弧即可。如果弧上的权ijw 有负有正，一般来说问题要复杂得多，要具体问题具体分析。本文中所要解决的问题都取权值为正，无向图皆采取两条对称的有向弧问题。5 kkveevevW.2110，其中kjGVvkiGEeji0),(,1),(，ie 与i
10、ivv,1关联，称W是图G的一条道路，k为路长，顶点0v 和kv 分别称为W的起点和终点，而121,.,kvvv称为他的内部顶点。若道路W的边互不相同，则W称为迹。若道路W的顶点互不相同，则W称为轨。称一条道路是闭的， 如果它有正的长且起点和终点相同。起点和终点重合的轨叫做圈 (cycle)。若图G 的两个顶点 u, v间存在道路，则称 u和v连通(connected) 。u, v间的最短轨的长叫做 u, v间的距离。记作 d(u,v)。若图 G 的任二顶点均连通，则称 G 是连通图。显然有：(i) 图P 是一条轨的充要条件是 P 是连通的，且有两个一度的顶点，其余顶点的度为2；(ii)图C
11、是一个圈的充要条件是 C 是各顶点的度均为 2 的连通图三、应用以行军途中各目标为图 G 的顶点，两目标之间的连线为图G 相应两顶点间的边，得图 G 。对G 的每一边 e，赋以一个实数 w(e)两目标之间的距离长度，称为e的权，得到赋权图 G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图 G 中指定的两个顶点00,vu间的具最小权的轨。 这条轨叫做00,vu间的最短路，它的权叫做00,vu间的距离，亦记作),(00vud。四、算法设计1Dijkstra算法1.1 定义预览：Dijkstra(迪杰斯特拉 ) 算法是典型的单源最短路径算法， 用于计算一个节点到其他所有节点的最短路径。 主
12、要特点是以起始点为中心向外层层扩展，直到扩6 展到终点为止。 Dijkstra算法是很有代表性的最短路径算法，注意该算法要求图中不存在负权边。1.2算法描述1) 算法思想：设 G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合 （用 S表示，初始时 S中只有一个源点， 以后每求得一条最短路径 , 就将加入到集合 S中， 直到全部顶点都加入到S中， 算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示） ，按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中， 总保持从源点 v 到 S中各顶点的最短路径长度不大于从源点v 到 U中任
13、何顶点的最短路径长度。 此外，每个顶点对应一个距离， S中的顶点的距离就是从v 到此顶点的最短路径长度，U中的顶点的距离，是从 v 到此顶点只包括 S中的顶点为中间顶点的当前最短路径长度。2）算法步骤：a.初始时， S只包含源点，即 Sv，v 的距离为 0。U 包含除 v 外的其他顶点，即 :U=其余顶点 ，若 v 与 U 中顶点 u 有边，则 正常有权值，若 u 不是 v 的出边邻接点，则 权值为 。b.从 U 中选取一个距离v 最小的顶点 k，把 k 加入 S 中（该选定的距离就是 v 到 k 的最短路径长度）。c.以 k 为新考虑的中间点，修改U 中各顶点的距离；若从源点v 到顶点 u的
14、距离（经过顶点 k）比原来距离（不经过顶点 k）短，则修改顶点 u 的距离值，修改后的距离值的顶点k 的距离加上边上的权。d.重复步骤 b 和 c 直到所有顶点都包含在S 中。3）算法实例图 1 是 5 个节点的赋权无向图7 图 1 各节点之间的赋权无向图1 10 100 2 30 5 50 10 60 3 20 4 图 1 中有 5 个节点（54321,vvvvv） ，且是无向图。每条弧有相应的权值。编码时若两节点之间没有弧，其相应的权值用99999 表示其代码如下： int const MAXLENTH=50; int const MAX=99999; void Dijkstra(int
15、n,int v,int *dist,int *prev,int cMAXLENTHMAXLENTH)/ 迪杰斯特 拉算法，计算最短路径 bool sMAXLENTH; int i,j; for (i=1;in;i+) for (j=1;jn;j+) Aij=g-edgesij; pathij=-1; for(k=1;kn;k+)/先确定 k 点，找寻经过 k 点的最短路径的节点 for(i=1;in;i+) for(j=1;jn;j+) if(Aik!=0 pathij=k; coutn; dispath(A,path,i); 11 运行结果如下3遗传算法3、1 算法简介遗传算法（ Genet
16、ic Algorithms，简称 GA）是一种基于自然选择原理和自然遗传机制的搜索（寻优）算法，它是模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。 遗传算法的实质是通过群体搜索技术，根据适者生存的原则逐代进化， 最终得到最优解或准最优解。 它必须做以下操作： 初始群体的产生、求每一个体的适应度、 根据适者生存的原则选择优良个体 （评估适应度）、被选出的优良个体两两配对， 通过随机交叉其染色体的基因并随机变异某些染色体的基因后生成下一代群体， 按此方法使群体逐代进化， 直到满足进化终止条件。其实现方法如下：（1） 根据具体问题确定可行解域，确定一种编码方法， 能用数值串或字符串表示可行解域的每一解。（2） 对每一解应有一个度量好坏的依据，它用一函数表示，叫做适应度函数，适应度函数应为非负函数。（3） 确定进化参数群
