数学建模经典问题——旅行商问题课件.ppt

《数学建模经典问题——旅行商问题课件.ppt》由会员分享，可在线阅读，更多相关《数学建模经典问题——旅行商问题课件.ppt（104页珍藏版）》请在三一办公上搜索。

1、1,第7章 旅行商问题,2,第7章 旅行商问题,1.问题概述,2.求解算法,2.1.下界和上界算法,2.2.分支定界法,目录,2.5.竞赛题,2.3.动态规划法,2.5.近似算法,3,7-1 问题概述,一、数学模型 1.标准TSP 旅行商问题（简称TSP），也称货郎担问题或旅行推销员问题，是运筹学中一个著名的问题，其一般提法为：有一个旅行商从城市1出发，需要到城市2、3、n去推销货物，最后返回城市1，若任意两个城市间的距离已知，则该旅行商应如何选择其最佳行走路线？,4,TSP在图论意义下又常常被称为最小Hamilton圈问题，Euler等人最早研究了该问题的雏形，后来由英国的Hamilton爵

2、士作为一个悬赏问题而提出。但这个能让普通人在几分钟内就可理解的游戏之作，却延续至今仍未能完全解决，成了一个世界难题。TSP有着明显的实际意义，如，邮局里负责到各信箱开箱取信的邮递员，以及去各分局送邮件的汽车等，都会遇到类似的问题。有趣的是，还有一些问题表面上看似乎与TSP无关，而实质上却可以归结为TSP来求解。已经证明，TSP是个NP难题，除非P=NP，否则不存在有效算法。,5,记为赋权图G=(V,E)，V为顶点集，E为边集，各顶点间的距离dij已知。设,则经典的TSP可写为如下的数学规划模型：,6,模型中，为集合中所含图的顶点数。约束（71）和（72）意味着对每个点而言，仅有一条边进和一条边

3、出；约束（73）则保证了没有任何子回路解的产生。于是，满足约束（71）、（72）和（73）的解构成了一条Hamilton回路。,7,当dij=dji(i,jV)时，问题被称为对称型TSP，否则称为非对称型TSP。若对所有1i,j,kn，有不等式dij+djk dik成立，则问题被称为是满足三角形不等式的，简称为TSP。,8,2.扩展TSP(1)瓶颈TSP 瓶颈问题是最早从TSP延伸出来的一种扩展型TSP，其含义与经典的TSP类似，仅目标不同，要求巡回路线中经过的最长距离最短，即最小化瓶颈距离。该情形体现了那些并不追求总巡回路线最短，而只希望在巡回路线中每次从一个地点至另一个地点的单次行程尽可能

4、短的实际应用问题的特征。,9,从严格的数学意义而言，瓶颈TSP（简称BTSP）并没有降低问题的难度，也未能提供任何特殊的解决办法。瓶颈TSP的数学模型与标准TSP类似，仅目标函数不同：,由于目标函数为瓶颈值，故求得的最佳巡回路线与标准TSP的往往截然不同。,10,(2)最小比率TSP 最小比率TSP（简称MRTSP）是从经典TSP引申出来的另一个变形问题，假定从一个城市走到另一个城市可得到某种收益（记为），则MRTSP的目标就是确定最佳行走路线，使得回路的总行程与总收益之比最小。这种优化目标的思想类似于人们日常生活中经常使用的费用效益比，与单纯的总行程最短相比，往往更具实际意义。,11,假定收

5、益的数学性质与相同，则最小比率TSP的数学模型也与标准TSP类似，仅目标函数不同：,毫无疑问，由于目标函数中的非线性因素，最小比率TSP的求解比之标准TSP显得更为困难。,12,(3)多人TSP 若标准TSP中，出发点有多个推销员同时出发，各自行走不同的路线，使得所有的城市都至少被访问过一次，然后返回出发点，要求所有推销员的总行程最短，则问题就成为一个多人的旅行商问题（简记MTSP）。令决策变量,则MTSP的数学模型为：,13,假定原问题为对称型MTSP，V=v0,v1,vn-1，v0为名推销员出发点，记V=v01,v02,v0m;v0,v1,vn-1，扩大的m-1个顶点称为“人造顶点”，其距

6、离矩阵也相应扩大，其中，位于出发点的m个顶点相互间的距离设定为，其他数值不变。,14,二、多面体理论 从上世纪70年代开始的关于算法复杂性的研究表明，要想为TSP找到一个好的算法，也即多项式算法，似乎是不可能的。由于推销员的每条路线可以用一个以1开始的排列来表示，因此所有可能的路线有条。这样，若用枚举法来解决这一问题，即使不太大，例如n30，用目前最快的计算机，也要化几百万年才能求出一条最短的路线。,15,早在1954年，Dantzig等人就曾提出过一种方法（非多项式算法），并且求出了一个42城市的TSP最优解。到了1960年代，不少人用分支定界法解决了许多有几十个城市的TSP。还有人提出了一

7、些近似方法，也解决了许多有几十个城市甚至上百个城市的TSP（有时找到的仅是近似解）。更值得注意的是，从1970年代中期开始，Grotschel与Padberg等人深入研究了TS多面体的最大面（facet），并从所得结果出发获得了一种解TSP的新算法，可以解决一些有100多个城市的TSP，且都在不长的时间内找到了最优解。,16,考虑个顶点的完全图Kn，则解TSP就相当于在中求一条总长度最短的Hamilton回路。现在，对每条边ej，定义一个变量xj与之对应，这样，TSP的一条路线T，即Kn的一条Hamilton回路，就可对应一个向量X=x1,x2,.xm，其中，,17,称X为路线T的关联向量，其

8、m=n(n-2)/2个分量中，恰好有个为1，其余的都为0。图有许多Hamilton回路，设为T1,T2 Ts,，对应的关联向量记为X1,X2 Xs，在m维空间Rm中，考虑这些向量生成的凸包（convex hull）Qn：,18,Qn是Rm中的一个凸多面体，称做TS多面体。显然，Qn是有界的，其极点正好是Kn的Hamilton回路关联向量。研究Qn的面非常重要的，因为根据线性不等式及凸多面体的理论，Qn一定是某一个有限线性不等式组的解集合，或者说，Qn一定是有限多个半空间的交。因此，如果能找出定义Qn的线性不等式组来，就可将TSP作为一个线性规划来解。,19,TS多面体研究中的一个重要问题就是寻

9、找能导出Qn最大面的不等式，Grotschel等人发现了一类很重要的能导出最大面的梳子不等式，并予以了证明。此外，还有其它能导出最大面的不等式，如团树不等式等。可见，Qn的最大面极多，曾经计算过由梳子不等式所导出的最大面个数如表71所示：,表71,20,可以看出，当增大时，最大面个数增长得非常快。在TS多面体理论的基础上，可以考虑先解TSP的松弛问题，如果得到的最优解正好是某一条路线的关联向量，那么就找到TSP的最优解了；否则，就设法找一些新的不等式作为额外约束，再解新的线性规划，直至找到恰好是关联向量的最优解。这种做法的基本思想与解整数规划的割平面法是同一类的，Gotschel 等人曾用这种

10、方法解过有120个城市的TSP，所增加的不等式只有子回路消去不等式与梳子不等式两类，在进行了13轮计算后，即解了13个线性规划后，就找到了TSP的精确最优解，每一轮的当时计算时间仅在30秒至2分钟之间。有趣的是，当n=120时，仅梳子不等式就有2*10179个，但在计算过程中，总共却只（凭经验）添加了96个子回路消去不等式与梳子不等式。,21,当然，用该方法有时会找不到TSP的最优解，因为很可能在进行了几轮迭代后，却找不到新的不等式。Padborg与Hong曾计算了74个TSP，其中54个得到了最优解，其余的虽未得到最优解，却得到了很好的下界，如果与近似方法配合，可以估计近似解的精确程度。如，

11、他们解过一个有313个城市的TSP，获得一个下界41236.46，而用近似方法能得到一条长为41349的路线，于是可估计出所得近似解与最优解的误差不超过0.26%。,22,7-2 求解算法,一、下界和上界算法1.下界（1）下界b1和b2 针对TSP对应图的邻接矩阵，将矩阵中每一行最小的元素相加，就可得到一个简单的下界b1。经进一步改进，可得到更好的下界：考虑一个TSP的完整解，在每条路径上，每个城市都有两条邻接边，一条进，一条出，那么，如果把矩阵中每一行最小的两个元素相加再除以2（不失一般性，可假定图中所有距离权重都为整数），再对其结果向上取整，就可得到一个合理的下界b2。显然，b2b1，因此

12、，一般不采用b1作为TSP的下界。,23,例1 已知TSP及其距离矩阵如图71所示，试求其下界,24,解：将矩阵中每一行最小的元素相加，1+3+1+3+2=10，即得b1=10。将矩阵中每一行最小的两个元素相加再除以2，再对结果向上取整，即可得b2=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14。,25,（2）下界b3为便于描述下界b3，先定义如下符号：T：对称TSP问题；n：结点总个数；w(i,j)：结点i与j之间距离；dmin(i,k)：与第i个结点关联的所有边中第k(k=1,2,3)长边的长度；dmin_j(i,k)：与第i个结点关联的所有边中第k(k=1,2,3)

13、长边的另一个结点的编号(其中一个结点编号为i)；node_ base(i)=dmin_j(i,1)+dmin_j(i,2)：表示与i点关联边中长度最短的两条边之和；C*(T)：最优回路长度；,26,于是，dmin(i,1)代表与第i个结点关联的所有边中最长边的长度，dmin_j(i,1)代表与第i个结点关联的所有边中次长边的另一个结点编号(其中一个结点编号为i)，第i结点的dmin(i,k)和dmin_j(i,k)可由距离矩阵w轻易求得。通过对下界b2进行改进，可以得出一个求对称型TSP更好的下界b3。在求b2的过程中，只有当与每一结点关联的边中长度最小的两条边都出现在最优TSP回路中时，等号

14、才成立，下面就来分析如何提高这个下界。,27,对结点i而言，设e(i)1与e(i)2分别为与结点i关联的边中长度最小的两条边，其长度分别为dmin(i,1)和dmin(i,2)。在对称型TSP回路中，由于有且仅有两条边与每一结点关联，因此，并不是与每个结点关联的最小两条边都能出现在最优TSP回路中，这意味可以在node_ base(i)的基础上增加TSP回路的长度，将在这种情况下增加的长度记为Adjust(T)，现在分析如何计算Adjust(T)。,28,对结点i的e(i)1，边e(i)1的一个结点为i，另一个结点为j=dmin_j(i,1)，若e(i)1也是结点j关联边中最小的两条边之一，即

15、 i=dmin_j(j,1)或 i=dmin_j(j,2)，则对边e(i)1来说就不需要调整，否则按以下方式调整：,29,若e(i)1不是结点j=dmin_j(i,1)关联边中最小的两条边之一，则只有以下两种情况：选中e(i)1到TSP回路中 此时对结点i不需调整，对结点j来说，由于边e(i)1出现在最优回路中，而e(i)1不是结点j关联边中最小的两条边之一，因此会造成结点j关联边中最小的两条边中至少有一条不会出现在最优回路中，从而对结点j而言，在node_base(i)的基础上至少会增加的长度为 dmin(i,1)dmin(j,2)。,30,不选中e(i)1到TSP回路中 此时对结点i需要调

16、整，由于边e(i)1不在回路中，故其在node_base(i)的基础上至少会增加的长度为 dmin(i,3)dmin(i,1)。此时对结点j来说，由于与它关联的最短两条边仍然可能在回路中，因此不须调整。,31,对于和，必须有且仅有一种情况出现，现取两种情况中增加长度小的值，因而回路的长路一定会在b2的基础上增加：add_node(i,1)=1/2*min(dmin(i,3)dmin(i,1),dmin(i,1)dmin(j,2)。对结点i的e(i)2，边e(i)2的一个结点为i，另一个结点为j=dmin_j(i,2)，若e(i)2也是结点j关联边中最小的两条边之一，则对边e(i)2来说不需要调

17、整，否则按与前面类似的方法计算调整值。经分析，其在base(T)的基础上至少要增加：add_node(i,2)=1/2*min(dmin(i,3)dmin(i,2),dmin(i,2)dmin(j,2)。,32,将每个结点都按上述方法进行一次调整，其调整累加和就是Adjust(T)，可写成如下公式：,33,将问题T中所有结点的基本长度node_base(T)累加之和的一半称为T的基本长度，并用base(T)来表示，可写成如下公式：,34,于是，有C*(T)base(T)+Adjust(T)=b3，即 b3=b2+Adjust(T)。由以上分析，不难得出求对称TSP下界b3的算法：,35,Ste

18、p 1.计算base(T)：get_base()i:Long For i=1 To n base=base+dmin(i,1)+dmin(i,2),36,Step 2.计算Adjust(T)：get_adjust()i,ii1,ii2:Long For i=1 To n ii1=dmin_j(i,1);ii2=dmin_j(i,2)If i dmin_j(ii1,1)And i dmin_j(ii1,2)adjust=adjust+min(dmin(i,3)-dmin(i,1),dmin(i,1)-dmin(ii1,2)If i dmin_j(ii2,1)And i dmin_j(ii2,2)

19、adjust=adjust+min(dmin(i,3)-dmin(i,2),dmin(i,2)-dmin(ii2,2),37,对例1而言，可计算其b3如下：dmin(1,1)=1；dmin_j(1,1)=3；dmin(1,2)=3；dmin_j(1,2)=2；dmin(1,3)=5；dmin_j(1,3)=4；dmin(2,1)=3；dmin_j(2,1)=1；dmin(2,2)=6；dmin_j(2,2)=3；dmin(2,3)=7；dmin_j(2,3)=4；dmin(3,1)=1；dmin_j(3,1)=1；dmin(3,2)=2；dmin_j(3,2)=5；dmin(3,3)=4；dm

20、in_j(3,3)=4；,38,dmin(4,1)=3；dmin_j(4,1)=5；dmin(4,2)=4；dmin_j(4,2)=3；dmin(4,3)=5；dmin_j(4,3)=1；dmin(5,1)=2；dmin_j(5,1)=3；dmin(5,2)=3；dmin_j(5,2)=4；dmin(5,3)=8；dmin_j(5,3)=1；,39,add_node(1,1)=0;add_node(1,2)=0;add_node(2,1)=0;add_node(2,2)=1/2min(7-6),(6-2)=1/2;add_node(3,1)=0;add_node(3,2)=1/2min(5-4

21、),(4-2)=1/2;add_node(4,1)=0;add_node(4,2)=0;add_node(5,1)=0;add_node(5,2)=0;所以，Adjust(T)=1/2+1/2=1，得b3=b2+Adjust(T)=14+1=15。,40,2.上界 事实上，TSP的任何可行解都是上界，这里，给出求TSP上界U1的贪心方法思想。算法步骤如下：,41,Step 1.图G=V,E中顶点个数为n=|V|，边的条数m=|E|，令i为出发点，TSP_edge_n为加入到TSP回路中边的条数且TSP_edge_n=0，TSP_edge为已加入到TSP回路中的边集合且TSP_edge=，k为当

22、前顶点且k=i。Step 2.从边集,中选中一条代价最小的一条边(k,h)，并执行 TSP_edge_n=TSP_edge_n+1；TSP_edge=TSP_edge+(k,h)；k=h。Step 3.若TSP_edge_n(n-1)，则转Step 2。Step 4.将边(k,i)加入到TSP_edge中。,42,求解结束后，TSP_edge中的边都在TSP回路中。对例1，可用上述算法求得其路径为：135421，路径长度1+2+3+7+3=16，这是TSP的一个上界U1。综合上下界，就可得到例1目标函数的界为 15,16。,43,二、分支定界法,二、分支定界法 分支定界法是一种在表示问题解空间

23、的树上进行系统搜索的精确算法，这里，介绍两种求解TSP的分支定界方法。,44,.基于上下界的分支定界法为用分支定界法求解TSP，需要计算某些边在TSP回路中和某些边不在TSP回路中等情况下的下界。若采用下界b2计算，由于每个顶点最多只有两个关联边在TSP回路中，已在TSP回路中的边则限制该边的其它邻接边加入，因此，针对每个顶点，分4种情况来计算：,45,(1)若某顶点没有关联边在TSP回路中，则该顶点的计算方法与计算b2的方法相同，即把该顶点关联的最短两边长度之和的一半加入到下界中；(2)若某顶点关联的边已有两条边e1和e2在TSP回路中，则不需要再加入与该顶点关联最小两条边的长度，即此时把e

24、1和e2长度之和的一半加入到下界中；(3)若某顶点关联的边已有一条边e1在TSP回路中，则只需要再加入与该顶点关联的最小边长度，即把e1和该顶点关联的最短一条边的长度之和的一半加入到下界中；(4)若某顶点关联边集的子集E1不能出现在TSP回路中，则将E1从图中删除再计算b2即可；如某顶点已有两关联边在回路中，则可将其它关联边删除，同样，可以将会与已加入到回路中的边形成子圈的边删除。,46,如例1中所示的无向图，若其TSP回路包含边(1,4)，则该部分解的下界b2=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16，此时计算其下界时，由于边(1,4)已在回路中，故与顶点1关联的

25、边只需再加入一条最短边(1,3)。若TSP回路包含边(1,2)和(2,4)，则这时的下界b2=(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16。,47,为描述方便，用eij=1表示边(i,j)在TSP回路中，eij=0表示边(i,j)不在TSP回路中。下面给出用分支定界法求解例1的过程（如图72所示）：,48,49,(1)用贪心算法求得上界U1=16；(2)假定边(1,3)不在TSP回路中，即e13=0，此时，b2=(5+3)+(3+6)+(4+2)+(3+4)+(2+3)/2=17.5，由于b2=17.5 U1=16，因此边(1,3)一定在回路中，即e13=1；(3)在e

26、13=1的情况下，假定e12=0，此时b2=(1+5)+(6+7)+(1+2)+(3+4)+(2+3)/2=17，由于b2=17 U1=16，因此边(1,2)一定在回路中，即e12=1；,50,(4)在e12=e13=1的情况下，由于顶点1已有两条关联边在最优回路中，因此在图71中删去边(1,4)和(1,5)，由于边(2,3)与边(1,2)、(1,3)形成圈，因此在图71中删去边(2,3)，即此时e14=e15=e23=0；(5)在e12=e13=1，e14=e15=e23=0的情况下，假定e25=1，此时b2=(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=18.5，由于b2

27、=18.5 U1=16，因此边(2,5)一定不在回路中，即e25=0；,51,在e12=e13=1，e14=e15=e23=e25=0的情况下，由于与顶点2关联的边有且只有2条在回路中，因此有e24=1，进而有e35=e54=1，e34=0。至此，得到 最优解：e12=e13=e24=e35=e54=1，e14=e15=e23=e25=e34=0；最优目标值：1+2+3+7+3=16。,52,2.基于降阶的分支定界法 对于有向TSP的距离距阵，可通过不同情况下上下界的对比来确定某些边(i,j)一定在或不在回路中。如果能确定(i,j)一定在回路中，由于每个顶点分别有且只有一条入边和出边，从而可确

28、定顶点i的其它出边一定不在回路中，也可以确定顶点j的其它出边一定不在回路中，因此可将这些边从距离距阵中去掉，从而达到降低矩阵阶数的目的。这里，以一个具体的例子来予以说明。,53,例2 已知有向TSP的距离矩阵如下：,54,解:由于每个顶点都必须有一条入边和出边，因此将顶点i的所有出边的权值减去所有出边权值的最小值min_out(i)，不会影响最优解，仅最优值在原来的基础上减少了min_out(i)。于是，可以将距离矩阵的每一行和每一列都减去该行或该列的最小值，直至每行每列都含有0为止。将上述矩阵的每行分别减去该行的最小值3,4,16,7,25,3，就得到如下缩减之后的矩阵：,55,该缩减矩阵所

29、对应TSP的最优解与原来的相同，但最优值比原来减少了3+4+16+7+25+3=58。由于矩阵中第3、4列中不含0元素，因此可继续缩减成：,56,该缩减矩阵所对应TSP的最优解与原来的相同，但最优值比原来减少了3+4+16+7+25+3=58。由于矩阵中第3、4列中不含0元素，因此可继续缩减成：,57,其最优值比原来减少58+15+8=81，这个81可作为该TSP初始的下界值b。,58,按e63=1和e63=0将解分成两种情况：(1)e63=0 此时，边(6,3)不能出现在回路中，其权值在这种情况下为，因此，距离矩阵可修改为：,59,由于第3列没有0元素，故用第3列各元素减去其最小元素48，得

30、如下缩减矩阵：,此时的下界 b=81+48=129。,60,(2)e63=1 此时，边(6,3)已出现在回路中，从顶点6出发的其它边都不可能在回路中，因此可删去第6行；同理，进入到顶点3的其它边都不可能在回路中，因此又可删去第3列。此时，边(3,6)不可能出现在回路中，令边(3,6)的权值为，矩阵化为：,61,继续依次计算，并实施分支和定界，具体过程如图73所示：,图73 降阶分支定界过程,62,e63=1，e46=0下的缩减矩阵：,63,e63=e46=1下的缩减矩阵：,64,e63=e46=1，e21=0下的缩减矩阵：,65,e63=e46=e21=1下的缩减矩阵：,66,e63=e46=

31、e21=1，e14=0下的缩减矩阵：,67,e63=e46=e21=e14=1下的缩减矩阵：,68,e63=e46=1，e21=e51=0下的缩减矩阵：,69,e63=e46=e51=1，e21=0下的缩减矩阵：,70,e63=e46=e51=1，e21=e14=0下的缩减矩阵：,71,e63=e46=e51=e14=1，e21=0下的缩减矩阵：,72,最后可得到两个最优TSP回路：(1,4,6,3,2,5,1)和(1,4,6,3,5,2,1)，最优回路长度为104。若将无向图中的每条边看成有向图中方向相反的两条边，则无向图也可看成是有向图，因此，基于降阶的分支定界法也可用来求解无向TSP问题

32、。,73,三、动态规划法,定理1 TSP满足最优性原理。最优化原理可以表述为：“一个过程的最优策略具有这样的性质,即无论初始状态和初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成最优策略，”,74,证：设s,s1,s2,sp,s是从s出发的一条总长最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1,s2,sp,s一定构成一条从s1到s的最短路径。若不然，设s1,r1,r2,rq,s是一条从s1到s的最短路径且经过n-1个不同城市，则s,s1,r1,r2,rq,s将是一条从s出发的路径长度最短的简单回路且比s,s1,s2,sp,s要短

33、，从而导致矛盾。所以，TSP满足最优性原理。,75,设TSP顶点编号分别为0，1，2，n，假设从顶点0出发，令d(i,V)表示从顶点 i 出发经过V 中各顶点一次且仅一次，最后回到出发点0的最短路径长度，中间计算过程中的d(k,Vk)也表示从顶点 k 出发经过Vk 中各顶点一次且仅一次，最后回到出发点0（注意不是k）的最短路径长度。开始时，V=Vi，cij为顶点 i 至顶点 j 的距离，于是，TSP的动态规划递推函数可写成：,76,d(i,V)=min cik+d(k,Vk)(kV)d(k,)=ck 0(k 0),例3 求解有向TSP：,77,解：从城市0出发经城市1、2、3然后回到城市0的最

34、短路径长度为：d(0,1,2,3)=min c01+d(1,2,3),c02+d(2,1,3),c03+d(3,1,2)这是最后一个阶段的决策，而d(1,2,3)=min c12+d(2,3),c13+d(3,2)，d(2,1,3)=min c21+d(1,3),c23+d(3,1)，d(3,1,2)=min c31+d(1,2),c32+d(2,1)；这一阶段的决策又依赖于下述计算结果：,78,d(1,2)=c12+d(2,)，d(2,3)=c23+d(3,)，d(3,2)=c32+d(2,)，d(1,3)=c13+d(3,)，d(2,1)=c21+d(1,)，d(3,1)=c31+d(1,

35、)；而下式可以直接获得（括号中是该决策引起的状态转移）：d(1,)=c10=5(10)，d(2,)=c20=6(20)，d(3,)=c30=3(30)；,79,再向前倒推，有：d(1,2)=c12+d(2,)=2+6=8(12)，d(1,3)=c13+d(3,)=3+3=6(13)，d(2,3)=c23+d(3,)=2+3=5(23)，d(2,1)=c21+d(1,)=4+5=9(21)，d(3,1)=c31+d(1,)=7+5=12(31)，d(3,2)=c32+d(2,)=5+6=11(32)；,80,再向前倒推，有：d(1,2,3)=min c12+d(2,3),c13+d(3,2)=m

36、in 2+5,3+11=7(12)，d(2,1,3)=min c21+d(1,3),c23+d(3,1)=min 4+6,2+12=10(21)，d(3,1,2)=min c31+d(1,2),c32+d(2,1)=min 7+8,5+9=14(32)；,81,最后有：d(0,1,2,3)=min c01+d(1,2,3),c02+d(2,1,3),c03+d(3,1,2)=min 3+7,6+10,7+14=10(01)。即，从顶点0出发的TSP最短回路长度为10，回路路径为：01230。,82,四、近似算法,由于精确式算法所能求解的问题规模非常有限，实际中真正使用的往往都是多项式阶数的近似

37、算法或启发式算法，算法的好坏用C/C*来衡量，其中，C为近似算法所得的总行程，C*为最优总行程，为最“坏“情况下近似与最优总行程之比所不超过的上界值。这里，列举几个常见的TSP快速近似算法。,83,旅行售货员问题的一些特殊性质：比如，费用函数w往往具有三角不等式性质，即对任意的3个顶点u,v,wV，有：w(u,w)w(u,v)+w(v,w)。当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数w就具有三角不等式性质。,对于给定的无向图G，可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。,84,当费用函数满足三角不等式时，算法找出的旅行售货员回

38、路的费用不会超过最优旅行售货员回路费用的2倍。,void approxTSP(Graph g)(1)选择g的任一顶点r；(2)用Prim算法找出带权图g的一棵以r为根的最小生成树T；(3)前序遍历树T得到的顶点表L；(4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；,85,(b)表示找到的最小生成树T；,(c)表示对T作前序遍历的次序；,(d)表示L产生的哈密顿回路H；,(e)是G的一个最小费用旅行售货员回路。,为什么：当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。,86,答：存在一个最优TSP回路TSPOPT，TSPOP

39、T中共有n条边，现去掉TOPT中最长的一条边，得路径POPT，POPT中共有n-1条边，其总权值之和WTSP大于等于最小生成树的总权值之和WT；即WTSP WT,下面只需证明该算法求得的TSP回路总长度之和WA小于等于2WT即可；把最小生成树中的边重复一次，再根据三角不等式就可得出结论（多次利用三角不等式）。,为什么：当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。,87,把最小生成树中的边重复一次，再根据三角不等式就可得出结论（多次利用三角不等式）。（d）中蓝色的边为原来不在最小生成树中的边，最小生成树中的边重复一次及不在(d)中，但在(b)中

40、的边反复利用三角不等式就可得出结论。,88,1.插入算法插入型算法可按插入规则的不同而分为若干类，其一般思想为：Step 1.通过某种插入方式选择插入边(i,j)和插入点 k，将 k 插入 i 和 j 之间,形成,i,k,j,。Step 2.依次进行，直至形成回路解。适用范围：对称型TSP。具体实施中，可将出发点取遍V中各点而得到多个解，并从中选择最好的一个，但此时的时间复杂度增加了n倍。主要的插入型算法有：,89,(1)最近插入法最坏情况：=2；时间复杂度：O(n2)。(2)最小插入法最坏情况：=2；时间复杂度：O(n2 lg n)。(3)任意插入法最坏情况：=2 1g n+0.16；时间复

41、杂度：O(n2)。(4)最远插入法最坏情况：=2 1g n+0.16；时间复杂度：O(n2)。(5)凸核插入法最坏情况：=未知；时间复杂度：O(n2lg n)。,90,插入法(Insertion Method),1 任选一节点为起点a；2 寻找距离节点a最近的节点b作为下一个造访的节点，形成a-b-a的子回路；3 寻找距离子回路最近的节点k作为下一个插入点；4 寻找插入成本最小的位置(i-j)，将k插入i-j之间，形成新的子回路；插入成本：Cik+Ckj-Cij5 重复步骤34，直到所有节点均已插入回路之中，即形成一个TSP的可行解。,91,插入法,1,4,2,3,5,7,4,3,8,7,5,

42、5,3,4,8,1,4,1,4,1,3,3,3,2,5,1 任选一节点为起点a；2 寻找距离节点a最近的节点b作为下一个造访的节点，形成a-b-a的子回路；3 寻找距离子回路最近的节点k作为下一个插入点；4 寻找插入成本最小的位置(i-j)，将k插入i-j之间，形成新的子回路；插入成本：Cik+Ckj-Cij5 重复步骤34，直到所有节点均已插入回路之中，即形成一个TSP的可行解。,92,2.最近邻算法Step 1.任取一出发点。Step 2.依次取最近的点加入当前解中，直至形成回路解。适用范围：对称型TSP。具体实施中，可将出发点取遍V中各点而得到多个解，从中选择最好的一个，但此时的时间复杂

43、度增加了n倍。最坏情况：=(1g n+1)/2；时间复杂度：O(n2)。,93,最近邻点法(Nearest-neighbor Heuristic),1 任选一节点为起点x；2 寻找距离节点x最近的节点y作为下一个造访的节点；3 寻找距离节点y最近的节点z作为下一个造访的节点；4 重复以上步骤，直到所有节点均已访问；5 连接最后一个节点与起点，即形成一个TSP的可行解；,94,最近邻点法,1,4,2,3,5,7,4,3,8,7,5,5,3,4,8,1,4,2,3,5,95,3.双生成树算法Step 1.首先求出最小生成树。Step 2.将树中各边都添一重复边形成Euler图，并求出其Euler回

44、路。Step 3.在Euler回路点序列中去除重复点，形成TSP回路解。适用范围：对称型TSP。最坏情况：=2；时间复杂度：O(n2)。,96,4 Christofides算法Step 1.首先求出最小生成树。Step 2.对树中所有奇顶点求解最小权匹配问题。Step 3.将匹配边添入生成树，并求出其Euler回路。Step 4.在Euler回路点序列中去除重复点，形成TSP回路解。适用范围：对称型TSP。最坏情况：=3/2；时间复杂度：O(n3)。,97,5.r-opt 算法 该方法是一种局部改进搜索算法，由Lin等人（1965）提出，其核心思想就是对给定的初始回路，通过每次交换 r 条边来

45、改进当前的解。适用范围：对称型TSP。显然，对不同的r，其优劣次序为：2-opt，3-optr-opt。但是，大量计算发现，3-opt比2-opt好，而4-opt、5-opt等却并不比3-opt来得优越，况且r越大，运算时间越长。对于3-opt，有一个经验公式告诉我们，其求得最优解的概率近似为2-n/10，例如，对于n=50,有 p=2-50/10=0.03，即，只要随机选取150条初始路线，则求得最优解的概率可达0.99。迄今为止，3-opt法仍是一种相当有效的近似算法。最坏情况:=2(n8,rn/4)；时间复杂度：O(nr)。,98,6.混合算法 用某个近似算法求得初始解，然后借助一个或若

46、干个r-opt算法对解加以改进。这种混合型的算法往往能获得较好的解，但同时也很耗时，一般仅在对解有较高要求时采用。,99,2-opt 交換法,先构建一个起始可行解在可行解中任选两个不相邻的节线(a b,c d)，以及另外两条对应之替换节线(a c,b d)，计算替换后总成本是否降低(即检查替换成本是否小于0)。替换成本：Cac+Cbd-Cab-Ccd(对称型TSP)若替换后总成本有降低，则予以替换，同时变更中间相关弧线的行走方向。重复步骤23，直到所有可能的替换均无法再降低成本为止,100,2-opt 交換法,1,4,2,3,5,7,4,3,8,7,5,5,3,4,8,101,如：98年全国数学建模竞赛题B题是TSP问题的一个变形,从县城出发分三个小组巡视受灾的地区各地的灾情，已知每个村镇所需要的停留时间以及行车速度，问如何设计各组的巡视路线才能以最快的速度掌握整个地区全部的受灾情况？,102,灾情巡视路线(CUMCM-1998B),多人TSP问题的扩展,103,考虑用一个3个结点来代替县城结点，将问题转化为一个TSP问题：,