数学建模经典问题——旅行商问题.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 记为赋权图G V E V为顶点集 E为边集 各顶点间的距离dij已知 设 则经典的TSP可写为如下的数学规划模型 6 模型中 为集合中所含图的顶点数 约束 7 1 和 7 2 意味着对每个点而言 仅有一条边进和一条边出 约束 7 3 则保证了没有任何子回路解的产生 于是 满足约束 7 1 7 2 和 7 3 的解构成了一条Hamilton回路 7 当dij dji i j V 时 问题被称为对称型TSP 否则称为非对称型TSP 若对所有1 i j k n 有不等式dij djk dik成立 则问题被称为是满足三角形不等式的 简称为 TSP 8 2 扩展TSP 1 瓶颈TSP瓶颈问题是最早从TSP延伸出来的一种扩展型TSP 其含义与经典的TSP类似 仅目标不同 要求巡回路线中经过的最长距离最短 即最小化瓶颈距离 该情形体现了那些并不追求总巡回路线最短 而只希望在巡回路线中每次从一个地点至另一个地点的单次行程尽可能短的实际应用问题的特征 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 v0 v1 vn 1 v0为名推销员出发点 记V v01 v02 v0m v0 v1 vn 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 考虑个顶点的完全图Kn 则解TSP就相当于在中求一条总长度最短的Hamilton回路 现在 对每条边ej 定义一个变量xj与之对应 这样 TSP的一条路线T 即Kn的一条Hamilton回路 就可对应一个向量X x1 x2 xm 其中 17 称X为路线T的关联向量 其m n n 2 2个分量中 恰好有个为1 其余的都为0 图有许多Hamilton回路 设为T1 T2 Ts 对应的关联向量记为X1 X2 Xs 在m维空间Rm中 考虑这些向量生成的凸包 convexhull Qn 18 Qn是Rm中的一个凸多面体 称做TS多面体 显然 Qn是有界的 其极点正好是Kn的Hamilton回路关联向量 研究Qn的面非常重要的 因为根据线性不等式及凸多面体的理论 Qn一定是某一个有限线性不等式组的解集合 或者说 Qn一定是有限多个半空间的交 因此 如果能找出定义Qn的线性不等式组来 就可将TSP作为一个线性规划来解 19 TS多面体研究中的一个重要问题就是寻找能导出Qn最大面的不等式 Grotschel等人发现了一类很重要的能导出最大面的梳子不等式 并予以了证明 此外 还有其它能导出最大面的不等式 如团树不等式等 可见 Qn的最大面极多 曾经计算过由梳子不等式所导出的最大面个数如表7 1所示 表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 下界b1和b2针对TSP对应图的邻接矩阵 将矩阵中每一行最小的元素相加 就可得到一个简单的下界b1 经进一步改进 可得到更好的下界 考虑一个TSP的完整解 在每条路径上 每个城市都有两条邻接边 一条进 一条出 那么 如果把矩阵中每一行最小的两个元素相加再除以2 不失一般性 可假定图中所有距离权重都为整数 再对其结果向上取整 就可得到一个合理的下界b2 显然 b2 b1 因此 一般不采用b1作为TSP的下界 23 例1已知TSP及其距离矩阵如图7 1所示 试求其下界 24 解 将矩阵中每一行最小的元素相加 1 3 1 3 2 10 即得b1 10 将矩阵中每一行最小的两个元素相加再除以2 再对结果向上取整 即可得b2 1 3 3 6 1 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 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轻易求得 通过对下界b2进行改进 可以得出一个求对称型TSP更好的下界b3 在求b2的过程中 只有当与每一结点关联的边中长度最小的两条边都出现在最优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 对于 和 必须有且仅有一种情况出现 现取两种情况中增加长度小的值 因而回路的长路一定会在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 32 将每个结点都按上述方法进行一次调整 其调整累加和就是Adjust T 可写成如下公式 33 将问题T中所有结点的基本长度node base T 累加之和的一半称为T的基本长度 并用base T 来表示 可写成如下公式 34 于是 有C T base T Adjust T b3 即b3 b2 Adjust T 由以上分析 不难得出求对称TSP下界b3的算法 35 Step1 计算base T get base i LongFori 1Tonbase base dmin i 1 dmin i 2 36 Step2 计算Adjust T get adjust i ii1 ii2 LongFori 1Ton ii1 dmin j i 1 ii2 dmin j i 2 Ifidmin j ii1 1 Andidmin j ii1 2 adjust adjust min dmin i 3 dmin i 1 dmin i 1 dmin ii1 2 Ifidmin j ii2 1 Andidmin 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 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 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 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 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 40 2 上界事实上 TSP的任何可行解都是上界 这里 给出求TSP上界U1的贪心方法思想 算法步骤如下 41 Step1 图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中 42 求解结束后 TSP edge中的边都在TSP回路中 对例1 可用上述算法求得其路径为 1 3 5 4 2 1 路径长度1 2 3 7 3 16 这是TSP的一个上界U1 综合上下界 就可得到例1目标函数的界为 15 16 43 二 分支定界法 二 分支定界法分支定界法是一种在表示问题解空间的树上进行系统搜索的精确算法 这里 介绍两种求解TSP的分支定界方法 44 基于上下界的分支定界法为用分支定界法求解TSP 需要计算某些边在TSP回路中和某些边不在TSP回路中等情况下的下界 若采用下界b2计算 由于每个顶点最多只有两个关联边在TSP回路中 已在TSP回路中的边则限制该边的其它邻接边加入 因此 针对每个顶点 分4种情况来计算 45 1 若某顶点没有关联边在TSP回路中 则该顶点的计算方法与计算b2的方法相同 即把该顶点关联的最短两边长度之和的一半加入到下界中 2 若某顶点关联的边已有两条边e1和e2在TSP回路中 则不需要再加入与该顶点关联最小两条边的长度 即此时把e1和e2长度之和的一半加入到下界中 3 若某顶点关联的边已有一条边e1在TSP回路中 则只需要再加入与该顶点关联的最小边长度 即把e1和该顶点关联的最短一条边的长度之和的一半加入到下界中 4 若某顶点关联边集的子集E1不能出现在TSP回路中 则将E1从图中删除再计算b2即可 如某顶点已有两关联边在回路中 则可将其它关联边删除 同样 可以将会与已加入到回路中的边形成子圈的边删除 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 47 为描述方便 用eij 1表示边 i j 在TSP回路中 eij 0表示边 i j 不在TSP回路中 下面给出用分支定界法求解例1的过程 如图7 2所示 48 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 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 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 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 按e63 1和e63 0将解分成两种情况 1 e63 0此时 边 6 3 不能出现在回路中 其权值在这种情况下为 因此 距离矩阵可修改为 59 由于第3列没有0元素 故用第3列各元素减去其最小元素48 得如下缩减矩阵 此时的下界b 81 48 129 60 2 e63 1此时 边 6 3 已出现在回路中 从顶点6出发的其它边都不可能在回路中 因此可删去第6行 同理 进入到顶点3的其它边都不可能在回路中 因此又可删去第3列 此时 边 3 6 不可能出现在回路中 令边 3 6 的权值为 矩阵化为 61 继续依次计算 并实施分支和定界 具体过程如图7 3所示 图7 3降阶分支定界过程 62 e63 1 e46 0下的缩减矩阵 63 e63 e46 1下的缩减矩阵 64 e63 e46 1 e21 0下的缩减矩阵 65 e63 e46 e21 1下的缩减矩阵 66 e63 e46 e21 1 e14 0下的缩减矩阵 67 e63 e46 e21 e14 1下的缩减矩阵 68 e63 e46 1 e21 e51 0下的缩减矩阵 69 e63 e46 e51 1 e21 0下的缩减矩阵 70 e63 e46 e51 1 e21 e14 0下的缩减矩阵 71 e63 e46 e51 e14 1 e21 0下的缩减矩阵 72 最后可得到两个最优TSP回路 1 4 6 3 2 5 1 和 1 4 6 3 5 2 1 最优回路长度为104 若将无向图中的每条边看成有向图中方向相反的两条边 则无向图也可看成是有向图 因此 基于降阶的分支定界法也可用来求解无向TSP问题 73 三 动态规划法 定理1TSP满足最优性原理 最优化原理可以表述为 一个过程的最优策略具有这样的性质 即无论初始状态和初始决策如何 对于先前决策所形成的状态而言 其以后的所有决策必构成最优策略 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满足最优性原理 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的动态规划递推函数可写成 76 d i V min cik d k V k k V d k ck0 k 0 例3求解有向TSP 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 这一阶段的决策又依赖于下述计算结果 78 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 1 0 d 2 c20 6 2 0 d 3 c30 3 3 0 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 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 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 82 四 近似算法 由于精确式算法所能求解的问题规模非常有限 实际中真正使用的往往都是多项式阶数的近似算法或启发式算法 算法的好坏用C C 来衡量 其中 C为近似算法所得的总行程 C 为最优总行程 为最 坏 情况下近似与最优总行程之比所不超过的上界值 这里 列举几个常见的TSP快速近似算法 83 旅行售货员问题的一些特殊性质 比如 费用函数w往往具有三角不等式性质 即对任意的3个顶点u v w V 有 w u w w u v w v w 当图G中的顶点就是平面上的点 任意2顶点间的费用就是这2点间的欧氏距离时 费用函数w就具有三角不等式性质 对于给定的无向图G 可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法 84 当费用函数满足三角不等式时 算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍 voidapproxTSP Graphg 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回路TSPOPT TSPOPT中共有n条边 现去掉TOPT中最长的一条边 得路径POPT POPT中共有n 1条边 其总权值之和WTSP大于等于最小生成树的总权值之和WT 即WTSP WT 下面只需证明该算法求得的TSP回路总长度之和WA小于等于2WT即可 把最小生成树中的边重复一次 再根据三角不等式就可得出结论 多次利用三角不等式 为什么 当费用函数满足三角不等式时 算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍 87 把最小生成树中的边重复一次 再根据三角不等式就可得出结论 多次利用三角不等式 d 中蓝色的边为原来不在最小生成树中的边 最小生成树中的边重复一次及不在 d 中 但在 b 中的边反复利用三角不等式就可得出结论 88 1 插入算法插入型算法可按插入规则的不同而分为若干类 其一般思想为 Step1 通过某种插入方式选择插入边 i j 和插入点k 将k插入i和j之间 形成 i k j Step2 依次进行 直至形成回路解 适用范围 对称型 TSP 具体实施中 可将出发点取遍V中各点而得到多个解 并从中选择最好的一个 但此时的时间复杂度增加了n倍 主要的插入型算法有 89 1 最近插入法最坏情况 2 时间复杂度 O n2 2 最小插入法最坏情况 2 时间复杂度 O n2lgn 3 任意插入法最坏情况 21gn 0 16 时间复杂度 O n2 4 最远插入法最坏情况 21gn 0 16 时间复杂度 O n2 5 凸核插入法最坏情况 未知 时间复杂度 O n2lgn 90 插入法 InsertionMethod 1任选一节点为起点a 2寻找距离节点a最近的节点b作为下一个造访的节点 形成a b a的子回路 3寻找距离子回路最近的节点k作为下一个插入点 4寻找插入成本最小的位置 i j 将k插入i j之间 形成新的子回路 插入成本 Cik Ckj Cij5重复步骤3 4 直到所有节点均已插入回路之中 即形成一个TSP的可行解 91 插入法 1 4 2 3 5 7 4 3 8 7 5 5 3 4 8 1 4 1 4 1 3 3 3 2 5 1任选一节点为起点a 2寻找距离节点a最近的节点b作为下一个造访的节点 形成a b a的子回路 3寻找距离子回路最近的节点k作为下一个插入点 4寻找插入成本最小的位置 i j 将k插入i j之间 形成新的子回路 插入成本 Cik Ckj Cij5重复步骤3 4 直到所有节点均已插入回路之中 即形成一个TSP的可行解 92 2 最近邻算法Step1 任取一出发点 Step2 依次取最近的点加入当前解中 直至形成回路解 适用范围 对称型 TSP 具体实施中 可将出发点取遍V中各点而得到多个解 从中选择最好的一个 但此时的时间复杂度增加了n倍 最坏情况 1gn 1 2 时间复杂度 O n2 93 最近邻点法 Nearest neighbor