《图论旅行商》PPT课件

《《图论旅行商》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、(Ⅲ)图论12.5旅行商问题1.旅行商问题:对正权完全图G，求G总长最短的H回路。(区别Euler回路与H回路)2.求解算法：分支定界法分支定界法是一种用较好方式搜索的准枚举法，实质上就是按字典序枚举所有可能情形并结合剪枝(过滤)的办法。例由A,B,C,D,E中的三个不同字母构成的全部字符串，按字典序的排列：ABC,ABD,ABE,ACD,ACE,ADE,BCD,BDE,CDE23.分支定界法初始阶段：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且各字符互异的所有字符串，本算法要按字典序的顺序逐一考察每一字符串)31)边按权排序(由小到大),d0:=∞边：a35a24a15a14a12a13a34a23a45a25权：3449101011131620142354101311169102043例4边：a35a24a15a14a12a13a34a23a45a25权：3449101011131620分支定界：S1:a35a2

3、4a15a14a12,非H回路,d(S1)=30;S2:a35a24a15a14a13,非H回路,d(S2)=30；S3:a35a24a15a14a34,非H回路,d(S3)=31；S4:a35a24a15a14a23,H回路,d0:=33;S5:a35a24a15a12a13,非H回路,d(S5)=31;S6:a35a24a15a12a34,H回路,d(S6)=32,d0:=32;S7:a35a24a15a13a34,非H回路,d(S6)=32;S8:a35a24a14a12a13,非H回路,d(S6)=36;继续下去所得组长度会比S8差，故可终止计算。5故最优解为S6，其

4、长度为32。计算要掌握两个要点：1.按字典序逐一考察各边集；2.每次考察完一个边集后，应考虑是否可以用过滤条件(当前d0值)跳过一些不必要情形的考察，因为比当前d0值差的情形不需考虑。64.近似算法－－“便宜”算法分支定界法虽可求得旅行售货员问题的准确最优解，但计算复杂度为O(n!)，故对大型问题需寻找近似算法求解。需采用近似算法往往需要增加一些限制，以便能够提高计算速度和近似程度：(1)G是无向正权图。(2)对图中任意的三点构成的三角形，其中任何两边之和大于第三边。7求解思路：给v1一个自环，得到第一个回路。以后反复执行以下过程：寻找与已得回路距离最近的点，将之插入到回路中

5、；回路以外无结点时终止。jt1tt2插入办法：设待插入点为j,有两种选择:(1)加入(j,t1)和(j,t)、删除(t,t1);(2)加入(j,t2)和(j,t)、删除(t,t2).选使回路长度增加量小的那种办法作插入。8例(1)t10(2)找出回路外到v1最近的点（在第一行找）v2，插入回路：v2v11818(3)找出到v1,v2最近的点（第1,2行去掉第1,2列后，在此范围找）v5，插入回路：v5v2v12718199(4)找出到v1,v2,v5最近的点（第1,2,5行去掉第1,2,5列后，在此范围找）v4，插入回路：v2v1v5v418242721(5)找出到v1,v2

6、,v5,v4最近的点（第1,2,4,5行去掉第1,2,4,5列后，在此范围找）v3，插入回路：17v424v2v1v5v3182723102.6最短路径1.最短路问题在一个赋权图中，将权视为边长，求指定两结点之间的最短路长及路线。正权图中V1到各点的最短路径对于正权图G，若L是点vs到点vt的最短路，且L经过点vj，记L中从vj到vt的那部分路线为L’，则L’就是vj到vt的一条最短路。vsvjvtL’L”(否则路线(vs→vj)+L”比L更短,矛盾)112.正权图最短路问题的求解——Dijkstra算法问题：求起点v1到其它各点的最短路。记号：用S表示已求得最短路的结点的集

7、合，用E表示到S中各点的最短路的边的集合。算法中的d(i)(称为点vi的标号)表示起点v1到vi的一条路的长度，当vi在S中时d(i)是v1到vi的最短路的长度。12Dijkstra算法：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:=S∪{k0},k:=k0,E:=E∪{ek0}(为取到值d(k0)的边),并修改与v