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