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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,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,爵士作为一个悬赏问题而提出。但这个能让普通人在几分钟内就可理解的游戏之作，却延续至今仍未能完全解决，成了一个世界难题。,TSP,有着明显的实际意义，如，邮局里负责到各信箱开箱取信的邮递员，以及去各分局送邮件的汽车等，都会遇到类似的问题。有趣的是，还有一些问题表面上看似乎与,TSP,无关，而实质上却可以归结为,TSP,来求解。已经证明，,TSP,是个,NP,难题，除非,P=NP,，否则不存在有效算法。,5,记为赋权图,GV,E,),，,V,为顶点集，,E,为边集，各顶点间的距离,d,ij,已知。设,则经典的,TSP,可写为如下的数学规划模型：,6,模型中，为集合中所含图的顶点数。约束（,7,1,）和（,7,2,）意味着对每个点而言，仅有一条边进和一条边出；约束（,7,3,）则保证了没有任何子回路解的产生。于是，满足约束（,7,1,）、（,7,2,）和（,7,3,）的解构成了一条,Hamilton,回路。,9,从严格的数学意义而言，瓶颈,TSP,（简称,BTSP,）并没有降低问题的难度，也未能提供任何特殊的解决办法。,瓶颈,TSP,的数学模型与标准,TSP,类似，仅目标函数不同：,由于目标函数为瓶颈值，故求得的最佳巡回路线与标准,TSP,的往往截然不同。,10,(2),最小比率,TSP,最小比率,TSP,（简称,MRTSP,）是从经典,TSP,引申出来的另一个变形问题,，假定从一个城市走到另一个城市可得到某种收益（记为），则,MRTSP,的目标就是确定最佳行走路线,，使得回路的总行程与总收益之比最小。这种优化目标的思想类似于人们日常生活中经常使用的费用效益比，与单纯的总行程最短相比，往往更具实际意义。,11,假定收益的数学性质与相同，则最小比率,TSP,的数学模型也与标准,TSP,类似，仅目标函数不同：,毫无疑问，由于目标函数中的非线性因素，最小比率,TSP,的求解比之标准,TSP,显得更为困难。,12,(3),多人,TSP,若标准,TSP,中,，出发点有多个推销员同时出发，各自行走不同的路线，使得所有的城市都至少被访问过一次，然后返回出发点，要求所有推销员的总行程最短，则问题就成为一个多人的旅行商问题（简记,MTSP,）。,令决策变量,则,MTSP,的数学模型为：,13,假定原问题为对称型,MTSP,，,V,=,v,0,v,1,v,n-1,，,v,0,为名推销员出发点，记,V,=,v,01,v,02,v,0m;,v,0,v,1,v,n-1,，扩大的,m-1,个顶点称为“人造顶点”，其距离矩阵也相应扩大，其中，位于出发点的,m,个顶点相互间的距离设定为，其他数值不变。,14,二、多面体理论,从上世纪,70,年代开始的关于算法复杂性的研究表明，要想为,TSP,找到一个好的算法，也即多项式算法，似乎是不可能的。由于推销员的每条路线可以用一个以,1,开始的排列来表示，因此所有可能的路线有条。这样，若用枚举法来解决这一问题，即使不太大，例如,n,30,，用目前最快的计算机，也要化几百万年才能求出一条最短的路线。,15,早在,1954,年，,Dantzig,等人就曾提出过一种方法（非多项式算法），并且求出了一个,42,城市的,TSP,最优解。到了,1960,年代，不少人用分支定界法解决了许多有几十个城市的,TSP,。还有人提出了一些近似方法，也解决了许多有几十个城市甚至上百个城市的,TSP,（有时找到的仅是近似解）。更值得注意的是，从,1970,年代中期开始，,Grotschel,与,Padberg,等人深入研究了,TS,多面体的最大面,（,facet,），并从所得结果出发获得了一种解,TSP,的新算法，可以解决一些有,100,多个城市的,TSP,，且都在不长的时间内找到了最优解。,16,考虑个顶点的完全图,K,n,，则解,TSP,就相当于在中求一条总长度最短的,Hamilton,回路。现在，对每条边,e,j,，定义一个变量,x,j,与之对应，这样，,TSP,的一条路线,T,，即,K,n,的一条,Hamilton,回路，就可对应一个向量,X,=,x,1,x,2,.,x,m,，其中，,17,称,X,为路线,T,的关联向量，其,m=,n,(n-2)/2,个分量中，恰好有个为,1,，其余的都为,0,。,图有许多,Hamilton,回路，设为,T,1,T,2,T,s,，对应的关联向量记为,X,1,X,2,X,s,，在,m,维空间,R,m,中，考虑这些向量生成的凸包（,convex hull,）,Q,n,：,18,Q,n,是,R,m,中的一个凸多面体，称做,TS,多面体。显然，,Q,n,是有界的，其极点正好是,K,n,的,Hamilton,回路关联向量。,研究,Q,n,的面非常重要的，因为根据线性不等式及凸多面体的理论，,Q,n,一定是某一个有限线性不等式组的解集合，或者说，,Q,n,一定是有限多个半空间的交。因此，如果能找出定义,Q,n,的线性不等式组来，就可将,TSP,作为一个线性规划来解。,19,TS,多面体研究中的一个重要问题就是寻找能导出,Q,n,最大面的不等式，,Grotschel,等人发现了一类很重要的能导出最大面的梳子不等式，并予以了证明。此外，还有其它能导出最大面的不等式，如团树不等式等。可见，,Q,n,的最大面极多，曾经计算过由梳子不等式所导出的最大面个数如表,7,1,所示：,n,6,8,10,20,30,50,120,c(n),60,41420,8841970,1.5*10,18,1.5*10,31,10,60,2*10,179,表,7,1,20,可以看出，当增大时，最大面个数增长得非常快。,在,TS,多面体理论的基础上，可以考虑先解,TSP,的松弛问题，如果得到的最优解正好是某一条路线的关联向量，那么就找到,TSP,的最优解了；否则，就设法找一些新的不等式作为额外约束，再解新的线性规划，直至找到恰好是关联向量的最优解。这种做法的基本思想与解整数规划的割平面法是同一类的，,Gotschel,等人曾用这种方法解过有,120,个城市的,TSP,，所增加的不等式只有子回路消去不等式与梳子不等式两类，在进行了,13,轮计算后，即解了,13,个线性规划后，就找到了,TSP,的精确最优解，每一轮的当时计算时间仅在,30,秒至,2,分钟之间。有趣的是，当,n=120,时，仅梳子不等式就有,2*10179,个，但在计算过程中，总共却只（凭经验）添加了,96,个子回路消去不等式与梳子不等式。,21,当然，用该方法有时会,找不到,TSP,的最优解，因为很可能在进行了几轮迭代后，却找不到新的不等式。,Padborg,与,Hong,曾计算了,74,个,TSP,，其中,54,个得到了最优解，其余的虽未得到最优解，却得到了很好的下界，如果与近似方法配合，可以估计近似解的精确程度。如，他们解过一个有,313,个城市的,TSP,，获得一个下界,41236.46,，而用近似方法能得到一条长为,41349,的路线，于是可估计出所得近似解与最优解的误差不超过,0.26%,。,22,7-2,求解算法,一、下界和上界算法,1.,下界,（,1,）下界,b,1,和,b,2,针对,TSP,对应图的邻接矩阵，将矩阵中每一行最小的元素相加，就可得到一个简单的下界,b,1,。经进一步改进，可得到更好的下界：考虑一个,TSP,的完整解，在每条路径上，每个城市都有两条邻接边，一条进，一条出，那么，如果把矩阵中每一行最小的两个元素相加再除以,2,（不失一般性，可假定图中所有距离权重都为整数），再对其结果向上取整，就可得到一个合理的下界,b,2,。,显然，,b,2,b,1,，因此，一般不采用,b,1,作为,TSP,的下界。,23,例,1,已知,TSP,及其距离矩阵如图,7,1,所示，试求其下界,2,7,1,5,6,3,1,3,4,2,5,3,9,8,4,(a),无向图,图,7,1,无向图及距离矩阵,(b),距离矩阵,24,解：,将矩阵中每一行最小的元素相加，,1+3+1+3+2=10,，即得,b,1,=10,。将矩阵中每一行最小的两个元素相加再除以,2,，再对结果向上取整，即可得,b,2,=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14,。,25,（,2,）下界,b,3,为便于描述下界,b,3,，先定义如下符号：,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),长边的另一个结点的编号,(,其中一个结点编号为,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,轻易求得。,通过对下界,b,2,进行改进，可以得出一个求对称型,TSP,更好的下界,b,3,。,在求,b,2,的过程中，只有当与每一结点关联的边中长度最小的两条边都出现在最优,TSP,回路中时，等号才成立，下面就来分析如何提高这个下界。,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,关联边中最小的两条边之一，即,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,需要调整，由于边,e,(,i,)1,不在回路中，故其在,node_base,(,i,),的基础上至少会增加的长度为,dmin,(,i,3),dmin,(,i,1),。,此时对结点,j,来说，由于与它关联的最短两条边仍然可能在回路中，因此不须调整。,31,对于和，必须有且仅有一种情况出现，现取两种情况中增加长度小的值，因而回路的长路一定会在,b,2,的基础上增加：,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,来说不需要调整，否则按与前面类似的方法计算调整值。经分析，其在,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),=,b,3,，即,b,3,=,b,2,+,Adjust(T),。,由以上分析，不难得出求对称,TSP,下界,b,3,的算法：,35,Step 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),adjust=adjust+min(dmin(i,3)-dmin(i,2),dmin(i,2)-dmin(ii2,2),37,对例,1,而言，可计算其,b,3,如下：,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,；,dmin_j,(3,3)=4,；,2,7,1,5,6,3,1,3,4,2,5,3,9,8,4,(a),无向图,图,7,1,无向图,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,；,2,7,1,5,6,3,1,3,4,2,5,3,9,8,4,(a),无向图,图,7,1,无向图,39,add_node,(1,1)=0;,add_node,(1,2)=0;,add_node,(2,1)=0;,add_node,(2,2)=1/2,min(7-6),(6-2)=1/2;,add_node,(3,1)=0;,add_node3,2)=1/2,min(5-4),(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,，得,b,3,=,b,2,+Adjust(,T,)=14+1=15,。,40,2.,上界,事实上，,TSP,的任何可行解都是上界，这里，给出求,TSP,上界,U,1,的贪心方法思想。,算法步骤如下：,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,为,当前顶点,且,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,U,1,故,剪支,e,12,=0,e,12,=1,b,2,=17,U,1,故,剪支,得最优解,e,12,=,e,13,=,e,24,=,e,35,=,e,54,=1,e,14,=,e,15,=,e,23,=,e,25,=,e,34,=0,e,25,=0,e,25,=1,b,2,=18.5,U,1,=16,故,剪支,此时有,e,14,=,e,15,=,e,23,=0,此时有,e,24,=,e,35,=,e,54,=1,e,34,=0,49,(1),用贪心算法求得,上界,U,1,=16,；,(2),假定边,(1,3),不在,TSP,回路中,，即,e,13,=0,，此时，,b,2,=(5+3)+(3+6)+(4+2)+(3+4)+(2+3)/2=17.5,，由于,b,2,=17.5,U,1=16,，因此边,(1,3),一定在回路中，即,e,13,=1,3),在,e,13,=1,的情况下，,假定,e,12,=0,，此时,b,2,=(1+5)+(6+7)+(1+2)+(3+4)+(2+3)/2=17,，由于,b,2,=17,U,1,=16,，因此边,(1,2),一定在回路中，即,e,12,=1,；,50,(4),在,e,12,=,e,13,=1,的情况下，由于顶点,1,已有两条关联边在最优回路中，因此在图,7,1,中,删去,边,(1,4),和,(1,5),，由于边,(2,3),与边,(1,2),、,(1,3),形成圈,，因此在图,7,1,中删去边,(2,3),，即此时,e,14,=,e,15,=,e,23,=0,；,(5),在,e,12,e,13,=1,，,e,14,=,e,15,=,e,23,=0,的情况下，,假定,e,25,=1,，此时,b,2,=(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=18.5,，由于,b,2,=18.5,U,1,=16,，因此边,(2,5),一定不在回路中，即,e,25,=0,；,51,在,e,12,=,e,13,=1,，,e,14,=,e,15,=,e,23,=,e,25,=0,的情况下，由于与顶点,2,关联的边有且只有,2,条在回路中，因此有,e,24,=1,，进而有,e,35,=,e,54,=1,，,e,34,=0,。,至此，得到,最优解：,e,12,=,e,13,=,e,24,=,e,35,=,e,54,=1,，,e,14,=,e,15,=,e,23,=,e,25,=,e,34,=0,；,最优目标值：,1+2+3+7+3=16,。,52,2.,基于降阶的分支定界法,对于,有向,TSP,的距离距阵，可通过不同情况下上下界的对比来确定某些边,(,i,j),一定在或不在回路中。如果能确定,(,i,j),一定在回路中，由于每个顶点分别,有且只有一条入边和出边,，从而可确定顶点,i,的其它出边一定不在回路中，也可以确定顶点,j,的其它出边一定不在回路中，因此可将这些边从距离距阵中去掉，从而达到,降低矩阵阶数,的目的。,这里，以一个具体的例子来予以说明。,53,例,2已知有向,TSP,的距离矩阵如下：,54,解,:,由于每个顶点都必须有一条入边和出边，因此,将顶点,i,的所有出边的权值减去所有出边权值的最小值,min_out,(,i,),，不会影响最优解，仅最优值在原来的基础上减少了,min_out,(,i,),。,于是，可以将距离矩阵的每一行和每一列都减去该行或该列的最小值，直至每行每列都含有,0,为止。,将上述矩阵的每行分别减去该行的最小值,3,4,16,7,25,3,，就得到如下缩减之后的矩阵：,55,该缩减矩阵所对应,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,按,e,63,=1,和,e,63,=0,将解分成两种情况：,(1),e,63,=0,此时，边,(6,3),不能出现在回路中，其权值在这种情况下为，因此，距离矩阵可修改为：,59,由于第,3,列没有,0,元素，故用第,3,列各元素减去其最小元素,48,，得如下缩减矩阵：,此时的下界,b,81+48=129,。,60,(2),e,63,=1,此时，边,(6,3),已出现在回路中，从顶点,6,出发的其它边都不可能在回路中，因此可,删去第,6,行,；同理，进入到顶点,3,的其它边都不可能在回路中，因此又可,删去第,3,列,。此时，边,(3,6),不可能出现在回路中，令边,(3,6),的权值为，矩阵化为：,61,继续依次计算，并实施分支和定界，具体过程如图,7,3,所示：,图,7,3,降阶分支定界过程,b,=81,e,63,=0,e,63,=1,b,=129,e,46,=0,e,46,=1,b,=113,e,21,=0,e,21,=1,b,=81,b,=81,b,=84,b,=101,e,14,=1,e,14,=0,b,=84,b,=112,得可行回路,(1,4,6,3,5,2,1),回路总长,104,，,由此可将下界,b,大于,104,的分支剪去。,62,e,63,=1,，,e,46,=0,下的缩减矩阵：,63,e,63,=,e,46,=1,下的缩减矩阵：,64,e,63,=,e,46,=1,，,e,21,=0,下的缩减矩阵：,65,e,63,=,e,46,=,e,21,=1,下的缩减矩阵：,66,e,63,=,e,46,=,e,21,=1,，,e,14,=0,下的缩减矩阵：,67,e,63,=,e,46,=,e,21,=,e,14,=1,下的缩减矩阵：,68,e,63,=,e,46,=1,，,e,21,=,e,51,=0,下的缩减矩阵：,69,e,63,=,e,46,=,e,51,=1,，,e,21,=0,下的缩减矩阵：,70,e,63,=,e,46,=,e,51,=1,，,e,21,=,e,14,=0,下的缩减矩阵：,71,e,63,=,e,46,=,e,51,=,e,14,=1,，,e,21,=0,下的缩减矩阵：,72,最后可得到两个最优,TSP,回路：,(1,4,6,3,2,5,1),和,(1,4,6,3,5,2,1),，最优回路长度为,104,。,若将无向图中的每条边看成有向图中方向相反的两条边，则无向图也可看成是有向图，因此，基于降阶的分支定界法也可用来求解无向,TSP,问题。,73,三、动态规划法,定理,1 TSP,满足,最优性原理,。,最优化原理,可以表述为：“一个过程的最优策略具有这样的性质,即无论初始状态和初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成最优策略，”,74,证：,设,s,s,1,s,2,s,p,s,是从,s,出发的一条总长最短的简单回路，假设从,s,到下一个城市,s,1,已经求出，则问题转化为求从,s,1,到,s,的最短路径，显然,s,1,s,2,s,p,s,一定构成一条从,s,1,到,s,的最短路径。若不然，设,s,1,r,1,r,2,r,q,s,是一条从,s,1,到,s,的最短路径且经过n,-1,个不同城市，则,s,s,1,r,1,r,2,r,q,s,将是一条从,s,出发的路径长度最短的简单回路且比,s,s,1,s,2,s,p,s,要短，从而导致矛盾。所以，,TSP,满足最优性原理。,75,设,TSP,顶点编号分别为,0,，,1,，,2,，,，,n,，假设从顶点,0,出发，令,d,(,i,V,),表示从顶点,i,出发经过,V,中各顶点一次且仅一次，最后回到出发点,0,的最短路径长度，中间计算过程中的,d,(,k,V,k,),也表示从顶点,k,出发经过,V,k,中各顶点一次且仅一次，最后回到出发点,0,（注意不是,k,）的最短路径长度。开始时，,V,=,V,i,，,c,ij,为顶点,i,至顶点,j,的距离，于是，,TSP,的动态规划递推函数可写成：,76,d,(,i,V,)=min,c,ik,+,d,(,k,V,k,)(,k,V,),d,(,k,)=,c,k,0,(,k,0,),例,3,求解有向,TSP,：,77,解：,从城市,0,出发经城市,1,、,2,、,3,然后回到城市,0,的最短路径长度为：,d,(0,1,2,3)=min,c,01,+,d,(1,2,3),c,02,+,d,(2,1,3),c,03,+,d,(3,1,2),这是最后一个阶段的决策，而,d,(1,2,3)=min,c,12,+,d,(2,3),c,13,+,d,(3,2),，,d,(2,1,3)=min,c,21,+,d,(1,3),c,23,+,d,(3,1),，,d,(3,1,2)=min,c,31,+,d,(1,2),c,32,+,d,(2,1),；,这一阶段的决策又依赖于下述计算结果：,78,d,(1,2)=,c,12,+,d,(2,),，,d,(2,3)=,c,23,+,d,(3,),，,d,(3,2)=,c,32,+,d,(2,),，,d,(1,3)=,c,13,+,d,(3,),，,d,(2,1)=,c,21,+,d,(1,),，,d,(3,1)=,c,31,+,d,(1,),；,而下式可以直接获得（括号中是该决策引起的状态转移）：,d,(1,)=,c,10,=5 10),，,d,(2,)=,c,20,=6 (20),，,d(3,)=,c,30,=3 (30),；,79,再向前倒推，有：,d,(1,2)=,c,12,+,d,(2,)=2+6=8(12),，,d,(1,3)=,c,13,+,d,(3,)=3+3=6(13),，,d,(2,3)=,c,23,+,d,(3,)=2+3=5(23),，,d,(2,1)=,c,21,+,d,(1,)=4+5=9(21),，,d,(3,1)=,c,31,+,d,(1,)=7+5=12(31),，,d,(3,2)=,c,32,+,d,(2,)=5+6=11(32),；,80,再向前倒推，有：,d,(1,2,3)=min,c,12,+,d,(2,3),c,13,+,d,(3,2)=min 2+5,3+11=7(12),，,d,(2,1,3)=min,c,21,+,d,(1,3),c,23,+,d,(3,1)=min 4+6,2+12=10(21),，,d,(3,1,2)=min,c,31,+,d,(1,2),c,32,+,d,(2,1)=min 7+8,5+9=14(32),；,81,最后有：,d,(0,1,2,3)=min,c,01,+,d,(1,2,3),c,02,+,d,(2,1,3),c,03,+,d,(3,1,2),=min 3+7,6+10,7+14=10 (01),。,即，从顶点,0,出发的,TSP,最短回路长度为,10,，回路路径为：,01230,。,82,四、近似算法,由于精确式算法所能求解的问题规模非常有限，实际中真正使用的往往都是多项式阶数的近似算法或启发式算法，算法的好坏用,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,当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的,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,回路,TSP,OPT,，,TSP,OPT,中共有,n,条边，现去掉,T,OPT,中最长的一条边，得路径,P,OPT,，,P,OPT,中共有,n-1,条边，其总权值之和,W,TSP,大于等于最小生成树的总权值之和,W,T,；即,W,TSP,W,T,下面只需证明该算法求得的,TSP,回路总长度之和,W,A,小于等于,2W,T,即可；,把最小生成树中的边重复一次，再根据三角不等式就可得出结论（多次利用三角不等式）。,为什么：,当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的,2,倍。,87,把最小生成树中的边重复一次，再根据三角不等式就可得出结论（多次利用三角不等式）。（,d,）中蓝色的边为原来不在最小生成树中的边，最小生成树中的边重复一次及不在,(d),中，但在,(b),中的边反复利用三角不等式就可得出结论。,88,1.,插入算法,插入型算法可按插入规则的不同而分为若干类，其一般思想为：,Step 1.,通过某种插入方式选择插入边,(,i,j,),和插入点,k,，将,k,插入,i,和,j,之间,形成,i,k,j,。,Step 2.,依次进行，直至形成回路解。,适用范围：对称型,TSP,。,具体实施中，可将出发点取遍,V,中各点而得到多个解，并从中选择最好的一个，但此时的时间复杂度增加了,n,倍。,主要的插入型算法有：,89,(1),最近插入法,最坏情况：,=2,；时间复杂度：,O,(,n,2,),。,(2),最小插入法,最坏情况：,=2,；时间复杂度：,O,(,n,2,lg,n,),。,(3),任意插入法,最坏情况：,=2 1g,n,+0.16,；时间复杂度：,O,(,n,2,),。,(4),最远插入法,最坏情况2 1g,n,+0.16,；时间复杂度：,O,(,n,2,),。,(5),凸核插入法,最坏情况：,=,未知；时间复杂度：,O,(,n,2,lg,n,),。,90,插入法,(Insertion Method),1,任选一节点为起点,a,；,2,寻找距离节点,a,最近的节点,b,作为下一个造访的节点，形成,a,-,b,-,a,的子回路；,3,寻找距离子回路最近的节点,k,作为下一个插入点；,4,寻找插入成本最小的位置,(,i,-,j,),，将,k,插入,i,-,j,之间，形成新的子回路；,插入成本：,C,ik,+C,kj,-C,ij,5,重复步骤,34,，直到所有节点均已插入回路之中，即形成一个,TSP,的可行解。,91,插入法,7,4,3,8,7,5,5,3,4,8,3,3,7,3,3,7,7,4,5,5,7,7,4,4,8,8,8,4,4,5,5,8,4,5,4,1,任选一节点为起点,a,；,2,寻找距离节点,a,最近的节点,b,作为下一个造访的节点，形成,a,-,b,-,a,的子回路；,3,寻找距离子回路最近的节点,k,作为下一个插入点；,4,寻找插入成本最小的位置,(,i,-,j,),，将,k,插入,i,-,j,之间，形成新的子回路；,插入成本：,C,ik,+C,kj,-C,ij,5,重复步骤,34,，直到所有节点均已插入回路之中，即形成一个,TSP,的可行解。,92,2最近邻算法,Step 1.,任取一出发点。,Step 2.,依次取最近的点加入当前解中，直至形成回路解。,适用范围：对称型,TSP,。,具体实施中，可将出发点取遍,V,中各点而得到多个解，从中选择最好的一个，但此时的时间复杂度增加了,n,倍。,最坏情况：,=(1g,n,+1)/2,；时间复杂度：,O,(,n,2,),。,93,最近邻点法,(Nearest-neighbor Heuristic),1,任选一节点为起点,x,；,2,寻找距离节点,x,最近的节点,y,作为下一个造访的节点；,3,寻找距离节点,y,最近的节点,z,作为下一个造访的节点；,4,重复以上步骤，直到所有节点均已访问；,5连接最后一个节点与起点，即形成一个,TSP,的可行解；,94,最近邻点法,7,4,3,8,7,5,5,3,4,8,1,2,3,4,5,1,4,7,3,8,2,4,7,5,5,3,7,7,3,4,4,3,5,3,8,5,8,5,4,8,95,3.,双生成树算法,Step 1.,首先求出最小生成树。,Step 2.,将树中各边都添一重复边形成,Euler,图，并求出其,Euler,回路。,Step 3.,在,Euler,回路点序列中去除重复点，形成,TSP,回路解。,适用范围：对称型,TSP,。,最坏情况：,=2,；时间复杂度：,O,(,n,2,),。,96,4 Christofides,算法,Step 1.,首先求出最小生成树。,Step 2.,对树中所有奇顶点求解最小权匹配问题。,Step 3.,将匹配边添入生成树，并求出其,Euler,回路。,Step 4.,在,Euler,回路点序列中去除重复点，形成,TSP,回路解。,适用范围：对称型,TSP,。,最坏情况：,=3/2,；时间复杂度：,O,(,n,3,),。,97,5.r-opt,算法,该方法是一种局部改进搜索算法，由,Lin,等人（,1965,）提出，其核心思想就是对给定的初始回路，通过每次交换,r,条边来改进当前的解。,适用范围：对称型,TSP,。,显然，对不同的,r,，其优劣次序为：,2-opt,，,3-optr-op