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

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

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

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

4、点集为顶点集,E为边集为边集,各顶各顶 点间的距离点间的距离dij已知。设已知。设 1 , 0, ij i j x 若在回路路径上 其他 则经典的TSP可写为如下的数学规划模型: 11 1 1 m in 1,(71) 1,(72) s.t 1, , 21 (73) 0, 1 nn ijij ij n ij j n ij i ij iSjS ij Zd x xiV xjV xSSVSn x 2021/3/275 11 1 1 min 1,(7 1) 1,(7 2) s.t 1, ,21 (7 3) 0,1 nn ijij ij n ij j n ij i ij i S j S ij Zd x x

5、iV xjV xSSVSn x 模型中模型中,为集合中所含图的顶点数。约束（为集合中所含图的顶点数。约束（71） 和（和（72）意味着对每个点而言）意味着对每个点而言,仅有一条边进和一条仅有一条边进和一条 边出边出;约束（约束（73）则保证了没有任何子回路解的产生。）则保证了没有任何子回路解的产生。 于是于是,满足约束（满足约束（71）、（）、（72）和（）和（73）的解构）的解构 成了一条成了一条Hamilton回路。回路。 2021/3/276 当当dij=dji (i, jV) 时时,问题被称为问题被称为对称型对称型TSP,否否 则称为则称为非对称型非对称型TSP。 若对所有若对所有1i

6、, j, kn ,有不等式有不等式dij + djk dik成成 立立,则问题被称为是则问题被称为是满足三角形不等式满足三角形不等式的的,简称为简称为 TSP。 2021/3/277 2. 扩展扩展TSP (1) 瓶颈瓶颈TSP 瓶颈问题是最早从瓶颈问题是最早从TSP延伸出来的一种扩展型延伸出来的一种扩展型 TSP,其含义与经典的其含义与经典的TSP类似类似,仅目标不同仅目标不同,要求巡要求巡 回路线中经过的最长距离最短回路线中经过的最长距离最短,即最小化瓶颈距离。即最小化瓶颈距离。 该情形体现了那些并不追求总巡回路线最短该情形体现了那些并不追求总巡回路线最短,而只希而只希 望在巡回路线中每次

7、从一个地点至另一个地点的单望在巡回路线中每次从一个地点至另一个地点的单 次行程尽可能短的实际应用问题的特征。次行程尽可能短的实际应用问题的特征。 2021/3/278 从严格的数学意义而言从严格的数学意义而言,瓶颈瓶颈TSP（简称（简称BTSP）并）并 没有降低问题的难度没有降低问题的难度,也未能提供任何特殊的解决办法。也未能提供任何特殊的解决办法。 瓶颈瓶颈TSP的数学模型与标准的数学模型与标准TSP类似类似,仅目标函数仅目标函数 不同不同: min Zmax, ijij dxi jV 由于目标函数为瓶颈值由于目标函数为瓶颈值,故求得的最佳巡回路故求得的最佳巡回路 线与标准线与标准TSP的往

8、往截然不同。的往往截然不同。 2021/3/279 (2) 最小比率最小比率TSP 最小比率最小比率TSP（简称（简称MRTSP）是从经典）是从经典TSP 引申出来的另一个变形问题引申出来的另一个变形问题,假定从一个城市走到另假定从一个城市走到另 一个城市可得到某种收益（记为）一个城市可得到某种收益（记为）,则则MRTSP的目的目 标就是确定最佳行走路线标就是确定最佳行走路线,使得回路的总行程与总收使得回路的总行程与总收 益之比最小。这种优化目标的思想类似于人们日常益之比最小。这种优化目标的思想类似于人们日常 生活中经常使用的费用效益比生活中经常使用的费用效益比,与单纯的总行程最短与单纯的总行

9、程最短 相比相比,往往更具实际意义。往往更具实际意义。 2021/3/2710 假定收益的数学性质与相同假定收益的数学性质与相同,则最小比率则最小比率TSP的的 数学模型也与标准数学模型也与标准TSP类似类似,仅目标函数不同仅目标函数不同: 毫无疑问毫无疑问,由于目标函数中的非线性因素由于目标函数中的非线性因素,最小最小 比率比率TSP的求解比之标准的求解比之标准TSP显得更为困难。显得更为困难。 m in ijij ij ijij ij dx Z px 2021/3/2711 (3) 多人多人TSP 若标准若标准TSP中中,出发点有多个推销员同时出发出发点有多个推销员同时出发,各自行走各自行

10、走 不同的路线不同的路线,使得所有的城市都至少被访问过一次使得所有的城市都至少被访问过一次,然后返回然后返回 出发点出发点,要求所有推销员的总行程最短要求所有推销员的总行程最短,则问题就成为一个多则问题就成为一个多 人的旅行商问题（简记人的旅行商问题（简记MTSP）。）。 令决策变量令决策变量 则则MTSP的数学模型为的数学模型为: 1, 0, ij ij x 若有某推销员从城市 到城市 否则 2021/3/2712 -1 10 -1 0 -1 0 min 1,1, 2,1 ,0 1,1, 2,1 . . ,0 0,1,0, mn ijij ij n kj k n ik k ijii Zd x

11、 jn x mj in xs t mi xxi j 对 对 对 对 且 不 存 在 任 何 子 回 路 假定原问题为对称型假定原问题为对称型MTSP,V=v0,v1,vn- 1,v0为名推销员出发点 为名推销员出发点,记记V=v01,v02,v0m; v0,v1,vn-1 ,扩大的扩大的m-1个顶点称为个顶点称为“人造顶点人造顶点”, 其距离矩阵也相应扩大其距离矩阵也相应扩大,其中其中,位于出发点的位于出发点的m个顶个顶 点相互间的距离设定为点相互间的距离设定为,其他数值不变。其他数值不变。 2021/3/2713 二、多面体理论二、多面体理论 从上世纪从上世纪70年代开始的关于算法复杂性的研

12、年代开始的关于算法复杂性的研 究表明究表明,要想为要想为TSP找到一个好的算法找到一个好的算法,也即多项式也即多项式 算法算法,似乎是不可能的。由于推销员的每条路线可以似乎是不可能的。由于推销员的每条路线可以 用一个以用一个以1开始的排列来表示开始的排列来表示,因此所有可能的路线因此所有可能的路线 有条。这样有条。这样,若用枚举法来解决这一问题若用枚举法来解决这一问题,即使不太即使不太 大大,例如例如n30,用目前最快的计算机用目前最快的计算机,也要化几百万也要化几百万 年才能求出一条最短的路线。年才能求出一条最短的路线。 2021/3/2714 早在早在1954年年,Dantzig等人就曾提

13、出过一种方等人就曾提出过一种方 法（非多项式算法）法（非多项式算法）,并且求出了一个并且求出了一个42城市的城市的TSP 最优解。到了最优解。到了1960年代年代,不少人用分支定界法解决不少人用分支定界法解决 了许多有几十个城市的了许多有几十个城市的TSP。还有人提出了一些近。还有人提出了一些近 似方法似方法,也解决了许多有几十个城市甚至上百个城市也解决了许多有几十个城市甚至上百个城市 的的TSP（有时找到的仅是近似解）。更值得注意的（有时找到的仅是近似解）。更值得注意的 是是,从从1970年代中期开始年代中期开始,Grotschel与与Padberg等人等人 深入研究了深入研究了TS多面体的

14、最大面多面体的最大面（facet）,并从所得并从所得 结果出发获得了一种解结果出发获得了一种解TSP的新算法的新算法,可以解决一些可以解决一些 有有100多个城市的多个城市的TSP,且都在不长的时间内找到了且都在不长的时间内找到了 最优解。最优解。 2021/3/2715 考虑个顶点的完全图考虑个顶点的完全图Kn ,则解则解TSP就相当于在就相当于在 中求一条总长度最短的中求一条总长度最短的Hamilton回路。现在回路。现在,对每对每 条边条边ej,定义一个变量定义一个变量xj与之对应与之对应,这样这样,TSP的一条路的一条路 线线T,即即Kn的一条的一条Hamilton回路回路,就可对应一

15、个向量就可对应一个向量 X=x1,x2,.xm,其中其中, 1, 0, jj jj xeT xeT 若 若 2021/3/2716 称称X为路线为路线T的关联向量的关联向量,其其m=n(n-2)/2个分量中个分量中,恰好有恰好有 个为个为1,其余的都为其余的都为0。 图有许多图有许多Hamilton回路回路,设为设为T1, T2 Ts,对应的关联向对应的关联向 量记为量记为X1, X2 Xs ,在在m维空间维空间Rm中中,考虑这些向量生成的凸考虑这些向量生成的凸 包（包（convex hull） Qn : 11 1,0,1,2, ss ni iii ii QXis 2021/3/2717 Qn

16、是是Rm中的一个凸多面体中的一个凸多面体,称做称做TS多面体。显多面体。显 然然, Qn是有界的是有界的,其极点正好是其极点正好是Kn的的Hamilton回路关回路关 联向量。联向量。 研究研究Qn的面非常重要的的面非常重要的,因为根据线性不等式及因为根据线性不等式及 凸多面体的理论凸多面体的理论, Qn一定是某一个有限线性不等式一定是某一个有限线性不等式 组的解集合组的解集合,或者说或者说, Qn一定是有限多个半空间的交。一定是有限多个半空间的交。 因此因此,如果能找出定义如果能找出定义Qn的线性不等式组来的线性不等式组来,就可将就可将 TSP作为一个线性规划来解。作为一个线性规划来解。 2

17、021/3/2718 TS多面体研究中的一个重要问题就是寻找能导出多面体研究中的一个重要问题就是寻找能导出Qn 最大面的不等式最大面的不等式,Grotschel等人发现了一类很重要的能导等人发现了一类很重要的能导 出最大面的梳子不等式出最大面的梳子不等式,并予以了证明。此外并予以了证明。此外,还有其它能导还有其它能导 出最大面的不等式出最大面的不等式,如团树不等式等。可见如团树不等式等。可见, Qn的最大面极的最大面极 多多,曾经计算过由梳子不等式所导出的最大面个数如表曾经计算过由梳子不等式所导出的最大面个数如表71 所示所示: n6810203050120 c(n)60414201.5*10

18、181.5*103110602*10179 表表71 2021/3/2719 可以看出可以看出,当增大时当增大时,最大面个数增长得非常快。最大面个数增长得非常快。 在在TS多面体理论的基础上多面体理论的基础上,可以考虑先解可以考虑先解TSP的松弛问的松弛问 题题,如果得到的最优解正好是某一条路线的关联向量如果得到的最优解正好是某一条路线的关联向量,那么就那么就 找到找到TSP的最优解了的最优解了;否则否则,就设法找一些新的不等式作为额就设法找一些新的不等式作为额 外约束外约束,再解新的线性规划再解新的线性规划,直至找到恰好是关联向量的最优直至找到恰好是关联向量的最优 解。这种做法的基本思想与解

19、整数规划的割平面法是同一类解。这种做法的基本思想与解整数规划的割平面法是同一类 的的,Gotschel 等人曾用这种方法解过有等人曾用这种方法解过有120个城市的个城市的TSP,所所 增加的不等式只有子回路消去不等式与梳子不等式两类增加的不等式只有子回路消去不等式与梳子不等式两类,在在 进行了进行了13轮计算后轮计算后,即解了即解了13个线性规划后个线性规划后,就找到了就找到了TSP的的 精确最优解精确最优解,每一轮的当时计算时间仅在每一轮的当时计算时间仅在30秒至秒至2分钟之间。分钟之间。 有趣的是有趣的是,当当n = 120时时,仅梳子不等式就有仅梳子不等式就有2*10179个个,但在计但

20、在计 算过程中算过程中,总共却只（凭经验）添加了总共却只（凭经验）添加了96个子回路消去不等个子回路消去不等 式与梳子不等式。式与梳子不等式。 2021/3/2720 当然当然,用该方法有时会用该方法有时会找不到找不到TSP的最优解的最优解, 因为很可能在进行了几轮迭代后因为很可能在进行了几轮迭代后,却找不到新的不等却找不到新的不等 式。式。Padborg与与Hong曾计算了曾计算了74个个TSP,其中其中54个个 得到了最优解得到了最优解,其余的虽未得到最优解其余的虽未得到最优解,却得到了很却得到了很 好的下界好的下界,如果与近似方法配合如果与近似方法配合,可以估计近似解的可以估计近似解的

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

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

23、例1 已知已知TSP及其距离矩阵如图及其距离矩阵如图71所示所示,试求其下试求其下 界界 2 71 56 3 1 34 2 5 3 9 8 4 (a) 无向图无向图 图图71 无向图无向图 及距离矩阵及距离矩阵 (b) 距离矩阵距离矩阵 3298 3475 2451 9763 8513 2021/3/2723 解解: 将矩阵中每一行最小的元素相加将矩阵中每一行最小的元素相加,1+3+1+3+2 = 10,即得即得b1=10。将矩阵中每一行最小的两个元素相。将矩阵中每一行最小的两个元素相 加再除以加再除以2,再对结果向上取整再对结果向上取整,即可得即可得b2 = (1+3) + (3+6) +

24、(1+2) + (3+4) + (2+3)/2 = 14。 2021/3/2724 （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) 长边长边 的另一个结点的编号的另一个结点的编号(其中一个结点编号为其中一个结

25、点编号为i); node_ base(i)= dmin_j(i, 1)+ dmin_j(i, 2):表示与表示与i点关联边中点关联边中 长度最短的两条边之和长度最短的两条边之和; C*(T):最优回路长度最优回路长度; 2021/3/2725 于是于是,dmin(i, 1)代表与第代表与第i个结点关联的所有边个结点关联的所有边 中最长边的长度中最长边的长度,dmin_j(i, 1) 代表与第代表与第i个结点关联个结点关联 的所有边中次长边的另一个结点编号的所有边中次长边的另一个结点编号(其中一个结点其中一个结点 编号为编号为i),第第i结点的结点的dmin(i, k)和和dmin_j(i, k

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

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

28、的一个结点为的一个结点为i,另一个另一个 结点为结点为j = dmin_j (i,1),若若e (i)1也是结点也是结点j关联边中关联边中 最小的两条边之一最小的两条边之一,即即 i = dmin_j (j,1) 或或 i = dmin_j (j,2),则对边则对边e (i)1来说就不需要调整来说就不需要调整,否则按以下方否则按以下方 式调整式调整: 2021/3/2728 若若e (i)1不是结点不是结点j=dmin_j(i,1)关联边中最小的两条边关联边中最小的两条边 之一之一,则只有以下两种情况则只有以下两种情况: 选中选中e (i)1到到TSP回路中回路中 此时对结点此时对结点i不需调

29、整不需调整,对结点对结点j来说来说,由于边由于边e (i)1出现在最优回路中出现在最优回路中,而而e (i)1不是结点不是结点j关联边中最关联边中最 小的两条边之一小的两条边之一,因此会造成结点因此会造成结点j关联边中最小的关联边中最小的 两条边中至少有一条不会出现在最优回路中两条边中至少有一条不会出现在最优回路中,从而对从而对 结点结点j而言而言,在在node_base (i)的基础上至少会增加的的基础上至少会增加的 长度为长度为 dmin (i,1) dmin (j,2) 。 2021/3/2729 不选中不选中e (i)1到到TSP回路中回路中 此时对结点此时对结点i需要调整需要调整,由

30、于边由于边e (i)1不在回路不在回路 中中,故其在故其在node_base (i)的基础上至少会增加的长的基础上至少会增加的长 度为度为 dmin (i,3) dmin (i,1)。 此时对结点此时对结点j来说来说,由于与它关联的最短两条边由于与它关联的最短两条边 仍然可能在回路中仍然可能在回路中,因此不须调整。因此不须调整。 2021/3/2730 对于和对于和,必须有且仅有一种情况出现必须有且仅有一种情况出现,现取两种情现取两种情 况中增加长度小的值况中增加长度小的值,因而回路的长路一定会在因而回路的长路一定会在b2的基础上的基础上 增加增加:add_node (i,1) = 1/2*m

31、in (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) dm

32、in (i,2), dmin (i,2) dmin (j,2)。 2021/3/2731 将每个结点都按上述方法进行一次调整将每个结点都按上述方法进行一次调整,其调其调 整累加和就是整累加和就是Adjust (T),可写成如下公式可写成如下公式: 1 ( )( 1)( 2) n i= Adjust Tadd_node i,+add_node i, 2021/3/2732 将问题将问题T中所有结点的基本长度中所有结点的基本长度node_base(T) 累加之和的一半称为累加之和的一半称为T的基本长度的基本长度,并用并用base (T)来来 表示表示,可写成如下公式可写成如下公式: 1 2 1 (

33、 )1/2*( ,1)( ,2) 1/2*( ) n i n i base Tdmin idmin i node_base ib 2021/3/2733 于是于是,有有C*(T) base(T) + Adjust(T) = b3,即即 b3 = b2 + Adjust(T) 。 由以上分析由以上分析,不难得出求对称不难得出求对称TSP下界下界b3的算法的算法: 2021/3/2734 Step 1. 计算计算base (T): get_base () i: Long For i = 1 To n base = base + dmin(i, 1) + dmin(i, 2) 2021/3/2735

34、 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)-dmi

35、n(i, 2),dmin(i, 2)-dmin(ii2, 2) 2021/3/2736 对例对例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

36、; dmin(3, 3)=4;dmin_j(3, 3)=4; 2 71 56 3 1 34 2 5 3 9 8 4 (a) 无向图无向图 图图71 无向图无向图 2021/3/2737 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 71 56 3 1 34 2 5 3 9 8 4 (a) 无向

37、图无向图 图图71 无向图无向图 5 2 11 1/2*( )1/2*( ,1)( ,2) (13)(36)(12)(34)(23)/214 n ii bnode_base idmin idmin i 2021/3/2738 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), (4-2)=1/2; add_node(4,1)=0; add_node(4,2)= 0 ; add_n

38、ode(5,1)=0; add_node(5,2)= 0; 所以所以,Adjust(T) = 1/2+1/2=1,得得b3 = b2 +Adjust(T)= 14 + 1 = 15。 2021/3/2739 2. 上界上界 事实上事实上,TSP的任何可行解都是上界的任何可行解都是上界,这里这里,给出给出 求求TSP上界上界U1的贪心方法思想。的贪心方法思想。 算法步骤如下算法步骤如下: 2021/3/2740 Step 1. 图图G = V, E中顶点个数为中顶点个数为n = |V|,边的条数边的条数m = |E|,令令i为出发点为出发点,TSP_edge_n为加入到为加入到TSP回路回路 中

39、边的条数且中边的条数且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 U1, 故剪支 e12=0 e12=1 b2 = 17 U1, 故剪支 得最优解e12=e13= e24= e35= e54

40、=1, e14=e15= e23= e25= e34=0 e25=0 e25=1 b2 = 18.5 U1=16, 故剪支 此时有e14=e15= e23=0 此时有e24= e35= e54=1, e34 = 0 2021/3/2748 (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

41、 = 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; 2021/3/2749 (4) 在在e12 = e13 = 1的情况下的情况下,由于顶点由于顶点1已有两条关联已有两条关联 边在最优回路中边在最优回路中,因此在图因此在图71中中删去删去边边(1, 4)和和(1, 5),由于边由于边(2, 3)与边与边(1, 2)、(1, 3)形成圈形成圈,因此在图

42、因此在图 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; 2021/3/2750 (6)在在e12 = e13 = 1,e14 = e15 = e23 = e25 = 0的情况下的情况下,由由 于与顶点于与顶点

43、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。 2021/3/2751 2. 基于降阶的分支定界法基于降阶的分支定界法 对于对于有向有向TSP的距离距阵的距离距阵,可通过不同情况下可通过不同情况下 上下界的对比来确定某些边上下界的对比来确定某些边(i, j)一定在或不在回路一定在或不

44、在回路 中。如果能确定中。如果能确定(i, j)一定在回路中一定在回路中,由于每个顶点分由于每个顶点分 别别有且只有一条入边和出边有且只有一条入边和出边,从而可确定顶点从而可确定顶点i的其的其 它出边一定不在回路中它出边一定不在回路中,也可以确定顶点也可以确定顶点j的其它出的其它出 边一定不在回路中边一定不在回路中,因此可将这些边从距离距阵中去因此可将这些边从距离距阵中去 掉掉,从而达到从而达到降低矩阵阶数降低矩阵阶数的目的。的目的。 这里这里,以一个具体的例子来予以说明。以一个具体的例子来予以说明。 2021/3/2752 例例2 已知有向已知有向TSP的距离矩阵如下的距离矩阵如下: 6 5

45、 4 3 2 1 6 5 4 3 2 1 924618883 2533884628 756809039 2816361745 162142774 93313933 2021/3/2753 解解: 由于每个顶点都必须有一条入边和出边由于每个顶点都必须有一条入边和出边,因此因此将顶将顶 点点i的所有出边的权值减去所有出边权值的最小值的所有出边的权值减去所有出边权值的最小值 min_out(i),不会影响最优解不会影响最优解,仅最优值在原来的基础仅最优值在原来的基础 上减少了上减少了min_out (i)。 于是于是,可以将距离矩阵的每一行和每一列都减去可以将距离矩阵的每一行和每一列都减去 该行或该

46、列的最小值该行或该列的最小值,直至每行每列都含有直至每行每列都含有0为止。为止。 将上述矩阵的每行分别减去该行的最小值将上述矩阵的每行分别减去该行的最小值3, 4, 16, 7, 25, 3,就得到如下缩减之后的矩阵就得到如下缩减之后的矩阵: 2021/3/2754 6 5 4 3 2 1 6 5 4 3 2 1 894315850 0863213 049738332 12020129 121738730 63010900 该缩减矩阵所对应该缩减矩阵所对应TSP的最优解与原来的相同的最优解与原来的相同,但最优但最优 值比原来减少了值比原来减少了3+4+16+7+25+3 = 58。 由于矩阵中

47、第由于矩阵中第3、4列中不含列中不含0元素元素,因此可继续缩减成因此可继续缩减成: 2021/3/2755 该缩减矩阵所对应该缩减矩阵所对应TSP的最优解与原来的相同的最优解与原来的相同,但最优但最优 值比原来减少了值比原来减少了3+4+16+7+25+3 = 58。 由于矩阵中第由于矩阵中第3、4列中不含列中不含0元素元素,因此可继续缩减成因此可继续缩减成: 2021/3/2756 其最优值比原来减少其最优值比原来减少58+15+8 = 81,这个这个81可可 作为该作为该TSP初始的下界值初始的下界值b。 6 5 4 3 2 1 6 5 4 3 2 1 89350850 0048213 0

48、49588332 12012129 121730580 6302750 2021/3/2757 按按e63 = 1和和e63 = 0将解分成两种情况将解分成两种情况: (1)e63 = 0 此时此时,边边(6, 3)不能出现在回路中不能出现在回路中,其权值在这其权值在这 种情况下为种情况下为,因此因此,距离矩阵可修改为距离矩阵可修改为: 8935850 0048213 049588332 12012129 121730580 6302750 6 5 4 3 2 1 6 5 4 3 2 1 2021/3/2758 由于第由于第3列没有列没有0元素元素,故用第故用第3列各元素减去列各元素减去 其最

49、小元素其最小元素48,得如下缩减矩阵得如下缩减矩阵: 8935850 000213 049108332 12012129 121730100 6302270 6 5 4 3 2 1 6 5 4 3 2 1 此时的下界此时的下界 b = 81 + 48 = 129。 2021/3/2759 (2)e63 = 1 此时此时,边边(6, 3)已出现在回路中已出现在回路中,从顶点从顶点6出发的出发的 其它边都不可能在回路中其它边都不可能在回路中,因此可因此可删去第删去第6行行;同理同理, 进入到顶点进入到顶点3的其它边都不可能在回路中的其它边都不可能在回路中,因此又可因此又可 删去第删去第3列列。此时

50、。此时,边边(3, 6)不可能出现在回路中不可能出现在回路中,令令 边边(3, 6)的权值为的权值为,矩阵化为矩阵化为: 00213 0498332 012129 1217300 63020 6 5 4 2 1 5 4 3 2 1 2021/3/2760 继续依次计算继续依次计算,并实施分支并实施分支 和定界和定界,具体过程如图具体过程如图73 所示所示: 图图73 降阶分支定界过程降阶分支定界过程 b = 81 e63 =0e63 =1 b =129 e46 =0 e46 =1 b =113 e21 =0 e21 =1 b =81 b =81 b =84b =101 e14 =1 e14 =

51、0 b = 84b =112 得可行回路(1,4,6,3,5,2,1), 回路总长104， 由此可将下界b大于104的分支剪去。 2021/3/2761 e63 = 1,e46 = 0下的缩减矩阵下的缩减矩阵: 00213 17510 012129 1217300 63020 6 5 4 2 1 5 4 3 2 1 2021/3/2762 e63 = e46 = 1下的缩减矩阵下的缩减矩阵: 0213 0129 17300 3020 5 3 2 1 5 4 2 1 2021/3/2763 e63 = e46 = 1,e21 = 0下的缩减矩阵下的缩减矩阵: 0210 0126 013 3020

52、 5 3 2 1 5 4 2 1 2021/3/2764 e63 = e46 = e21 = 1下的缩减矩阵下的缩减矩阵: 020 00 280 5 3 1 5 4 2 2021/3/2765 e63 = e46 = e21 = 1,e14 = 0下的缩减矩阵下的缩减矩阵: 020 00 0 5 3 1 5 4 2 2021/3/2766 e63 = e46 = e21 = e14 = 1下的缩减矩阵下的缩减矩阵: 20 00 5 3 5 2 2021/3/2767 e63 = e46 = 1,e21 = e51 = 0下的缩减矩阵下的缩减矩阵: 021 010 013 3020 5 3 2

53、1 5 4 2 1 2021/3/2768 e63 = e46 = e51 =1,e21 = 0下的缩减矩阵下的缩减矩阵: 01 011 00 3 2 1 5 4 2 2021/3/2769 e63 = e46 = e51 = 1,e21 = e14 = 0下的缩减矩阵下的缩减矩阵: 01 00 0 3 2 1 5 4 2 2021/3/2770 e63 = e46 = e51 = e14 = 1,e21 = 0下的缩减矩阵下的缩减矩阵: 00 0 3 2 5 2 2021/3/2771 最后可得到两个最优最后可得到两个最优TSP回路回路:(1, 4, 6, 3, 2, 5, 1) 和和 (1

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

55、言对于先前决策所形成的状态而言,其以后的所有决策其以后的所有决策 必构成最优策略必构成最优策略,” 2021/3/2773 证证: 设设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个个 不同

56、城市不同城市,则则s, s1, r1, r2, , rq, s将是一条从将是一条从s出发出发 的路径长度最短的简单回路且比的路径长度最短的简单回路且比s, s1, s2, , sp, s 要短要短,从而导致矛盾。所以从而导致矛盾。所以,TSP满足最优性原理。满足最优性原理。 2021/3/2774 设设TSP顶点编号分别为顶点编号分别为0,1,2,n,假设从顶点假设从顶点 0出发出发,令令d (i, V )表示从顶点表示从顶点 i 出发经过出发经过V 中各顶点中各顶点 一次且仅一次一次且仅一次,最后回到出发点最后回到出发点0的最短路径长度的最短路径长度,中中 间计算过程中的间计算过程中的d (

57、k, Vk)也表示从顶点也表示从顶点 k 出发出发 经过经过Vk 中各顶点一次且仅一次中各顶点一次且仅一次,最后回到出发最后回到出发 点点0（注意不是（注意不是k）的最短路径长度。开始时）的最短路径长度。开始时,V = V i,cij为顶点为顶点 i 至顶点至顶点 j 的距离的距离,于是于是,TSP的动态规的动态规 划递推函数可写成划递推函数可写成: 2021/3/2775 d (i, V ) = min cik + d (k, Vk) ( kV ) d (k, ) = ck 0 ( k 0 ) 例例3 求解有向求解有向TSP: 367 523 642 375 C 2021/3/2776 解解

58、: 从城市从城市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 (

59、2, 1); 这一阶段的决策又依赖于下述计算结果这一阶段的决策又依赖于下述计算结果: 2021/3/2777 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, ); 而下式可以直接获得（括号中是该决策引起的状态转而下式可以直接获得（括号中是该决策引起的状态转 移）移）: d (1, ) = c10 = 5 (10), d (2, ) = c2

60、0 = 6 (20), d (3, ) = c30 = 3 (30); 2021/3/2778 再向前倒推再向前倒推,有有: 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