《数学建模经典问题——旅行商问题精选PPT.ppt》由会员分享，可在线阅读，更多相关《数学建模经典问题——旅行商问题精选PPT.ppt（105页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于数学建模经典问题旅行商问题第1页，讲稿共105张，创作于星期二2第第7章章 旅行商旅行商问题1.问题概述问题概述 2.求解算法求解算法 2.1.下界和上界算法下界和上界算法2.2.分支定界法分支定界法 目录目录2.5.竞赛题竞赛题2.3.动态规划法动态规划法2.5.近似算法近似算法第2页，讲稿共105张，创作于星期二37-1 问题概述问题概述 一、数学模型一、数学模型 1.标准准TSP 旅行商旅行商问题（简称称TSP），也称），也称货郎担郎担问题或或旅行推旅行推销员问题，是运筹学中一个著名的，是运筹学中一个著名的问题，其，其一般提法一般提法为：有一个旅行商从城市：有一个旅行商从城市1出出发
2、，需要到城，需要到城市市2、3、n去推去推销货物，最后返回城市物，最后返回城市1，若任，若任意两个城市意两个城市间的距离已知，的距离已知，则该旅行商旅行商应如何如何选择其最佳行走路其最佳行走路线？第3页，讲稿共105张，创作于星期二4 TSP在在图论意意义下又常常被称下又常常被称为最小最小Hamilton圈圈问题，Euler等人最早研究了等人最早研究了该问题的的雏形，后来由英国的形，后来由英国的Hamilton爵士作爵士作为一一个个悬赏问题而提出。但而提出。但这个能个能让普通人在几分普通人在几分钟内就可理解的游内就可理解的游戏之作，却延之作，却延续至今仍未能完全解决，成了一个世界至今仍未能完全
3、解决，成了一个世界难题。TSP有着明有着明显的的实际意意义，如，如，邮局里局里负责到各信箱开箱取信的到各信箱开箱取信的邮递员，以及去各分局送，以及去各分局送邮件的汽件的汽车等，都会遇到等，都会遇到类似的似的问题。有趣的是，。有趣的是，还有一些有一些问题表面上看似乎与表面上看似乎与TSP无关，而无关，而实质上却可以上却可以归结为TSP来求解。已来求解。已经证明，明，TSP是个是个NP难题，除非，除非P=NP，否，否则不存在不存在有效算法。有效算法。第4页，讲稿共105张，创作于星期二5 记为赋权图G=(V,E)，V为顶点集，点集，E为边集，集，各各顶点点间的距离的距离dij已知。已知。设则经典的
4、TSP可写为如下的数学规划模型：第5页，讲稿共105张，创作于星期二6 模模型型中中，为集集合合中中所所含含图的的顶点点数数。约束束（71）和和（72）意意味味着着对每每个个点点而而言言，仅有有一一条条边进和和一一条条边出出；约束束（73）则保保证了了没没有有任任何何子子回回路路解解的的产生生。于于是是，满足足约束束（71）、（72）和和（73）的的解解构构成成了了一一条条Hamilton回路。回路。第6页，讲稿共105张，创作于星期二7 当当dij=dji (i,jV)时，问题被称被称为对称型称型TSP，否，否则称称为非非对称型称型TSP。若若对所有所有1i,j,kn，有不等式，有不等式di
5、j+djk dik成立，成立，则问题被称被称为是是满足三角形不等式足三角形不等式的，的，简称称为TSP。第7页，讲稿共105张，创作于星期二82.扩展展TSP(1)瓶瓶颈TSP 瓶瓶颈问题是最早从是最早从TSP延伸出来的一种延伸出来的一种扩展型展型TSP，其含，其含义与与经典的典的TSP类似，似，仅目目标不同，要不同，要求巡回路求巡回路线中中经过的最的最长距离最短，即最小化瓶距离最短，即最小化瓶颈距离。距离。该情形体情形体现了那些并不追求了那些并不追求总巡回路巡回路线最短，最短，而只希望在巡回路而只希望在巡回路线中每次从一个地点至另一个地中每次从一个地点至另一个地点的点的单次行程尽可能短的次行
6、程尽可能短的实际应用用问题的特征。的特征。第8页，讲稿共105张，创作于星期二9 从从严格的数学意格的数学意义而言，瓶而言，瓶颈TSP（简称称BTSP）并）并没有降低没有降低问题的的难度，也未能提供任何特殊的解决度，也未能提供任何特殊的解决办法。法。瓶瓶颈TSP的数学模型与的数学模型与标准准TSP类似，似，仅目目标函数函数不同：不同：由于目由于目标函数函数为瓶瓶颈值，故求得的最佳巡回路，故求得的最佳巡回路线与与标准准TSP的往往截然不同。的往往截然不同。第9页，讲稿共105张，创作于星期二10(2)最小比率最小比率TSP 最小比率最小比率TSP（简称称MRTSP）是从）是从经典典TSP引引申出
7、来的另一个申出来的另一个变形形问题，假定从一个城市走到另，假定从一个城市走到另一个城市可得到某种收益（一个城市可得到某种收益（记为），），则MRTSP的目的目标就是确定最佳行走路就是确定最佳行走路线，使得回路的，使得回路的总行程与行程与总收益之比最小。收益之比最小。这种种优化目化目标的思想的思想类似于人似于人们日日常生活中常生活中经常使用的常使用的费用效益比，与用效益比，与单纯的的总行程行程最短相比，往往更具最短相比，往往更具实际意意义。第10页，讲稿共105张，创作于星期二11 假定收益的数学性假定收益的数学性质与相同，与相同，则最小比率最小比率TSP的的数学模型也与数学模型也与标准准TSP
8、类似，似，仅目目标函数不同：函数不同：毫无疑毫无疑问，由于目，由于目标函数中的非函数中的非线性因素，最小比率性因素，最小比率TSP的求解比之的求解比之标准准TSP显得更得更为困困难。第11页，讲稿共105张，创作于星期二12(3)多人多人TSP 若若标准准TSP中中，出，出发点有多个推点有多个推销员同同时出出发，各自行走不同的路，各自行走不同的路线，使得所有的城市都至少被，使得所有的城市都至少被访问过一次，然后返回出一次，然后返回出发点，要求所有点，要求所有推推销员的的总行程最短，行程最短，则问题就成就成为一个多人的旅行商一个多人的旅行商问题（简记MTSP）。）。令决策令决策变量量则MTSP的
9、数学模型的数学模型为：第12页，讲稿共105张，创作于星期二13 假定原假定原问题为对称型称型MTSP，V=v0,v1,vn-1，v0为名推名推销员出出发点，点，记V=v01,v02,v0m;v0,v1,vn-1，扩大的大的m-1个个顶点称点称为“人造人造顶点点”，其距离，其距离矩矩阵也相也相应扩大，其中，位于出大，其中，位于出发点的点的m个个顶点相点相互互间的距离的距离设定定为，其他数，其他数值不不变。第13页，讲稿共105张，创作于星期二14二、多面体理二、多面体理论 从上世从上世纪70年代开始的关于算法复年代开始的关于算法复杂性的研究性的研究表明，要想表明，要想为TSP找到一个好的算法，
10、也即多找到一个好的算法，也即多项式式算法，似乎是不可能的。由于推算法，似乎是不可能的。由于推销员的每条路的每条路线可可以用一个以以用一个以1开始的排列来表示，因此所有可能的路开始的排列来表示，因此所有可能的路线有条。有条。这样，若用枚，若用枚举法来解决法来解决这一一问题，即使，即使不太大，例如不太大，例如n30，用目前最快的，用目前最快的计算机，也要化算机，也要化几百万年才能求出一条最短的路几百万年才能求出一条最短的路线。第14页，讲稿共105张，创作于星期二15 早在早在1954年，年，Dantzig等人就曾提出等人就曾提出过一种方一种方法（非多法（非多项式算法），并且求出了一个式算法），并
11、且求出了一个42城市的城市的TSP最最优解。到了解。到了1960年代，不少人用分支定界法年代，不少人用分支定界法解决了解决了许多有几十个城市的多有几十个城市的TSP。还有人提出了一有人提出了一些近似方法，也解决了些近似方法，也解决了许多有几十个城市甚至上百多有几十个城市甚至上百个城市的个城市的TSP（有（有时找到的找到的仅是近似解）。更是近似解）。更值得得注意的是，从注意的是，从1970年代中期开始，年代中期开始，Grotschel与与Padberg等人深入研究了等人深入研究了TS多面体的最大面多面体的最大面（facet），并从所得），并从所得结果出果出发获得了一种解得了一种解TSP的的新算法
12、，可以解决一些有新算法，可以解决一些有100多个城市的多个城市的TSP，且都，且都在不在不长的的时间内找到了最内找到了最优解。解。第15页，讲稿共105张，创作于星期二16 考考虑个个顶点的完全点的完全图Kn，则解解TSP就相当于在就相当于在中求一条中求一条总长度最短的度最短的Hamilton回路。回路。现在，在，对每每条条边ej，定，定义一个一个变量量xj与之与之对应，这样，TSP的一的一条路条路线T，即，即Kn的一条的一条Hamilton回路，就可回路，就可对应一一个向量个向量X=x1,x2,.xm，其中，其中，第16页，讲稿共105张，创作于星期二17 称称X为路路线T的关的关联向量，其
13、向量，其m=n(n-2)/2个分量中，恰好有个个分量中，恰好有个为1，其余的都，其余的都为0。图有有许多多Hamilton回路，回路，设为T1,T2 Ts,，对应的关的关联向量向量记为X1,X2 Xs，在，在m维空空间Rm中，考中，考虑这些向量生成的凸包（些向量生成的凸包（convex hull）Qn：第17页，讲稿共105张，创作于星期二18 Qn是是Rm中的一个凸多面体，称做中的一个凸多面体，称做TS多面体。多面体。显然，然，Qn是有界的，其极点正好是是有界的，其极点正好是Kn的的Hamilton回路回路关关联向量。向量。研究研究Qn的面非常重要的，因的面非常重要的，因为根据根据线性不等式
14、性不等式及凸多面体的理及凸多面体的理论，Qn一定是某一个有限一定是某一个有限线性不等性不等式式组的解集合，或者的解集合，或者说，Qn一定是有限多个半空一定是有限多个半空间的交。因此，如果能找出定的交。因此，如果能找出定义Qn的的线性不等式性不等式组来，来，就可将就可将TSP作作为一个一个线性性规划来解。划来解。第18页，讲稿共105张，创作于星期二19 TS多面体研究中的一个重要问题就是寻找能导出多面体研究中的一个重要问题就是寻找能导出Qn最大面的不等式，最大面的不等式，Grotschel等人发现了一类很重要的能导等人发现了一类很重要的能导出最大面的梳子不等式，并予以了证明。此外，还有其它出最
15、大面的梳子不等式，并予以了证明。此外，还有其它能导出最大面的不等式，如团树不等式等。可见，能导出最大面的不等式，如团树不等式等。可见，Qn的最的最大面极多，曾经计算过由梳子不等式所导出的最大面个数大面极多，曾经计算过由梳子不等式所导出的最大面个数如表如表71所示：所示：n6810203050120c(n)604142088419701.5*10181.5*103110602*10179表表71 第19页，讲稿共105张，创作于星期二20 可以看出，当增大可以看出，当增大时，最大面个数增，最大面个数增长得非常快。得非常快。在在TS多面体理多面体理论的基的基础上，可以考上，可以考虑先解先解TSP的
16、松弛的松弛问题，如果得到的最如果得到的最优解正好是某一条路解正好是某一条路线的关的关联向量，那么就找到向量，那么就找到TSP的最的最优解了；否解了；否则，就，就设法找一些新的不等式作法找一些新的不等式作为额外外约束，再解新的束，再解新的线性性规划，直至找到恰好是关划，直至找到恰好是关联向量的最向量的最优解。解。这种做法的基本思想与解整数种做法的基本思想与解整数规划的割平面法是同一划的割平面法是同一类的，的，Gotschel 等人曾用等人曾用这种方法解种方法解过有有120个城市的个城市的TSP，所增加的，所增加的不等式只有子回路消去不等式与梳子不等式两不等式只有子回路消去不等式与梳子不等式两类，
17、在，在进行了行了13轮计算后，即解了算后，即解了13个个线性性规划后，就找到了划后，就找到了TSP的精确最的精确最优解，解，每一每一轮的当的当时计算算时间仅在在30秒至秒至2分分钟之之间。有趣的是，当。有趣的是，当n=120时，仅梳子不等式就有梳子不等式就有2*10179个，但在个，但在计算算过程中，程中，总共却只共却只（凭（凭经验）添加了）添加了96个子回路消去不等式与梳子不等式。个子回路消去不等式与梳子不等式。第20页，讲稿共105张，创作于星期二21 当然，用当然，用该方法有方法有时会会找不到找不到TSP的最的最优解，解，因因为很可能在很可能在进行了几行了几轮迭代后，却找不到新的不迭代后
18、，却找不到新的不等式。等式。Padborg与与Hong曾曾计算了算了74个个TSP，其中，其中54个得到了最个得到了最优解，其余的解，其余的虽未得到最未得到最优解，却得到解，却得到了很好的下界，如果与近似方法配合，可以估了很好的下界，如果与近似方法配合，可以估计近近似解的精确程度。如，他似解的精确程度。如，他们解解过一个有一个有313个城市的个城市的TSP，获得一个下界得一个下界41236.46，而用近似方法能得到，而用近似方法能得到一条一条长为41349的路的路线，于是可估，于是可估计出所得近似解与出所得近似解与最最优解的解的误差不超差不超过0.26%。第21页，讲稿共105张，创作于星期二
19、227-2 求解算法求解算法一、下界和上界算法一、下界和上界算法1.下界下界（1）下界）下界b1和和b2 针对TSP对应图的的邻接矩接矩阵，将矩，将矩阵中每一行最小的元素相加，中每一行最小的元素相加，就可得到一个就可得到一个简单的下界的下界b1。经进一步改一步改进，可得到更好的下界：考，可得到更好的下界：考虑一个一个TSP的完整解，在每条路径上，每个城市都有两条的完整解，在每条路径上，每个城市都有两条邻接接边，一条一条进，一条出，那么，如果把矩，一条出，那么，如果把矩阵中每一行最小的两个元素相中每一行最小的两个元素相加再除以加再除以2（不失一般性，可假定（不失一般性，可假定图中所有距离中所有距
20、离权重都重都为整数），整数），再再对其其结果向上取整，就可得到一个合理的下界果向上取整，就可得到一个合理的下界b2。显然，然，b2b1，因此，一般不采用，因此，一般不采用b1作作为TSP的下界。的下界。第22页，讲稿共105张，创作于星期二23例例1 已知已知TSP及其距离矩及其距离矩阵如如图71所示，所示，试求其下求其下界界 271563134253984(a)无向图无向图图图71 无无向向图图及及距离矩阵距离矩阵(b)距离矩阵距离矩阵第23页，讲稿共105张，创作于星期二24解：解：将矩将矩阵中每一行最小的元素相加，中每一行最小的元素相加，1+3+1+3+2=10，即得，即得b1=10。将
21、矩。将矩阵中每一行最小的两个元素相中每一行最小的两个元素相加再除以加再除以2，再，再对结果向上取整，即可得果向上取整，即可得b2=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14。第24页，讲稿共105张，创作于星期二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个个结点关点关联的所有的所有边中第中第
22、k(k=1,2,3)长边的另一的另一个个结点的点的编号号(其中一个其中一个结点点编号号为i)；node_ base(i)=dmin_j(i,1)+dmin_j(i,2)：表示与：表示与i点关点关联边中中长度最度最短的两条短的两条边之和；之和；C*(T)：最：最优回路回路长度；度；第25页，讲稿共105张，创作于星期二26 于是，于是，dmin(i,1)代表与第代表与第i个个结点关点关联的所有的所有边中最中最长边的的长度，度，dmin_j(i,1)代表与第代表与第i个个结点关点关联的所有的所有边中次中次长边的另一个的另一个结点点编号号(其中一个其中一个结点点编号号为i)，第，第i结点的点的dmi
23、n(i,k)和和dmin_j(i,k)可由距可由距离矩离矩阵w轻易求得。易求得。通通过对下界下界b2进行改行改进，可以得出一个求，可以得出一个求对称型称型TSP更好的下界更好的下界b3。在求在求b2的的过程中，只有当与每一程中，只有当与每一结点关点关联的的边中中长度最小的两条度最小的两条边都出都出现在最在最优TSP回路中回路中时，等号才成立，下面就来分析如何提高等号才成立，下面就来分析如何提高这个下界。个下界。第26页，讲稿共105张，创作于星期二27 对结点点i而言，而言，设e(i)1与与e(i)2分分别为与与结点点i关关联的的边中中长度最小的两条度最小的两条边，其，其长度分度分别为dmin
24、(i,1)和和dmin(i,2)。在在对称型称型TSP回路中，由于有且回路中，由于有且仅有两条有两条边与与每一每一结点关点关联，因此，并不是与每个，因此，并不是与每个结点关点关联的最的最小两条小两条边都能出都能出现在最在最优TSP回路中，回路中，这意味可以意味可以在在node_ base(i)的基的基础上增加上增加TSP回路的回路的长度，将在度，将在这种情况下增加的种情况下增加的长度度记为Adjust(T)，现在分析如在分析如何何计算算Adjust(T)。第27页，讲稿共105张，创作于星期二28 对结点点i的的e(i)1，边e(i)1的一个的一个结点点为i，另一，另一个个结点点为j=dmin
25、_j(i,1)，若，若e(i)1也是也是结点点j关关联边中最小的两条中最小的两条边之一，即之一，即 i=dmin_j(j,1)或或 i=dmin_j(j,2)，则对边e(i)1来来说就不需要就不需要调整，否整，否则按以下方式按以下方式调整：整：第28页，讲稿共105张，创作于星期二29若若e(i)1不是不是结点点j=dmin_j(i,1)关关联边中最小的两条中最小的两条边之一，之一，则只有以下两种情况：只有以下两种情况：选中中e(i)1到到TSP回路中回路中 此此时对结点点i不需不需调整，整，对结点点j来来说，由于，由于边e(i)1出出现在最在最优回路中，而回路中，而e(i)1不是不是结点点j
26、关关联边中中最小的两条最小的两条边之一，因此会造成之一，因此会造成结点点j关关联边中最小中最小的两条的两条边中至少有一条不会出中至少有一条不会出现在最在最优回路中，从回路中，从而而对结点点j而言，在而言，在node_base(i)的基的基础上至少会增上至少会增加的加的长度度为 dmin(i,1)dmin(j,2)。第29页，讲稿共105张，创作于星期二30 不不选中中e(i)1到到TSP回路中回路中 此此时对结点点i需要需要调整，由于整，由于边e(i)1不在回路不在回路中，故其在中，故其在node_base(i)的基的基础上至少会增加的上至少会增加的长度度为 dmin(i,3)dmin(i,1
27、)。此此时对结点点j来来说，由于与它关，由于与它关联的最短两条的最短两条边仍然可能在回路中，因此不仍然可能在回路中，因此不须调整。整。第30页，讲稿共105张，创作于星期二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)，若，若
28、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张，创作于星期二32 将每个将每个结点都按上述方法点都按上述方法进行一次行一次调整，其整，其调整累加和就是整累加和就是Adjust(T)，可写成如下公式：，可写成如下公式：第32页，讲稿共105张，创作于星期二3
29、3 将将问题T中所有中所有结点的基本点的基本长度度node_base(T)累累加之和的一半称加之和的一半称为T的基本的基本长度，并用度，并用base(T)来表来表示，可写成如下公式：示，可写成如下公式：第33页，讲稿共105张，创作于星期二34 于是，有于是，有C*(T)base(T)+Adjust(T)=b3，即，即 b3=b2+Adjust(T)。由以上分析，不由以上分析，不难得出求得出求对称称TSP下界下界b3的算法：的算法：第34页，讲稿共105张，创作于星期二35Step 1.计算算base(T)：get_base()i:Long For i=1 To n base=base+dmi
30、n(i,1)+dmin(i,2)第35页，讲稿共105张，创作于星期二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)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),d
31、min(i,2)-dmin(ii2,2)第36页，讲稿共105张，创作于星期二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；
32、271563134253984(a)无向图无向图图图71 无向图无向图第37页，讲稿共105张，创作于星期二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)无向图无向图图图71 无向图无向图第38页，讲稿共105张，创作于星期二39add_node(1,1)=0;add_node(1,2)=0;
33、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_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张，创作于星期二402.上界上界 事事实上，上，TSP的任何可行解都是上界，的任何可行解都是上界，这里，里，给出求出求TSP上界上界U1
34、的的贪心方法思想。心方法思想。算法步算法步骤如下：如下：第40页，讲稿共105张，创作于星期二41Step 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_ed
35、ge+(k,h)；k=h。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=0第48页，讲稿共105张，创作于星期二49(1)用用贪心算法求得心算法求得上界上界U1=16；(2)假定假定边(1,3)不在不在TSP回路中回路中，即，即e13=0，此，此时，b2=(5+3)+(3+6)+(4+2)+(3+4)+(2+3)/2=17.5
36、，由，由于于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张，创作于星期二50(4)在在e12=e13=1的情况下，由于的情况下，由于顶点点1已有两条关已有两条关联边在最在最优回路中，因此在回路中，因此在图71中中删去去边(1,4)和和(1,5)，由于，由于边(2,3)与与边(1,2)
37、、(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；第50页，讲稿共105张，创作于星期二51(6)在在e12=e13=1，e14=e15=e23=e25=0的情况下，由的情况下，由于与于与顶点点2关关联的的边有且只有有且只有2条在回路中，因此有条在
38、回路中，因此有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张，创作于星期二522.基于降基于降阶的分支定界法的分支定界法 对于于有向有向TSP的距离距的距离距阵，可通，可通过不同情况下不同情况下上下界的上下界的对比来确定某些比来确定某些边(i,j)一定在或不在回路一定在或不在回路中。如果能确定中。如果能确定(i,j)一定在回路中，由于每个一定在回路中，由于每个顶点点分分别有且只有一条入有且只有一条入
39、边和出和出边，从而可确定，从而可确定顶点点i的的其它出其它出边一定不在回路中，也可以确定一定不在回路中，也可以确定顶点点j的其它的其它出出边一定不在回路中，因此可将一定不在回路中，因此可将这些些边从距离距从距离距阵中去掉，从而达到中去掉，从而达到降低矩降低矩阵阶数数的目的。的目的。这里，以一个具体的例子来予以里，以一个具体的例子来予以说明。明。第52页，讲稿共105张，创作于星期二53例例2 已知有向已知有向TSP的距离矩的距离矩阵如下：如下：第53页，讲稿共105张，创作于星期二54解解:由于每个由于每个顶点都必点都必须有一条入有一条入边和出和出边，因此，因此将将顶点点i的所有出的所有出边的
40、的权值减去所有出减去所有出边权值的最小的最小值min_out(i)，不会影响最，不会影响最优解，解，仅最最优值在原来的基在原来的基础上减少了上减少了min_out(i)。于是，可以将距离矩于是，可以将距离矩阵的每一行和每一列都减的每一行和每一列都减去去该行或行或该列的最小列的最小值，直至每行每列都含有，直至每行每列都含有0为止。止。将上述矩将上述矩阵的每行分的每行分别减去减去该行的最小行的最小值3,4,16,7,25,3，就得到如下，就得到如下缩减之后的矩减之后的矩阵：第54页，讲稿共105张，创作于星期二55 该缩减矩减矩阵所所对应TSP的最的最优解与原来的相同，但最解与原来的相同，但最优值
41、比原比原来减少了来减少了3+4+16+7+25+3=58。由于矩由于矩阵中第中第3、4列中不含列中不含0元素，因此可元素，因此可继续缩减成：减成：第55页，讲稿共105张，创作于星期二56该缩减矩减矩阵所所对应TSP的最的最优解与原来的相同，但最解与原来的相同，但最优值比原来减少了比原来减少了3+4+16+7+25+3=58。由于矩由于矩阵中第中第3、4列中不含列中不含0元素，因此可元素，因此可继续缩减成：减成：第56页，讲稿共105张，创作于星期二57 其最其最优值比原来减少比原来减少58+15+8=81，这个个81可可作作为该TSP初始的下界初始的下界值b。第57页，讲稿共105张，创作于
42、星期二58按按e63=1和和e63=0将解分成两种情况：将解分成两种情况：(1)e63=0 此此时，边(6,3)不能出不能出现在回路中，其在回路中，其权值在在这种情况下种情况下为，因此，距离矩，因此，距离矩阵可修改可修改为：第58页，讲稿共105张，创作于星期二59 由于第由于第3列没有列没有0元素，故用第元素，故用第3列各元素减去列各元素减去其最小元素其最小元素48，得如下，得如下缩减矩减矩阵：此此时的下界的下界 b=81+48=129。第59页，讲稿共105张，创作于星期二60(2)e63=1 此此时，边(6,3)已出已出现在回路中，从在回路中，从顶点点6出出发的其它的其它边都不可能在回路
43、中，因此可都不可能在回路中，因此可删去第去第6行行；同理，同理，进入到入到顶点点3的其它的其它边都不可能在回路中，都不可能在回路中，因此又可因此又可删去第去第3列列。此。此时，边(3,6)不可能出不可能出现在在回路中，令回路中，令边(3,6)的的权值为，矩，矩阵化化为：第60页，讲稿共105张，创作于星期二61继续依次计算，并实施分支继续依次计算，并实施分支和定界，具体过程如图和定界，具体过程如图73所示：所示：图图73 降阶分支定界过程降阶分支定界过程b=81e63=0e63=1b=129e46=0e46=1b=113e21=0e21=1b=81b=81b=84b=101e14=1e14=0
44、b=84b=112得可行回路(1,4,6,3,5,2,1),回路总长104，由此可将下界b大于104的分支剪去。第61页，讲稿共105张，创作于星期二62e63=1，e46=0下的下的缩减矩减矩阵：第62页，讲稿共105张，创作于星期二63e63=e46=1下的下的缩减矩减矩阵：第63页，讲稿共105张，创作于星期二64e63=e46=1，e21=0下的下的缩减矩减矩阵：第64页，讲稿共105张，创作于星期二65e63=e46=e21=1下的下的缩减矩减矩阵：第65页，讲稿共105张，创作于星期二66e63=e46=e21=1，e14=0下的下的缩减矩减矩阵：第66页，讲稿共105张，创作于星
45、期二67e63=e46=e21=e14=1下的下的缩减矩减矩阵：第67页，讲稿共105张，创作于星期二68e63=e46=1，e21=e51=0下的下的缩减矩减矩阵：第68页，讲稿共105张，创作于星期二69e63=e46=e51=1，e21=0下的下的缩减矩减矩阵：第69页，讲稿共105张，创作于星期二70e63=e46=e51=1，e21=e14=0下的下的缩减矩减矩阵：第70页，讲稿共105张，创作于星期二71e63=e46=e51=e14=1，e21=0下的下的缩减矩减矩阵：第71页，讲稿共105张，创作于星期二72 最后可得到两个最最后可得到两个最优TSP回路：回路：(1,4,6,3
46、,2,5,1)和和(1,4,6,3,5,2,1)，最，最优回路回路长度度为104。若将无向若将无向图中的每条中的每条边看成有向看成有向图中方向相反中方向相反的两条的两条边，则无向无向图也可看成是有向也可看成是有向图，因此，基，因此，基于降于降阶的分支定界法也可用来求解无向的分支定界法也可用来求解无向TSP问题。第72页，讲稿共105张，创作于星期二73三、动态规划法定理定理1 TSP满足足最最优性原理性原理。最最最最优优化化化化原原原原理理理理可可以以表表述述为：“一一个个过程程的的最最优策策略略具具有有这样的的性性质,即即无无论初初始始状状态和和初初始始决决策策如如何何,对于于先先前前决决策
47、策所所形形成成的的状状态而而言言,其其以以后后的的所所有有决决策策必必构构成成最最优策策略略，”第73页，讲稿共105张，创作于星期二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将是一条从
48、将是一条从s出出发的路径的路径长度最短的度最短的简单回路且比回路且比s,s1,s2,sp,s要短，从而要短，从而导致矛盾。所以，致矛盾。所以，TSP满足最足最优性原理。性原理。第74页，讲稿共105张，创作于星期二75 设TSP顶点点编号分号分别为0，1，2，n，假，假设从从顶点点0出出发，令，令d(i,V)表示从表示从顶点点 i 出出发经过V 中各中各顶点一次且点一次且仅一次，最后回到出一次，最后回到出发点点0的最短路的最短路径径长度，中度，中间计算算过程中的程中的d(k,Vk)也表示从也表示从顶点点 k 出出发经过Vk 中各中各顶点一次且点一次且仅一次，最一次，最后回到出后回到出发点点0（
49、注意不是（注意不是k）的最短路径）的最短路径长度。开度。开始始时，V=Vi，cij为顶点点 i 至至顶点点 j 的距离，于的距离，于是，是，TSP的的动态规划划递推函数可写成：推函数可写成：第75页，讲稿共105张，创作于星期二76d(i,V)=min cik+d(k,Vk)(kV)d(k,)=ck 0 (k 0)例例3 求解有向求解有向TSP：第76页，讲稿共105张，创作于星期二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)
50、这是最后一个是最后一个阶段的决策，而段的决策，而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张，创作于星期二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,)；而下式可以直接而下式可以直接获得（