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