《图论旅行商》PPT课件

《图论旅行商》PPT课件

ID:36705170

大小:297.75 KB

页数:32页

时间:2019-05-10

《图论旅行商》PPT课件_第1页
《图论旅行商》PPT课件_第2页
《图论旅行商》PPT课件_第3页
《图论旅行商》PPT课件_第4页
《图论旅行商》PPT课件_第5页
资源描述:

《《图论旅行商》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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。