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

1、1第第7章章 旅行商问题旅行商问题2第第7章章 旅行商问题旅行商问题1.问题概述问题概述 2.求解算法求解算法 2.1.下界和上界算法下界和上界算法2.2.分支定界法分支定界法 目录目录2.5.竞赛题竞赛题2.3.动态规划法动态规划法2.5.近似算法近似算法37-1 问题概述问题概述 一、数学模型一、数学模型 1. 标准标准TSP 旅行商问题（简称旅行商问题（简称TSP），也称货郎担问题或），也称货郎担问题或旅行推销员问题，是运筹学中一个著名的问题，其旅行推销员问题，是运筹学中一个著名的问题，其一般提法为：有一个旅行商从城市一般提法为：有一个旅行商从城市1出发，需要到出发，需要到城市城市2、3

2、、n去推销货物，最后返回城市去推销货物，最后返回城市1，若，若任意两个城市间的距离已知，则该旅行商应如何选任意两个城市间的距离已知，则该旅行商应如何选择其最佳行走路线？择其最佳行走路线？4 TSP在图论意义下又常常被称为最小在图论意义下又常常被称为最小Hamilton圈问题，圈问题，Euler等人最早研究了该问题的雏形，后来由英国的等人最早研究了该问题的雏形，后来由英国的Hamilton爵士作为一个悬赏问题而提出。但这个能让普通人爵士作为一个悬赏问题而提出。但这个能让普通人在几分钟内就可理解的游戏之作，却延续至今仍未能完全解在几分钟内就可理解的游戏之作，却延续至今仍未能完全解决，成了一个世界难

3、题。决，成了一个世界难题。 TSP有着明显的实际意义，如，邮局里负责到各信箱开有着明显的实际意义，如，邮局里负责到各信箱开箱取信的邮递员，以及去各分局送邮件的汽车等，都会遇到箱取信的邮递员，以及去各分局送邮件的汽车等，都会遇到类似的问题。有趣的是，还有一些问题表面上看似乎与类似的问题。有趣的是，还有一些问题表面上看似乎与TSP无关，而实质上却可以归结为无关，而实质上却可以归结为TSP来求解。已经证明，来求解。已经证明，TSP是个是个NP难题，除非难题，除非P = NP，否则不存在有效算法。，否则不存在有效算法。5 记为赋权图记为赋权图G=(V,E)，V为顶点集，为顶点集，E为边集，为边集，各顶

4、点间的距离各顶点间的距离dij已知。设已知。设1 ,0,iji jx若在回路路径上其他则经典的TSP可写为如下的数学规划模型：1111m in 1,(71)1,(72)s.t1, , 21 (73)0, 1nnijijijnijjnijiijiSjSijZd xxiVxjVxSSVSnx 61111min 1,(7 1)1,(7 2)s.t1, ,21 (7 3)0,1nnijijijnijjnijiiji S j SijZd xxiVxjVxSSVSnx 模型中，为集合中所含图的顶点数。约束（模型中，为集合中所含图的顶点数。约束（71）和（和（72）意味着对每个点而言，仅有一条边进和一条）意

5、味着对每个点而言，仅有一条边进和一条边出；约束（边出；约束（73）则保证了没有任何子回路解的产生。）则保证了没有任何子回路解的产生。于是，满足约束（于是，满足约束（71）、（）、（72）和（）和（73）的解构）的解构成了一条成了一条Hamilton回路。回路。7 当当dij=dji (i, jV) 时，问题被称为时，问题被称为对称型对称型TSP，否，否则称为则称为非对称型非对称型TSP。 若对所有若对所有1i, j, kn ，有不等式，有不等式dij + djk dik成成立，则问题被称为是立，则问题被称为是满足三角形不等式满足三角形不等式的，简称为的，简称为TSP。82. 扩展扩展TSP(1

6、) 瓶颈瓶颈TSP 瓶颈问题是最早从瓶颈问题是最早从TSP延伸出来的一种扩展型延伸出来的一种扩展型TSP，其含义与经典的，其含义与经典的TSP类似，仅目标不同，要类似，仅目标不同，要求巡回路线中经过的最长距离最短，即最小化瓶颈求巡回路线中经过的最长距离最短，即最小化瓶颈距离。该情形体现了那些并不追求总巡回路线最短，距离。该情形体现了那些并不追求总巡回路线最短，而只希望在巡回路线中每次从一个地点至另一个地而只希望在巡回路线中每次从一个地点至另一个地点的单次行程尽可能短的实际应用问题的特征。点的单次行程尽可能短的实际应用问题的特征。9 从严格的数学意义而言，瓶颈从严格的数学意义而言，瓶颈TSP（简

7、称（简称BTSP）并没有降低问题的难度，也未能提供任何特殊的解决并没有降低问题的难度，也未能提供任何特殊的解决办法。办法。 瓶颈瓶颈TSP的数学模型与标准的数学模型与标准TSP类似，仅目标函类似，仅目标函数不同：数不同： min Zmax,ijijdxi jV 由于目标函数为瓶颈值，故求得的最佳巡回路由于目标函数为瓶颈值，故求得的最佳巡回路线与标准线与标准TSP的往往截然不同。的往往截然不同。10(2) 最小比率最小比率TSP 最小比率最小比率TSP（简称（简称MRTSP）是从经典）是从经典TSP引引申出来的另一个变形问题申出来的另一个变形问题，假定从一个城市走到另，假定从一个城市走到另一个城

8、市可得到某种收益（记为），则一个城市可得到某种收益（记为），则MRTSP的的目标就是确定最佳行走路线目标就是确定最佳行走路线，使得回路的总行程与，使得回路的总行程与总收益之比最小。这种优化目标的思想类似于人们总收益之比最小。这种优化目标的思想类似于人们日常生活中经常使用的费用效益比，与单纯的总行日常生活中经常使用的费用效益比，与单纯的总行程最短相比，往往更具实际意义。程最短相比，往往更具实际意义。11 假定收益的数学性质与相同，则最小比率假定收益的数学性质与相同，则最小比率TSP的的数学模型也与标准数学模型也与标准TSP类似，仅目标函数不同：类似，仅目标函数不同： 毫无疑问，由于目标函数中的非

9、线性因素，最毫无疑问，由于目标函数中的非线性因素，最小比率小比率TSP的求解比之标准的求解比之标准TSP显得更为困难。显得更为困难。m in ijijijijijijdxZpx12(3) 多人多人TSP 若标准若标准TSP中中，出发点有多个推销员同时出发，各自行，出发点有多个推销员同时出发，各自行走不同的路线，使得所有的城市都至少被访问过一次，然后走不同的路线，使得所有的城市都至少被访问过一次，然后返回出发点，要求所有推销员的总行程最短，则问题就成为返回出发点，要求所有推销员的总行程最短，则问题就成为一个多人的旅行商问题（简记一个多人的旅行商问题（简记MTSP）。）。 令决策变量令决策变量则则

10、MTSP的数学模型为：的数学模型为： 1,0,ijijx若有某推销员从城市 到城市否则13-110-10-10min1,1, 2,1,01,1, 2,1. .,00,1,0,mnijijijnkjknikkijiiZd xjnxmjinxs tmixxi j 对对对对且 不 存 在 任 何 子 回 路 假定原问题为对称型假定原问题为对称型MTSP，V=v0,v1,vn-1，v0为名推销员出发点，记为名推销员出发点，记V=v01,v02,v0m; v0,v1,vn-1 ，扩大的，扩大的m-1个顶点称为个顶点称为“人造顶点人造顶点”，其距离，其距离矩阵也相应扩大，其中，位于出发点的矩阵也相应扩大，

11、其中，位于出发点的m个顶点相个顶点相互间的距离设定为互间的距离设定为，其他数值不变。，其他数值不变。14二、多面体理论二、多面体理论 从上世纪从上世纪70年代开始的关于算法复杂性的研究年代开始的关于算法复杂性的研究表明，要想为表明，要想为TSP找到一个好的算法，也即多项式找到一个好的算法，也即多项式算法，似乎是不可能的。由于推销员的每条路线可算法，似乎是不可能的。由于推销员的每条路线可以用一个以以用一个以1开始的排列来表示，因此所有可能的开始的排列来表示，因此所有可能的路线有条。这样，若用枚举法来解决这一问题，即路线有条。这样，若用枚举法来解决这一问题，即使不太大，例如使不太大，例如n30，用

12、目前最快的计算机，也，用目前最快的计算机，也要化几百万年才能求出一条最短的路线。要化几百万年才能求出一条最短的路线。15 早在早在1954年，年，Dantzig等人就曾提出过一种方等人就曾提出过一种方法（非多项式算法），并且求出了一个法（非多项式算法），并且求出了一个42城市的城市的TSP最优解。到了最优解。到了1960年代，不少人用分支定界法年代，不少人用分支定界法解决了许多有几十个城市的解决了许多有几十个城市的TSP。还有人提出了一。还有人提出了一些近似方法，也解决了许多有几十个城市甚至上百些近似方法，也解决了许多有几十个城市甚至上百个城市的个城市的TSP（有时找到的仅是近似解）。更值得（

13、有时找到的仅是近似解）。更值得注意的是，从注意的是，从1970年代中期开始，年代中期开始，Grotschel与与Padberg等人深入研究了等人深入研究了TS多面体的最大面多面体的最大面（facet），并从所得结果出发获得了一种解），并从所得结果出发获得了一种解TSP的的新算法，可以解决一些有新算法，可以解决一些有100多个城市的多个城市的TSP，且都，且都在不长的时间内找到了最优解。在不长的时间内找到了最优解。16 考虑个顶点的完全图考虑个顶点的完全图Kn ，则解，则解TSP就相当于在就相当于在中求一条总长度最短的中求一条总长度最短的Hamilton回路。现在，对每回路。现在，对每条边条边e

14、j，定义一个变量，定义一个变量xj与之对应，这样，与之对应，这样，TSP的一的一条路线条路线T，即，即Kn的一条的一条Hamilton回路，就可对应一回路，就可对应一个向量个向量X=x1,x2,.xm，其中，其中，1,0,jjjjxeTxeT若若17 称称X为路线为路线T的关联向量，其的关联向量，其m=n(n-2)/2个分量中，恰好个分量中，恰好有个为有个为1，其余的都为，其余的都为0。 图有许多图有许多Hamilton回路，设为回路，设为T1, T2 Ts,，对应的关联向，对应的关联向量记为量记为X1, X2 Xs ，在，在m维空间维空间Rm中，考虑这些向量生成的中，考虑这些向量生成的凸包（

15、凸包（convex hull） Qn ：111,0,1,2,ssniiiiiiQXis18 Qn是是Rm中的一个凸多面体，称做中的一个凸多面体，称做TS多面体。多面体。显然，显然， Qn是有界的，其极点正好是是有界的，其极点正好是Kn的的Hamilton回回路关联向量。路关联向量。 研究研究Qn的面非常重要的，因为根据线性不等式的面非常重要的，因为根据线性不等式及凸多面体的理论，及凸多面体的理论， Qn一定是某一个有限线性不等一定是某一个有限线性不等式组的解集合，或者说，式组的解集合，或者说， Qn一定是有限多个半空间一定是有限多个半空间的交。因此，如果能找出定义的交。因此，如果能找出定义Qn

16、的线性不等式组来，的线性不等式组来，就可将就可将TSP作为一个线性规划来解。作为一个线性规划来解。19 TS多面体研究中的一个重要问题就是寻找能导出多面体研究中的一个重要问题就是寻找能导出Qn最大面的不等式，最大面的不等式，Grotschel等人发现了一类很重要的能导等人发现了一类很重要的能导出最大面的梳子不等式，并予以了证明。此外，还有其它出最大面的梳子不等式，并予以了证明。此外，还有其它能导出最大面的不等式，如团树不等式等。可见，能导出最大面的不等式，如团树不等式等。可见， Qn的最的最大面极多，曾经计算过由梳子不等式所导出的最大面个数大面极多，曾经计算过由梳子不等式所导出的最大面个数如表

17、如表71所示：所示：n6810203050120c(n)604142088419701.5*10181.5*103110602*10179表表71 20 可以看出，当增大时，最大面个数增长得非常快。可以看出，当增大时，最大面个数增长得非常快。 在在TS多面体理论的基础上，可以考虑先解多面体理论的基础上，可以考虑先解TSP的松弛问的松弛问题，如果得到的最优解正好是某一条路线的关联向量，那么题，如果得到的最优解正好是某一条路线的关联向量，那么就找到就找到TSP的最优解了；否则，就设法找一些新的不等式作的最优解了；否则，就设法找一些新的不等式作为额外约束，再解新的线性规划，直至找到恰好是关联向量为额

18、外约束，再解新的线性规划，直至找到恰好是关联向量的最优解。这种做法的基本思想与解整数规划的割平面法是的最优解。这种做法的基本思想与解整数规划的割平面法是同一类的，同一类的，Gotschel 等人曾用这种方法解过有等人曾用这种方法解过有120个城市的个城市的TSP，所增加的不等式只有子回路消去不等式与梳子不等式，所增加的不等式只有子回路消去不等式与梳子不等式两类，在进行了两类，在进行了13轮计算后，即解了轮计算后，即解了13个线性规划后，就找个线性规划后，就找到了到了TSP的精确最优解，每一轮的当时计算时间仅在的精确最优解，每一轮的当时计算时间仅在30秒至秒至2分钟之间。有趣的是，当分钟之间。有

19、趣的是，当n = 120时，仅梳子不等式就有时，仅梳子不等式就有2*10179个，但在计算过程中，总共却只（凭经验）添加了个，但在计算过程中，总共却只（凭经验）添加了96个子回路消去不等式与梳子不等式。个子回路消去不等式与梳子不等式。21 当然，用该方法有时会当然，用该方法有时会找不到找不到TSP的最优解，的最优解，因为很可能在进行了几轮迭代后，却找不到新的不因为很可能在进行了几轮迭代后，却找不到新的不等式。等式。Padborg与与Hong曾计算了曾计算了74个个TSP，其中，其中54个得到了最优解，其余的虽未得到最优解，却得到个得到了最优解，其余的虽未得到最优解，却得到了很好的下界，如果与近

20、似方法配合，可以估计近了很好的下界，如果与近似方法配合，可以估计近似解的精确程度。如，他们解过一个有似解的精确程度。如，他们解过一个有313个城市个城市的的TSP，获得一个下界，获得一个下界41236.46，而用近似方法能，而用近似方法能得到一条长为得到一条长为41349的路线，于是可估计出所得近的路线，于是可估计出所得近似解与最优解的误差不超过似解与最优解的误差不超过0.26%。227-2 求解算法求解算法一、下界和上界算法一、下界和上界算法1. 下界下界（1）下界）下界b1和和b2 针对针对TSP对应图的邻接矩阵，将矩阵中每一行最小的元对应图的邻接矩阵，将矩阵中每一行最小的元素相加，就可得

21、到一个简单的下界素相加，就可得到一个简单的下界b1。经进一步改进，可得。经进一步改进，可得到更好的下界：考虑一个到更好的下界：考虑一个TSP的完整解，在每条路径上，每的完整解，在每条路径上，每个城市都有两条邻接边，一条进，一条出，那么，如果把矩个城市都有两条邻接边，一条进，一条出，那么，如果把矩阵中每一行最小的两个元素相加再除以阵中每一行最小的两个元素相加再除以2（不失一般性，可（不失一般性，可假定图中所有距离权重都为整数），再对其结果向上取整，假定图中所有距离权重都为整数），再对其结果向上取整，就可得到一个合理的下界就可得到一个合理的下界b2。 显然，显然，b2b1，因此，一般不采用，因此，

22、一般不采用b1作为作为TSP的下界。的下界。23例例1 已知已知TSP及其距离矩阵如图及其距离矩阵如图71所示，试求其下所示，试求其下界界 271563134253984(a) 无向图无向图图图71 无向图及无向图及距离矩阵距离矩阵(b) 距离矩阵距离矩阵3298347524519763851324解：解： 将矩阵中每一行最小的元素相加，将矩阵中每一行最小的元素相加，1+3+1+3+2 = 10，即得，即得b1=10。将矩阵中每一行最小的两个元素相。将矩阵中每一行最小的两个元素相加再除以加再除以2，再对结果向上取整，即可得，再对结果向上取整，即可得b2 = (1+3) + (3+6) + (1

23、+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) 长边长边的另一个结点的编号的另一个结点的编号(其中一个结点编号为其中一个结点编号为i)；nod

24、e_ 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轻易求得。

25、轻易求得。 通过对下界通过对下界b2进行改进，可以得出一个求对称进行改进，可以得出一个求对称型型TSP更好的下界更好的下界b3。 在求在求b2的过程中，只有当与每一结点关联的边的过程中，只有当与每一结点关联的边中长度最小的两条边都出现在最优中长度最小的两条边都出现在最优TSP回路中时，回路中时，等号才成立，下面就来分析如何提高这个下界。等号才成立，下面就来分析如何提高这个下界。27 对结点对结点i而言，设而言，设e (i)1与与e (i)2分别为与结点分别为与结点i关关联的边中长度最小的两条边，其长度分别为联的边中长度最小的两条边，其长度分别为dmin (i, 1) 和和dmin (i, 2)

26、。 在对称型在对称型TSP回路中，由于有且仅有两条边与回路中，由于有且仅有两条边与每一结点关联，因此，并不是与每个结点关联的最每一结点关联，因此，并不是与每个结点关联的最小两条边都能出现在最优小两条边都能出现在最优TSP回路中，这意味可以回路中，这意味可以在在node_ base(i)的基础上增加的基础上增加TSP回路的长度，将在回路的长度，将在这种情况下增加的长度记为这种情况下增加的长度记为Adjust (T)，现在分析，现在分析如何计算如何计算Adjust(T)。28 对结点对结点i的的e (i)1，边，边e (i)1的一个结点为的一个结点为i，另一，另一个结点为个结点为j = dmin_

27、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出现在最优回路中，而出

28、现在最优回路中，而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)的基础上至少会增

29、加的长的基础上至少会增加的长度为度为 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的

30、的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 将每个结点都按上述方法进行一次调整，其

31、调将每个结点都按上述方法进行一次调整，其调整累加和就是整累加和就是Adjust (T)，可写成如下公式：，可写成如下公式：1( )( 1)( 2)ni=Adjust Tadd_node i,+add_node i,33 将问题将问题T中所有结点的基本长度中所有结点的基本长度node_base(T)累累加之和的一半称为加之和的一半称为T的基本长度，并用的基本长度，并用base (T)来表来表示，可写成如下公式：示，可写成如下公式：121( )1/2*( ,1)( ,2)1/2*( )ninibase Tdmin idmin inode_base ib34 于是，有于是，有C*(T) base(T

32、) + Adjust(T) = b3，即，即 b3 = b2 + Adjust(T) 。由以上分析，不难得出求对称由以上分析，不难得出求对称TSP下界下界b3的算法：的算法：35Step 1. 计算计算base (T)： get_base () i: Long For i = 1 To n base = base + dmin(i, 1) + dmin(i, 2) 36Step 2. 计算计算Adjust (T)： get_adjust () i , ii1, ii2: Long For i = 1 To n ii1 = dmin_j (i, 1); ii2 = dmin_j (i, 2) I

33、f 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而言，可计算其而言，可计算其b3如下：如下：dmin(1, 1)=1；dmin_j(1, 1)=3；dmin(1, 2)=3；dmin_j(1, 2)=2；

34、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) 无向图无向图图图71 无向图无向图38dmin(4, 1)=3；dmin_j(4, 1)=5；dmin(4, 2)=4；dmin_j(4, 2)=3；dmin(4, 3)

35、=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) 无向图无向图图图71 无向图无向图52111/2*( )1/2*( ,1)( ,2)(13)(36)(12)(34)(23)/214niibnode_base idmin idmin i39add_node(1,1)=0; add_node(1,2)=0; add_node(2,1)=0; add_node(2,2)=1/2min (7-6), (6-2)

36、=1/2;add_node(3,1)=0; add_node(3,2)=1/2min (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。402. 上界上界 事实上，事实上，TSP的任何可行解都是上界，这里，的任何可行解都是上界，这里，给出求给出求TSP上界上界U1的贪心方法思想。的贪心方法思想。算法步骤如下：算法步骤如下：41Step 1. 图

37、图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。

38、Step 3. 若若TSP_edge_n 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 = 049 (1)用贪心算法求得用贪心算法求得上界上界U1 = 16； (2)假定边假定边(1, 3)不在不在TSP回路中回路中，即，即e13 = 0，此时，此时，b2 = (5+3) + (3+6) + (4+2) + (3+4) + (2+

39、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；50(4) 在在e12 = e13 = 1的情况下，由于顶点的情况下，由于顶点1已有两条关联已有两条关联边在最优回路中，因此在图边在最优回路中，因此在图71中中删

40、去删去边边(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 = 18.5 U1 = 16，因此边，因此边(2, 5)一定不在回路中，即一定不在回路中，即e25 = 0；51在在e12 = e

41、13 = 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。 522. 基于降阶的分支定界法基于降阶的分支定界法 对于对于有向有向TSP的距离距阵，可通过不同情况下的距离距阵，可通过不同

42、情况下上下界的对比来确定某些边上下界的对比来确定某些边(i, j)一定在或不在回路一定在或不在回路中。如果能确定中。如果能确定(i, j)一定在回路中，由于每个顶点一定在回路中，由于每个顶点分别分别有且只有一条入边和出边有且只有一条入边和出边，从而可确定顶点，从而可确定顶点i的的其它出边一定不在回路中，也可以确定顶点其它出边一定不在回路中，也可以确定顶点j的其它的其它出边一定不在回路中，因此可将这些边从距离距阵出边一定不在回路中，因此可将这些边从距离距阵中去掉，从而达到中去掉，从而达到降低矩阵阶数降低矩阵阶数的目的。的目的。 这里，以一个具体的例子来予以说明。这里，以一个具体的例子来予以说明。

43、53例例2 已知有向已知有向TSP的距离矩阵如下：的距离矩阵如下：6 5 4 3 2 1654321924618883253388462875680903928163617451621427749331393354解解: 由于每个顶点都必须有一条入边和出边，因此由于每个顶点都必须有一条入边和出边，因此将将顶点顶点i的所有出边的权值减去所有出边权值的最小值的所有出边的权值减去所有出边权值的最小值min_out(i)，不会影响最优解，仅最优值在原来的基，不会影响最优解，仅最优值在原来的基础上减少了础上减少了min_out (i)。 于是，可以将距离矩阵的每一行和每一列都减于是，可以将距离矩阵的每一

44、行和每一列都减去该行或该列的最小值，直至每行每列都含有去该行或该列的最小值，直至每行每列都含有0为为止。止。 将上述矩阵的每行分别减去该行的最小值将上述矩阵的每行分别减去该行的最小值3, 4, 16, 7, 25, 3，就得到如下缩减之后的矩阵：，就得到如下缩减之后的矩阵：556 5 4 3 2 165432189431585008632130497383321202012912173873063010900 该缩减矩阵所对应该缩减矩阵所对应TSP的最优解与原来的相同，但最优的最优解与原来的相同，但最优值比原来减少了值比原来减少了3+4+16+7+25+3 = 58。 由于矩阵中第由于矩阵中第

45、3、4列中不含列中不含0元素，因此可继续缩减成：元素，因此可继续缩减成：56该缩减矩阵所对应该缩减矩阵所对应TSP的最优解与原来的相同，但最的最优解与原来的相同，但最优值比原来减少了优值比原来减少了3+4+16+7+25+3 = 58。由于矩阵中第由于矩阵中第3、4列中不含列中不含0元素，因此可继续缩减元素，因此可继续缩减成：成：57 其最优值比原来减少其最优值比原来减少58+15+8 = 81，这个，这个81可可作为该作为该TSP初始的下界值初始的下界值b。6543216 5 4 3 2 189350850004821304958833212012129121730580630275058按

46、按e63 = 1和和e63 = 0将解分成两种情况：将解分成两种情况：(1)e63 = 0 此时，边此时，边(6, 3)不能出现在回路中，其权值在不能出现在回路中，其权值在这种情况下为这种情况下为，因此，距离矩阵可修改为：，因此，距离矩阵可修改为：893585000482130495883321201212912173058063027506 5 4 3 2 165432159 由于第由于第3列没有列没有0元素，故用第元素，故用第3列各元素减去列各元素减去其最小元素其最小元素48，得如下缩减矩阵：，得如下缩减矩阵：8935850000213049108332120121291217301006

47、3022706 5 4 3 2 1654321 此时的下界此时的下界 b = 81 + 48 = 129。60(2)e63 = 1 此时，边此时，边(6, 3)已出现在回路中，从顶点已出现在回路中，从顶点6出发出发的其它边都不可能在回路中，因此可的其它边都不可能在回路中，因此可删去第删去第6行行；同理，进入到顶点同理，进入到顶点3的其它边都不可能在回路中，的其它边都不可能在回路中，因此又可因此又可删去第删去第3列列。此时，边。此时，边(3, 6)不可能出现在不可能出现在回路中，令边回路中，令边(3, 6)的权值为的权值为，矩阵化为：，矩阵化为：0021304983320121291217300

48、630206 5 4 2 15432161继续依次计算，并实施分继续依次计算，并实施分支和定界，具体过程如图支和定界，具体过程如图73所示：所示：图图73 降阶分支定界过程降阶分支定界过程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的分支剪去。62e63 = 1，e46 = 0下的缩减矩阵：下的缩减矩阵： 002131751001212912173006302

49、06 5 4 2 15432163e63 = e46 = 1下的缩减矩阵：下的缩减矩阵：0213012917300302053215 4 2 164e63 = e46 = 1，e21 = 0下的缩减矩阵：下的缩减矩阵：02100126013302053215 4 2 165e63 = e46 = e21 = 1下的缩减矩阵：下的缩减矩阵：020002805315 4 266e63 = e46 = e21 = 1，e14 = 0下的缩减矩阵：下的缩减矩阵：0200005315 4 267e63 = e46 = e21 = e14 = 1下的缩减矩阵：下的缩减矩阵：2000535 268e63 =

50、 e46 = 1，e21 = e51 = 0下的缩减矩阵：下的缩减矩阵：021010013302053215 4 2 169e63 = e46 = e51 =1，e21 = 0下的缩减矩阵：下的缩减矩阵：01011003215 4 270e63 = e46 = e51 = 1，e21 = e14 = 0下的缩减矩阵：下的缩减矩阵：010003215 4 271e63 = e46 = e51 = e14 = 1，e21 = 0下的缩减矩阵：下的缩减矩阵：000325 272 最后可得到两个最优最后可得到两个最优TSP回路：回路：(1, 4, 6, 3, 2, 5, 1) 和和 (1, 4, 6,

51、 3, 5, 2, 1)，最优回路长度为，最优回路长度为104。 若将无向图中的每条边看成有向图中方向相反若将无向图中的每条边看成有向图中方向相反的两条边，则无向图也可看成是有向图，因此，基的两条边，则无向图也可看成是有向图，因此，基于降阶的分支定界法也可用来求解无向于降阶的分支定界法也可用来求解无向TSP问题。问题。73三、动态规划法定理定理1 TSP满足满足最优性原理最优性原理。可以表述为：可以表述为：“一个过程的最优策一个过程的最优策略具有这样的性质略具有这样的性质,即无论初始状态和初始决策如何即无论初始状态和初始决策如何,对于先前决策所形成的状态而言对于先前决策所形成的状态而言,其以后

52、的所有决策其以后的所有决策必构成最优策略，必构成最优策略，”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

53、, s将是一条从将是一条从s出发的路出发的路径长度最短的简单回路且比径长度最短的简单回路且比s, s1, s2, , sp, s要短，要短，从而导致矛盾。所以，从而导致矛盾。所以，TSP满足最优性原理。满足最优性原理。75 设设TSP顶点编号分别为顶点编号分别为0，1，2，n，假设，假设从顶点从顶点0出发，令出发，令d (i, V )表示从顶点表示从顶点 i 出发经过出发经过V 中各顶点一次且仅一次，最后回到出发点中各顶点一次且仅一次，最后回到出发点0的最短的最短路径长度，中间计算过程中的路径长度，中间计算过程中的d (k, Vk)也表示也表示从顶点从顶点 k 出发经过出发经过Vk 中各顶点一

54、次且仅一次，中各顶点一次且仅一次，最后回到出发点最后回到出发点0（注意不是（注意不是k）的最短路径长度。）的最短路径长度。开始时，开始时，V = Vi，cij为顶点为顶点 i 至顶点至顶点 j 的距离，的距离，于是，于是，TSP的动态规划递推函数可写成：的动态规划递推函数可写成：76d (i, V ) = min cik + d (k, Vk) ( kV )d (k, ) = ck 0 ( k 0 )例例3 求解有向求解有向TSP：367523642375C77解：解： 从城市从城市0出发经城市出发经城市1、2、3然后回到城市然后回到城市0的最的最短路径长度为：短路径长度为：d (0, 1,

55、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)；这一阶段的决策又依赖于下述计算结果：这一阶段的决策又依赖于下述计算结果：78d (1, 2) = c12 + d (2, )

56、， 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 (10)，d (2, ) = c20 = 6 (20)，d (3, ) = c30 = 3 (30)； 79再向前倒推，有：再向前倒推，有：d (1, 2) = c12 + d (2, ) = 2

57、+ 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) = min 2

58、+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出

59、发的出发的TSP最短回路长度为最短回路长度为10，回路路径，回路路径为：为：01230。82四、近似算法 由于精确式算法所能求解的问题规模非常有限，由于精确式算法所能求解的问题规模非常有限，实际中真正使用的往往都是多项式阶数的近似算法实际中真正使用的往往都是多项式阶数的近似算法或启发式算法，算法的好坏用或启发式算法，算法的好坏用C/C*来衡量，其中，来衡量，其中，C为近似算法所得的总行程，为近似算法所得的总行程，C*为最优总行程，为最优总行程，为为最最“坏坏“情况下近似与最优总行程之比所不超过的情况下近似与最优总行程之比所不超过的上界值。这里，列举几个常见的上界值。这里，列举几个常见的TSP快

60、速近似算法。快速近似算法。83 旅行售货员问题的一些特殊性质特殊性质： 比如，费用函数w往往具有三角不等式性质三角不等式性质，即对任意的3个顶点u,v,wV，有：w(u,w)w(u,v)+w(v,w)。当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数w就具有三角不等式性质。 对于给定的无向图G，可以利用找图图G的最小的最小生成树生成树的算法设计找近似最优的旅行售货员回路的算法。 84 当费用函数满足三角不等式时，算法当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的优旅行售货员回路费用