《《旅行商问题》ppt课件》由会员分享，可在线阅读，更多相关《《旅行商问题》ppt课件（33页珍藏版）》请在金锄头文库上搜索。
1、1,(),图 论,2,2.5 旅行商问题 1. 旅行商问题: 对正权完全图G，求G总长最短的H回路。 (区别Euler回路与H回路) 2. 求解算法：分支定界法 分支定界法是一种用较好方式搜索的准枚举法，实质上就是按字典序枚举所有可能情形并结合剪枝(过滤)的办法。 例 由A,B,C,D,E中的三个不同字母构成的全部字符串，按字典序的排列： ABC,ABD,ABE,ACD,ACE,ADE,BCD,BDE,CDE,3,3. 分支定界法 初始阶段：1. 将全部边按权由小到大排列； 2. 取前n边作为S，置d0:=。 (d0为已考察的H回路中最短的路长) 迭代阶段：3. 若S构成H回路且其路长d(S)
2、d0，则d0:= d(S)。跳过比当前d0差的后续情形后, 用剩下未考察的第一组边作为S，返回3。 全部情形考察完毕时的d0即为最短H回路长度，取其值的那个S就是问题的解。,（将一条边看作一个字符，步骤1已得各字符间的先后关系。对于长为n且各字符互异的所有字符串，本算法要按字典序的顺序逐一考察每一字符串),4,1) 边按权排序(由小到大), d0:= 边： a35 a24 a15 a14 a12 a13 a34 a23 a45 a25 权： 3 4 4 9 10 10 11 13 16 20,例,5,边： a35 a24 a15 a14 a12 a13 a34 a23 a45 a25 权： 3
3、 4 4 9 10 10 11 13 16 20 分支定界： S1: a35 a24 a15 a14 a12 , 非H回路,d(S1)=30; S2: a35 a24 a15 a14 a13 , 非H回路,d(S2)= 30； S3: a35 a24 a15 a14 a34 , 非H回路,d(S3)=31 ； S4: a35 a24 a15 a14 a23 , H回路, d0:= 33; S5: a35 a24 a15 a12 a13 , 非H回路,d(S5)=31; S6: a35 a24 a15 a12 a34 , H回路,d(S6)=32, d0:= 32; S7: a35 a24 a1
4、5 a13 a34 , 非H回路,d(S6)=32; S8: a35 a24 a14 a12 a13 , 非H回路,d(S6)=36; 继续下去所得组长度会比S8差，故可终止计算。,6,故最优解为S6 ，其长度为32。 计算要掌握两个要点： 1. 按字典序逐一考察各边集； 2. 每次考察完一个边集后，应考虑是否可以用过滤条件(当前d0值)跳过一些不必要情形的考察，因为比当前d0值差的情形不需考虑。,7,4. 近似算法“便宜”算法 分支定界法虽可求得旅行售货员问题的准确最优解，但计算复杂度为O(n!)，故对大型问题需寻找近似算法求解。 需采用近似算法往往需要增加一些限制，以便能够提高计算速度和近
5、似程度： (1) G是无向正权图。 (2) 对图中任意的三点构成的三角形，其中任何两边之和大于第三边。,8,求解思路：给v1一个自环，得到第一个回路。以后反复执行以下过程：寻找与已得回路距离最近的点，将之插入到回路中；回路以外无结点时终止。,插入办法：设待插入点为j, 有两种选择: (1) 加入(j,t1)和(j,t)、删除(t,t1); (2) 加入(j,t2)和(j,t)、删除(t,t2). 选使回路长度增加量小的那种办法作插入。,9,例,10,11,2.6 最短路径 1. 最短路问题 在一个赋权图中，将权视为边长，求指定两结点之间的最短路长及路线。 正权图中V1到各点的最短路径 对于正权
6、图G，若L是点vs到点vt的最短路，且L经过点vj ，记L中从vj到vt的那部分路线为L，则L就是vj到vt的一条最短路。,(否则路线 (vsvj)+L” 比L更短,矛盾),12,2. 正权图最短路问题的求解 Dijkstra算法 问题：求起点v1到其它各点的最短路。 记号：用S表示已求得最短路的结点的集合，用E表示到S中各点的最短路的边的集合。 算法中的d(i)(称为点vi的标号)表示起点v1到vi的一条路的长度，当vi在S中时d(i)是v1到vi的最短路的长度。,13,Dijkstra 算法： 1) 让d(1):=0, S:=1, k:=1, E:=; d(i)=w1i, i = 2, 3
7、, ,n. (若图中边(vi,vj)不存在，则记wij =) 2) 在S以外的所有点中找标号最小的点： d(k0)=min d(j): vj不在S中 ; 3) S:=Sk0,k:= k0, E:=Eek0(为取到值d(k0)的边),并修改与vk0相邻的点的标号： d(j):=min d(j), d(k)+wkj, jS. 若|S|=n，则终止迭代；否则回到第2步。 (注意理解jS时标号d(j)的含义),14,对本算法的理解及算法正确性的证明：,(实线表示图中一条边，虚线表示若干条边组成的一条路),15,例 求v1到其它各点的最短路。,令d(v1)=0, 则(红点集合表示S):,16,3. 权均
8、为1时最短路问题的求解 因为是正权图，故可直接采用Dijkstra方法。但此时情况特殊，Dijkstra算法可以简化： 每轮迭代有一批结点标号相同，让它们都进入S；修改它们的全部直接后继结点的标号（均相等），故下一次让这一批结点全部进入S；。 总之，每轮让一批结点进入S后，其全部直接后继结点将成为下一轮进入S的全部结点。反复这一操作，直到|S|=n为止。,17,例 求v1到其它各点的最短路。,令d(v1)=0, 则(红点集合表示S):,18,2. 权有负数时最短路问题的求解 Ford 算法 权有负数时Dijkstra算法失效。( 为什么? ) 若图中不含负回路时最短路问题可解。 Ford算法采
9、用迭代的办法，逐步逼近并最终得到最优解。 算法中第k 次迭代后，d(i)表示从起点v1 到点vi 的一条路的长度，且d(i)小于或等于边数不超过k 的最短路的长度。 因此，算法的迭代次数不超过n 。,19,Ford 算法 1) 令d(1):=0, d(i):=, i =2,3,n; p:=1; 2) 对i =2,3,n, 修改vi 的标号： d(i):=min(d(i), min(d(k)+wki) ) . p:=p+1;,3) 若全部d(i)没有变化则结束; 否则,当pn 时转向2) ，当pn 时存在负回路问题无解.,20,例 求v1到其它各点的最短路。,令d(v1)=0, 则:,21,改进
10、 Ford算法工作量由迭代次数确定。为减小迭代次数，先删除权为负数的边，使用Dijkstra算法，所得解为近似最优解。按计算所得路长对各结点从低到高排队，重新编号。 再添上负数边，将Dijkstra算法得到的路长作为路长的初值，可有效提高算法的效率。,22,2.7 关键路径 1.PT 图 一个结点表示一道工序。工序i 完工后才能开始工序j 表示为一条有向边(i, j), 边长表示完成此工序所需时间。 于是，一个工程可用一个有向图表示，这就是PT 图。 求最早完工时间，就是求PT 图的最长路长度，而最长路即为完成工程的关键工序（关键路径）。,23,PT图中不可能存在有向回路，故可对全部结点重新编
11、号，使得每条有向边总是由编号小的结点指向编号大的。 最长路的计算完全类似于Dijkstra算法的过程。（求min 改为求max）,24,2. PERT 图 一条有向边表示一道工序。 工序 (i, j)表示到结点i 的所有工序都完工后，此工序才能开工。 边长表示完成此工序所需时间。 于是，一个工程可用一个有向图表示，这就是PERT 图。 求最早完工时间，就是求PERT 图的最长路长度，而最长路即为完成工程的关键工序（关键路径）。,25,PERT图中不可能存在有向回路，故可对全部结点重新编号，使得每条有向边总是由编号小的结点指向编号大的。 最长路的计算完全类似于Dijkstra算法的过程。（求mi
12、n 改为求max）,26,2.8 中国邮路问题 定义 例 某邮递员负责在若干街道投递邮件。现从邮局出发，经过每一条街道最后返邮局，问如何行走，使得投递线路最短。这就是“中国邮路”问题。 中国邮路问题: 设G是一个连通的正权简单图，问如何在G中添加重复边，使G有欧拉回路，且重复边的总长最小。,27,2. 算法 定理 设G是无向连通图，适当加边使G存在最佳邮路的充要条件是: (1) G中每条边最多加重复边一条; (2) 在G的任意一个回路上,重复边的长度之和不超过该回路长度的一半. 证：必要性. 若某边的重复边至少有两条，则去掉其中两条后各结点仍然为偶点，故仍然存在Euler回路。,28,若G的某
13、回路C上所加重复边的长度之和超过了该回路长度的一半，则重新删增重复边：将C中原有重复边全部删除，而对C中原来没有重复边的边，每边增加一条重复边。 这样，各点度数为偶的性质不变，故仍含Euler回路，且总路长下降，矛盾。 充分性. (略),29,算法 (1) 适当加边，使所有结点成为偶点(度数为偶数的点)，并且每边的重复边不超过一条。 (2) 检查每个回路，若回路中重复边长之和大于整个回路长的一半，则在该回路上作边的删增：使重复边不重复，使不重复边重复。 若所有回路都满足要求(重复边长之和不大于整个回路长的一半), 则终止迭代。 例 (p.33),30,3. 有向图的中国邮路问题 对于有向图来说, 中国邮路问题可能无解。其原因是G中可能含有出度(正度)或入度(负度)为0的结点，可能进得去出不来或出得去回不来。 如果各结点的正、负度相等，则G中存在有向Euler回路。它经过每边一次且仅一次，因此任一条Euler回路都是中国邮路。 以下通过一个例，介绍它的求解方法。,31,(1)添加总发点vs总收点vt，求vs到vt的2条有向最短路，将它们添加到原图中去。,例 求有向图的中国邮路问题。,32,(2)求vs到vt的一条有向最短路，将它们添加到原图中去, 去掉首尾的边。,(3)求vs到vt的最后一条有向最短路，将它们添加到原图中去, 去掉首尾的边。,33,
