数学建模经典问题-旅行商问题

关于数学建模经典问题——旅行商问题2第7章旅行商问题1.问题概述

2.求解算法

2.1.下界和上界算法2.2.分支定界法

目录2.5.竞赛题2.3.动态规划法2.5.近似算法第2页,共105页，2024年2月25日，星期天3§7-1问题概述

一、数学模型

1.标准TSP

旅行商问题（简称TSP），也称货郎担问题或旅行推销员问题，是运筹学中一个著名的问题，其一般提法为：有一个旅行商从城市1出发，需要到城市2、3、…、n去推销货物，最后返回城市1，若任意两个城市间的距离已知，则该旅行商应如何选择其最佳行走路线？第3页,共105页，2024年2月25日，星期天4TSP在图论意义下又常常被称为最小Hamilton圈问题，Euler等人最早研究了该问题的雏形，后来由英国的Hamilton爵士作为一个悬赏问题而提出。但这个能让普通人在几分钟内就可理解的游戏之作，却延续至今仍未能完全解决，成了一个世界难题。

TSP有着明显的实际意义，如，邮局里负责到各信箱开箱取信的邮递员，以及去各分局送邮件的汽车等，都会遇到类似的问题。有趣的是，还有一些问题表面上看似乎与TSP无关，而实质上却可以归结为TSP来求解。已经证明，TSP是个NP难题，除非P=NP，否则不存在有效算法。第4页,共105页，2024年2月25日，星期天5

记为赋权图G=(V,E)，V为顶点集，E为边集，各顶点间的距离dij已知。设则经典的TSP可写为如下的数学规划模型：第5页,共105页，2024年2月25日，星期天6

模型中，为集合中所含图的顶点数。约束（7－1）和（7－2）意味着对每个点而言，仅有一条边进和一条边出；约束（7－3）则保证了没有任何子回路解的产生。于是，满足约束（7－1）、（7－2）和（7－3）的解构成了一条Hamilton回路。第6页,共105页，2024年2月25日，星期天7

当dij=dji

(i,j∈V)时，问题被称为对称型TSP，否则称为非对称型TSP。若对所有1≤i,j,k≤n

，有不等式dij+djk≥dik成立，则问题被称为是满足三角形不等式的，简称为ΔTSP。第7页,共105页，2024年2月25日，星期天82.扩展TSP(1)瓶颈TSP

瓶颈问题是最早从TSP延伸出来的一种扩展型TSP，其含义与经典的TSP类似，仅目标不同，要求巡回路线中经过的最长距离最短，即最小化瓶颈距离。该情形体现了那些并不追求总巡回路线最短，而只希望在巡回路线中每次从一个地点至另一个地点的单次行程尽可能短的实际应用问题的特征。第8页,共105页，2024年2月25日，星期天9

从严格的数学意义而言，瓶颈TSP（简称BTSP）并没有降低问题的难度，也未能提供任何特殊的解决办法。瓶颈TSP的数学模型与标准TSP类似，仅目标函数不同：

由于目标函数为瓶颈值，故求得的最佳巡回路线与标准TSP的往往截然不同。第9页,共105页，2024年2月25日，星期天10(2)最小比率TSP最小比率TSP（简称MRTSP）是从经典TSP引申出来的另一个变形问题，假定从一个城市走到另一个城市可得到某种收益（记为），则MRTSP的目标就是确定最佳行走路线，使得回路的总行程与总收益之比最小。这种优化目标的思想类似于人们日常生活中经常使用的费用效益比，与单纯的总行程最短相比，往往更具实际意义。第10页,共105页，2024年2月25日，星期天11

假定收益的数学性质与相同，则最小比率TSP的数学模型也与标准TSP类似，仅目标函数不同：

毫无疑问，由于目标函数中的非线性因素，最小比率TSP的求解比之标准TSP显得更为困难。第11页,共105页，2024年2月25日，星期天12(3)多人TSP

若标准TSP中，出发点有多个推销员同时出发，各自行走不同的路线，使得所有的城市都至少被访问过一次，然后返回出发点，要求所有推销员的总行程最短，则问题就成为一个多人的旅行商问题（简记MTSP）。令决策变量则MTSP的数学模型为：第12页,共105页，2024年2月25日，星期天13

假定原问题为对称型MTSP，V={v0,v1,…vn-1}，v0为名推销员出发点，记V‘={v01,v02,…v0m;v0,v1,…vn-1}，扩大的m-1个顶点称为“人造顶点”，其距离矩阵也相应扩大，其中，位于出发点的m个顶点相互间的距离设定为∞，其他数值不变。第13页,共105页，2024年2月25日，星期天14二、多面体理论从上世纪70年代开始的关于算法复杂性的研究表明，要想为TSP找到一个好的算法，也即多项式算法，似乎是不可能的。由于推销员的每条路线可以用一个以1开始的排列来表示，因此所有可能的路线有条。这样，若用枚举法来解决这一问题，即使不太大，例如n＝30，用目前最快的计算机，也要化几百万年才能求出一条最短的路线。第14页,共105页，2024年2月25日，星期天15

早在1954年，Dantzig等人就曾提出过一种方法（非多项式算法），并且求出了一个42城市的TSP最优解。到了1960年代，不少人用分支定界法解决了许多有几十个城市的TSP。还有人提出了一些近似方法，也解决了许多有几十个城市甚至上百个城市的TSP（有时找到的仅是近似解）。更值得注意的是，从1970年代中期开始，Grotschel与Padberg等人深入研究了TS多面体的最大面（facet），并从所得结果出发获得了一种解TSP的新算法，可以解决一些有100多个城市的TSP，且都在不长的时间内找到了最优解。第15页,共105页，2024年2月25日，星期天16

考虑个顶点的完全图Kn

，则解TSP就相当于在中求一条总长度最短的Hamilton回路。现在，对每条边ej，定义一个变量xj与之对应，这样，TSP的一条路线T，即Kn的一条Hamilton回路，就可对应一个向量X={x1,x2,….xm}，其中，第16页,共105页，2024年2月25日，星期天17

称X为路线T的关联向量，其m=n(n-2)/2个分量中，恰好有个为1，其余的都为0。图有许多Hamilton回路，设为T1,T2…Ts,，对应的关联向量记为X1,X2…Xs

，在m维空间Rm中，考虑这些向量生成的凸包（convexhull）Qn

：第17页,共105页，2024年2月25日，星期天18

Qn是Rm中的一个凸多面体，称做TS多面体。显然，Qn是有界的，其极点正好是Kn的Hamilton回路关联向量。研究Qn的面非常重要的，因为根据线性不等式及凸多面体的理论，Qn一定是某一个有限线性不等式组的解集合，或者说，Qn一定是有限多个半空间的交。因此，如果能找出定义Qn的线性不等式组来，就可将TSP作为一个线性规划来解。第18页,共105页，2024年2月25日，星期天19TS多面体研究中的一个重要问题就是寻找能导出Qn最大面的不等式，Grotschel等人发现了一类很重要的能导出最大面的梳子不等式，并予以了证明。此外，还有其它能导出最大面的不等式，如团树不等式等。可见，Qn的最大面极多，曾经计算过由梳子不等式所导出的最大面个数如表7－1所示：n6810203050120c(n)604142088419701.5*10181.5*103110602*10179表7－1第19页,共105页，2024年2月25日，星期天20

可以看出，当增大时，最大面个数增长得非常快。在TS多面体理论的基础上，可以考虑先解TSP的松弛问题，如果得到的最优解正好是某一条路线的关联向量，那么就找到TSP的最优解了；否则，就设法找一些新的不等式作为额外约束，再解新的线性规划，直至找到恰好是关联向量的最优解。这种做法的基本思想与解整数规划的割平面法是同一类的，Gotschel等人曾用这种方法解过有120个城市的TSP，所增加的不等式只有子回路消去不等式与梳子不等式两类，在进行了13轮计算后，即解了13个线性规划后，就找到了TSP的精确最优解，每一轮的当时计算时间仅在30秒至2分钟之间。有趣的是，当n=120时，仅梳子不等式就有2*10179个，但在计算过程中，总共却只（凭经验）添加了96个子回路消去不等式与梳子不等式。第20页,共105页，2024年2月25日，星期天21

当然，用该方法有时会找不到TSP的最优解，因为很可能在进行了几轮迭代后，却找不到新的不等式。Padborg与Hong曾计算了74个TSP，其中54个得到了最优解，其余的虽未得到最优解，却得到了很好的下界，如果与近似方法配合，可以估计近似解的精确程度。如，他们解过一个有313个城市的TSP，获得一个下界41236.46，而用近似方法能得到一条长为41349的路线，于是可估计出所得近似解与最优解的误差不超过0.26%。第21页,共105页，2024年2月25日，星期天22§7-2求解算法一、下界和上界算法1.下界（1）下界b1和b2

针对TSP对应图的邻接矩阵，将矩阵中每一行最小的元素相加，就可得到一个简单的下界b1。经进一步改进，可得到更好的下界：考虑一个TSP的完整解，在每条路径上，每个城市都有两条邻接边，一条进，一条出，那么，如果把矩阵中每一行最小的两个元素相加再除以2（不失一般性，可假定图中所有距离权重都为整数），再对其结果向上取整，就可得到一个合理的下界b2。显然，b2≥b1，因此，一般不采用b1作为TSP的下界。第22页,共105页，2024年2月25日，星期天23例1已知TSP及其距离矩阵如图7－1所示，试求其下界271563134253984(a)无向图图7－1无向图及距离矩阵(b)距离矩阵第23页,共105页，2024年2月25日，星期天24解：将矩阵中每一行最小的元素相加，1+3+1+3+2=10，即得b1=10。将矩阵中每一行最小的两个元素相加再除以2，再对结果向上取整，即可得b2=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14。第24页,共105页，2024年2月25日，星期天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)长边的另一个结点的编号(其中一个结点编号为i)；node_base(i)=dmin_j(i,1)+dmin_j(i,2)：表示与i点关联边中长度最短的两条边之和；C*(T)：最优回路长度；第25页,共105页，2024年2月25日，星期天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回路中时，等号才成立，下面就来分析如何提高这个下界。第26页,共105页，2024年2月25日，星期天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)。第27页,共105页，2024年2月25日，星期天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来说就不需要调整，否则按以下方式调整：第28页,共105页，2024年2月25日，星期天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)。第29页,共105页，2024年2月25日，星期天30②不选中e(i)1到TSP回路中此时对结点i需要调整，由于边e(i)1不在回路中，故其在node_base(i)的基础上至少会增加的长度为dmin(i,3)–dmin(i,1)。此时对结点j来说，由于与它关联的最短两条边仍然可能在回路中，因此不须调整。第30页,共105页，2024年2月25日，星期天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来说不需要调整，否则按与前面类似的方法计算调整值。经分析，其在base(T)的基础上至少要增加：add_node(i,2)=1/2*min(dmin(i,3)–dmin(i,2),dmin(i,2)–dmin(j,2))。第31页,共105页，2024年2月25日，星期天32

将每个结点都按上述方法进行一次调整，其调整累加和就是Adjust(T)，可写成如下公式：第32页,共105页，2024年2月25日，星期天33

将问题T中所有结点的基本长度node_base(T)累加之和的一半称为T的基本长度，并用base(T)来表示，可写成如下公式：第33页,共105页，2024年2月25日，星期天34

于是，有C*(T)≥base(T)+Adjust(T)=b3，即b3=b2+Adjust(T)。由以上分析，不难得出求对称TSP下界b3的算法：第34页,共105页，2024年2月25日，星期天35Step1.计算base(T)：

get_base()

{

i:LongFori=1Tonbase=base+dmin(i,1)+dmin(i,2)}第35页,共105页，2024年2月25日，星期天36Step2.计算Adjust(T)：get_adjust(){i,ii1,ii2:LongFori=1Ton{ii1=dmin_j(i,1);ii2=dmin_j(i,2)Ifi<>dmin_j(ii1,1)Andi<>dmin_j(ii1,2)adjust=adjust+min(dmin(i,3)-dmin(i,1),dmin(i,1)-dmin(ii1,2))Ifi<>dmin_j(ii2,1)Andi<>dmin_j(ii2,2)adjust=adjust+min(dmin(i,3)-dmin(i,2),dmin(i,2)-dmin(ii2,2))}}第36页,共105页，2024年2月25日，星期天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；dmin_j(3,3)=4；271563134253984(a)无向图图7－1无向图第37页,共105页，2024年2月25日，星期天38dmin(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；271563134253984(a)无向图图7－1无向图第38页,共105页，2024年2月25日，星期天39add_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_node(3,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，得b3=b2+Adjust(T)=14+1=15。第39页,共105页，2024年2月25日，星期天402.上界事实上，TSP的任何可行解都是上界，这里，给出求TSP上界U1的贪心方法思想。算法步骤如下：第40页,共105页，2024年2月25日，星期天41Step1.图G={V,E}中顶点个数为n=|V|，边的条数m=|E|，令i为出发点，TSP_edge_n为加入到TSP回路中边的条数且TSP_edge_n=0，TSP_edge为已加入到TSP回路中的边集合且TSP_edge={}，k为当前顶点且k=i。Step2.从边集

中选中一条代价最小的一条边(k,h)，并执行

TSP_edge_n=TSP_edge_n+1；

TSP_edge=TSP_edge+{(k,h)}；

k=h。Step3.若TSP_edge_n<(n-1)，则转Step2。Step4.将边(k,i)加入到TSP_edge中。第41页,共105页，2024年2月25日，星期天42

求解结束后，TSP_edge中的边都在TSP回路中。对例1，可用上述算法求得其路径为：1→3→5→4→2→1，路径长度1+2+3+7+3=16，这是TSP的一个上界U1。综合上下界，就可得到例1目标函数的界为[15,16]。271563134253984(a)无向图图7－1无向图第42页,共105页，2024年2月25日，星期天43二、分支定界法二、分支定界法分支定界法是一种在表示问题解空间的树上进行系统搜索的精确算法，这里，介绍两种求解TSP的分支定界方法。第43页,共105页，2024年2月25日，星期天44.基于上下界的分支定界法为用分支定界法求解TSP，需要计算某些边在TSP回路中和某些边不在TSP回路中等情况下的下界。若采用下界b2计算，由于每个顶点最多只有两个关联边在TSP回路中，已在TSP回路中的边则限制该边的其它邻接边加入，因此，针对每个顶点，分4种情况来计算：第44页,共105页，2024年2月25日，星期天45(1)若某顶点没有关联边在TSP回路中，则该顶点的计算方法与计算b2的方法相同，即把该顶点关联的最短两边长度之和的一半加入到下界中；(2)若某顶点关联的边已有两条边e1和e2在TSP回路中，则不需要再加入与该顶点关联最小两条边的长度，即此时把e1和e2长度之和的一半加入到下界中；(3)若某顶点关联的边已有一条边e1在TSP回路中，则只需要再加入与该顶点关联的最小边长度，即把e1和该顶点关联的最短一条边的长度之和的一半加入到下界中；(4)若某顶点关联边集的子集E1不能出现在TSP回路中，则将E1从图中删除再计算b2即可；如某顶点已有两关联边在回路中，则可将其它关联边删除，同样，可以将会与已加入到回路中的边形成子圈的边删除。第45页,共105页，2024年2月25日，星期天46

如例1中所示的无向图，若其TSP回路包含边(1,4)，则该部分解的下界b2=((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16，此时计算其下界时，由于边(1,4)已在回路中，故与顶点1关联的边只需再加入一条最短边(1,3)。若TSP回路包含边(1,2)和(2,4)，则这时的下界b2=((1+3)+(3+7)+(1+2)+(3+7)+(2+3))/2=16。271563134253984(a)无向图图7－1无向图第46页,共105页，2024年2月25日，星期天47

为描述方便，用eij

=1表示边(i,j)在TSP回路中，eij

=0表示边(i,j)不在TSP回路中。下面给出用分支定界法求解例1的过程（如图7－2所示）：第47页,共105页，2024年2月25日，星期天48图7－2分支定界求解过程U1=16e13=0e13=1b2=17.5>U1,故剪支e12=0e12=1b2=17>U1,故剪支得最优解e12=e13=e24=e35=e54=1,

e14=e15=e23=e25=e34=0e25=0e25=1b2=18.5>U1=16,故剪支此时有e14=e15=e23=0此时有e24=e35=e54=1,e34=0第48页,共105页，2024年2月25日，星期天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)在e13=1的情况下，假定e12=0，此时b2=((1+5)+(6+7)+(1+2)+(3+4)+(2+3))/2=17，由于b2=17>U1=16，因此边(1,2)一定在回路中，即e12=1；第49页,共105页，2024年2月25日，星期天50(4)在e12=e13=1的情况下，由于顶点1已有两条关联边在最优回路中，因此在图7－1中删去边(1,4)和(1,5)，由于边(2,3)与边(1,2)、(1,3)形成圈，因此在图7－1中删去边(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=18.5>U1=16，因此边(2,5)一定不在回路中，即e25=0；第50页,共105页，2024年2月25日，星期天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。第51页,共105页，2024年2月25日，星期天522.基于降阶的分支定界法对于有向TSP的距离距阵，可通过不同情况下上下界的对比来确定某些边(i,j)一定在或不在回路中。如果能确定(i,j)一定在回路中，由于每个顶点分别有且只有一条入边和出边，从而可确定顶点i的其它出边一定不在回路中，也可以确定顶点j的其它出边一定不在回路中，因此可将这些边从距离距阵中去掉，从而达到降低矩阵阶数的目的。这里，以一个具体的例子来予以说明。第52页,共105页，2024年2月25日，星期天53例2已知有向TSP的距离矩阵如下：第53页,共105页，2024年2月25日，星期天54解:

由于每个顶点都必须有一条入边和出边，因此将顶点i的所有出边的权值减去所有出边权值的最小值min_out(i)，不会影响最优解，仅最优值在原来的基础上减少了min_out(i)。于是，可以将距离矩阵的每一行和每一列都减去该行或该列的最小值，直至每行每列都含有0为止。将上述矩阵的每行分别减去该行的最小值3,4,16,7,25,3，就得到如下缩减之后的矩阵：第54页,共105页，2024年2月25日，星期天55

该缩减矩阵所对应TSP的最优解与原来的相同，但最优值比原来减少了3+4+16+7+25+3=58。由于矩阵中第3、4列中不含0元素，因此可继续缩减成：第55页,共105页，2024年2月25日，星期天56该缩减矩阵所对应TSP的最优解与原来的相同，但最优值比原来减少了3+4+16+7+25+3=58。由于矩阵中第3、4列中不含0元素，因此可继续缩减成：第56页,共105页，2024年2月25日，星期天57

其最优值比原来减少58+15+8=81，这个81可作为该TSP初始的下界值b。第57页,共105页，2024年2月25日，星期天58按e63=1和e63=0将解分成两种情况：(1)e63=0

此时，边(6,3)不能出现在回路中，其权值在这种情况下为∞，因此，距离矩阵可修改为：第58页,共105页，2024年2月25日，星期天59

由于第3列没有0元素，故用第3列各元素减去其最小元素48，得如下缩减矩阵：

此时的下界b=81+48=129。第59页,共105页，2024年2月25日，星期天60(2)e63=1

此时，边(6,3)已出现在回路中，从顶点6出发的其它边都不可能在回路中，因此可删去第6行；同理，进入到顶点3的其它边都不可能在回路中，因此又可删去第3列。此时，边(3,6)不可能出现在回路中，令边(3,6)的权值为∞，矩阵化为：第60页,共105页，2024年2月25日，星期天61继续依次计算，并实施分支和定界，具体过程如图7－3所示：图7－3降阶分支定界过程b=81e63=0e63=1b=129e46=0e46=1b=113e21=0e21=1b=81b=81b=84b=101e14=1e14=0b=84b=112得可行回路(1,4,6,3,5,2,1),回路总长104，由此可将下界b大于104的分支剪去。第61页,共105页，2024年2月25日，星期天62e63=1，e46=0下的缩减矩阵：第62页,共105页，2024年2月25日，星期天63e63=e46=1下的缩减矩阵：第63页,共105页，2024年2月25日，星期天64e63=e46=1，e21=0下的缩减矩阵：第64页,共105页，2024年2月25日，星期天65e63=e46=e21=1下的缩减矩阵：第65页,共105页，2024年2月25日，星期天66e63=e46=e21=1，e14=0下的缩减矩阵：第66页,共105页，2024年2月25日，星期天67e63=e46=e21=e14=1下的缩减矩阵：第67页,共105页，2024年2月25日，星期天68e63=e46=1，e21=e51=0下的缩减矩阵：第68页,共105页，2024年2月25日，星期天69e63=e46=e51=1，e21=0下的缩减矩阵：第69页,共105页，2024年2月25日，星期天70e63=e46=e51=1，e21=e14=0下的缩减矩阵：第70页,共105页，2024年2月25日，星期天71e63=e46=e51=e14=1，e21=0下的缩减矩阵：第71页,共105页，2024年2月25日，星期天72

最后可得到两个最优TSP回路：(1,4,6,3,2,5,1)和(1,4,6,3,5,2,1)，最优回路长度为104。若将无向图中的每条边看成有向图中方向相反的两条边，则无向图也可看成是有向图，因此，基于降阶的分支定界法也可用来求解无向TSP问题。第72页,共105页，2024年2月25日，星期天73三、动态规划法定理1TSP满足最优性原理。

最优化原理可以表述为：“一个过程的最优策略具有这样的性质,即无论初始状态和初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成最优策略，”第73页,共105页，2024年2月25日，星期天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要短，从而导致矛盾。所以，TSP满足最优性原理。第74页,共105页，2024年2月25日，星期天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}，cij为顶点i至顶点j的距离，于是，TSP的动态规划递推函数可写成：第75页,共105页，2024年2月25日，星期天76d(i,V')=min{cik

+d(k,V'－{k})}(k∈V')d(k,{})=ck0

(k≠0

)例3求解有向TSP：第76页,共105页，2024年2月25日，星期天77解：从城市0出发经城市1、2、3然后回到城市0的最短路径长度为：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})}；这一阶段的决策又依赖于下述计算结果：第77页,共105页，2024年2月25日，星期天78d(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,{})；而下式可以直接获得（括号中是该决策引起的状态转移）：d(1,{})=c10=5(1→0)，d(2,{})=c20=6(2→0)，d(3,{})=c30=3(3→0)；第78页,共105页，2024年2月25日，星期天79再向前倒推，有：d(1,{2})=c12+d(2,{})=2+6=8(1→2)，d(1,{3})=c13+d(3,{})=3+3=6(1→3)，d(2,{3})=c23+d(3,{})=2+3=5(2→3)，d(2,{1})=c21+d(1,{})=4+5=9(2→1)，d(3,{1})=c31+d(1,{})=7+5=12(3→1)，d(3,{2})=c32+d(2,{})=5+6=11(3→2)；第79页,共105页，2024年2月25日，星期天80再向前倒推，有：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}=min{2+5,3+11}=7(1→2)，d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}=min{4+6,2+12}=10(2→1)，d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}=min{7+8,5+9}=14(3→2)；第80页,共105页，2024年2月25日，星期天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(0→1)。即，从顶点0出发的TSP最短回路长度为10，回路路径为：0→1→2→3→0。第81页,共105页，2024年2月25日，星期天82四、近似算法

由于精确式算法所能求解的问题规模非常有限，实际中真正使用的往往都是多项式阶数的近似算法或启发式算法，算法的好坏用C/C*≤ε来衡量，其中，C为近似算法所得的总行程，C*为最优总行程，ε为最“坏“情况下近似与最优总行程之比所不超过的上界值。这里，列举几个常见的TSP快速近似算法。第82页,共105页，2024年2月25日，星期天83

旅行售货员问题的一些特殊性质：比如，费用函数w往往具有三角不等式性质，即对任意的3个顶点u,v,w∈V，有：w(u,w)≤w(u,v)+w(v,w)。当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数w就具有三角不等式性质。

对于给定的无向图G，可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。

第83页,共105页，2024年2月25日，星期天84

当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。

voidapproxTSP(Graphg){(1)选择g的任一顶点r；

(2)用Prim算法找出带权图g的一棵以r为根的最小生成树T；

(3)前序遍历树T得到的顶点表L；

(4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；}第84页,共105页，2024年2月25日，星期天85(b)表示找到的最小生成树T；(c)表示对T作前序遍历的次序；(d)表示L产生的哈密顿回路H；(e)是G的一个最小费用旅行售货员回路。

为什么：当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。第85页,共105页，2024年2月25日，星期天86答：存在一个最优TSP回路TSPOPT，TSPOPT中共有n条边，现去掉TOPT中最长的一条边，得路径POPT，POPT中共有n-1条边，其总权值之和WTSP大于等于最小生成树的总权值之和WT；即WTSP≥WT,下面只需证明该算法求得的TSP回路总长度之和WA小于等于2WT即可；把最小生成树中的边重复一次，再根据三角不等式就可得出结论（多次利用三角不等式）。

为什么：当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。第86页,共105页，2024年2月25日，星期天87

把最小生成树中的边重复一次，再根据三角不等式就可得出结论（多次利用三角不等式）。（d）中蓝色的边为原来不在最小生成树中的边，最小生成树中的边重复一次及不在(d)中，但在(b)中的边反复利用三角不等式就可得出结论。第87页,共105页，2024年2月25日，星期天881.插入算法插入型算法可按插入规则的不同而分为若干类，其一般思想为：Step1.通过某种插入方式选择插入边(i,j)和插入点k，将k

插入i

和j之间,形成{…,i,k,j,…}。Step2.依次进行，直至形成回路解。适用范围：对称型△TSP。具体实施中，可将出发点取遍V中各点而得到多个解，并从中选择最好的一个，但此时的时间复杂度增加了n倍。主要的插入型算法有：第88页,共105页，2024年2月25日，星期天89(1)最近插入法最坏情况：ε=2；时间复杂度：O(n2)。(2)最小插入法最坏情况：ε=2；时间复杂度：O(n2lgn)。(3)任意插入法最坏情况：ε=21gn+0.16；时间复杂度：O(n2)。(4)最远插入法最坏情况：ε=21gn+0.16；时间复杂度：O(n2)。(5)凸核插入法最坏情况：ε=未知；时间复杂度：O(n2lgn)。第89页,共105页，2024年2月25日，星期天90插入法(InsertionMethod)

1任选一节点为起点a；2寻找距离节点a最近的节点b作为下一个造访的节点，形成a-b-a的子回路；3寻找距离子回路最近的节点k作为下一个插入点；4寻找插入成本最小的位置(i-j)，将k插入i-j之间，形成新的子回路；

‧插入成本：Cik+Ckj-Cij5重复步骤3~4，直到所有节点均已插入回路之中，即形成一个TSP的可行解。第90页,共105页，2024年2月25日，星期天91插入法743875534833733774557744888445584541任选一节点为起点a；2寻找距离节点a最近的节点b作为下一个造访的节点，形成a-b-a的子回路；3寻找距离子回路最近的节点k作为下一个插入点；4寻找插入成本最小的位置(i-j)，将k插入i-j之间，形成新的子回路；

‧插入成本：Cik+Ckj-Cij5重复步骤3~4，直到所有节点均已插入回路之中，即形成一个TSP的可行解。第91页,共105页，2024年2月25日，星期天922.最近邻算法Step1.任取一出发点。Step2.依次取最近的点加入当前解中，直至形成