动机
一条配送路线必须访问每一个地点,并回到起点。寻找代价最小的路线可能十分困难,但近似算法能够给出一条路线,并证明其代价相对于未知最优值的比值。对于度量距离,最小生成树给出一个有用的下界,而沿该树绕行一周的途径可以给出代价至多为最优值两倍的巡回。
三角不等式使我们可以删去重复访问而不增加代价。我们还将说明,对树中奇度顶点做匹配,可以把论证改进为因子 ;这里假定存在精确的最小权完美匹配算法,并把它视为一个独立的计算要素。
定义
定义 4.4.1
(度量实例)
设 是含 个顶点的有限集。对每一对有序顶点 ,令 ,且 ,,。不同的顶点之间的距离可以为零。由此得到的完全无向加权图在本章所需的意义下是度量的。
定义 4.4.2
(巡回与最优值)
巡回(tour)是一条闭途径,它恰好访问每个顶点一次,然后回到起点。当 时,巡回把唯一的一条无向边走两次。记 为最小的巡回代价。途径(walk)可以重复顶点或边;每一次经过都贡献相应的距离。若 ,则零代价的原地巡回是最优的,可以单独返回。
定义 4.4.3
(生成树、多重图与欧拉途径)
最小生成树(MST)是权最小的、连通且无圈的生成子图。多重图可以含有同一条边的平行副本;顶点的度数计入每一个副本。连通且各顶点度数均为偶数的多重图的欧拉(Euler)回路,是恰好经过每个边副本一次并回到起点的闭途径。标准的欧拉回路构造沿着未使用的边前进并拼接闭途径;其运行时间与边副本的个数成线性关系。
定理
定理 4.4.4
(双倍树近似)
将最小生成树的每条边加倍,对其欧拉回路按首次访问进行捷径处理,得到的巡回代价至多为 。
定理 4.4.5
(奇度顶点匹配的改进)
设 为某棵 MST 的奇度顶点集。若把 上的一个精确最小权完美匹配加入该树,则所得多重图的欧拉回路可以经捷径处理为代价至多为 的巡回。
上的完美匹配把其顶点划分为互不相交的数对,每一对使用一条边;当 时取空匹配。第二个定理假定这样的最小权匹配可以被计算出来。一般图上加权完美匹配的多项式时间算法是另一个独立的结果,本章不予证明。
证明
生成树下界
引理 4.4.6
(最小生成树的下界)
给 上的完全图赋予非负边权,并设 为最小生成树。则 。
证明
(删去最优巡回的一条边)
取一条最优巡回。当 时,删去其任意一条边,其余的边构成一条生成路径,因而是一棵生成树;由于边权非负,它的代价不超过该巡回的代价。当 时,删去两次经过中的一次,剩下唯一的生成边,其代价同样不超过巡回代价。MST 不比这棵树更贵,故
这一论证不需要三角不等式。它利用完全性来保证巡回存在,并利用权的非负性来说明删去一条边不会增加代价。
加倍树并对途径做捷径处理
证明
(加倍树,再取捷径)
将 MST 的每条边加倍。所得连通多重图的每个顶点度数均为偶数,因此存在欧拉回路,其代价恰为 。它可能多次访问同一顶点,所以还不是旅行商的巡回。
从选定的起点出发,按欧拉途径首次访问各顶点的顺序列出这些顶点。把相邻的两个列出顶点直接相连,再把最后一个顶点连回起点。每个顶点在返回之前恰好出现一次。每条直接边都替换了原途径中连续的一段。反复应用三角不等式可知,该直接边的代价不超过被替换的那一段。这些片段(包括最后返回起点的片段)构成原途径的一个划分,因此捷径巡回的代价至多为 。
对于两个顶点,捷径处理后剩下这两个顶点之间那条边的两次相反方向的经过,恰好是所需的闭巡回。零权边不会造成问题;所有不等式都是非严格的。若 ,证明给出代价为零的巡回。乘积形式的陈述仍然作为不等式有意义,而无需除以零。
证明透视
上界与下界在树上相遇
因子二来自三个互不相同的步骤,每一步用到不同的假设。删去最优巡回的一条边只用到边权非负,给出 。把树加倍完全不用距离:它只是令每个度数变成偶数,因此存在代价恰为 的欧拉途径。捷径是唯一用到三角不等式的步骤,被它换成直接边的每一段途径各用一次。把三者连起来,捷径巡回的代价至多为 ,而 。
匹配奇度顶点
证明
(奇偶性、交替匹配与捷径)
有限无向图中奇度顶点的个数为偶数,因为度数之和等于边数的两倍。设 为 的奇度顶点集, 为 上的一个最小权完美匹配。把 加到 上,恰好改变 中各顶点的奇偶性,使每个顶点的度数变为偶数。结果仍然连通,因此存在代价为 的欧拉回路。
我们证明 。沿着一条最优巡回走一遍,只保留 中的顶点,并在相邻的保留顶点之间做捷径处理。由三角不等式,所得 上的闭途径不比原巡回更贵。当 时,它的圈上各边交替地分成两个完美匹配。这两个匹配的代价之和就是该途径的代价,所以较便宜的那个匹配的代价至多为其一半。最小匹配 不比该匹配更贵。
当 时,捷径得到的闭途径沿两个方向各经过这两个奇度顶点之间的那条边一次。把这两次经过视为该边的两个副本,便得到两个单边的完美匹配,每个的代价都等于该边的代价;同样得到代价至多为一半的结论。当 时, 为空,代价为零。因此在所有情形下 。
欧拉途径的代价至多为 。按首次访问对其做捷径处理不会增加代价,因此最终的巡回满足第二个定理。即使存在多棵 MST、多个最小匹配或多条最优巡回并列的情形,这个证明依然给出代价保证。
证明透视
配对界从何而来
度数的握手奇偶性只用了一次: 是偶数,所以完美匹配存在,加入它之后每个度数都变成偶数。三角不等式用了两次,一次是把最优巡回缩短到只经过 ,另一次是对最后的欧拉途径作捷径处理。关键一步是:经过偶数个顶点的闭途径可以分成两个匹配,所以其中较便宜的一个成本至多是该途径的一半。 的最小性使它可以与这个较便宜的匹配相比较。
算法代价与适用范围
完全图有 条边。MST 可以在多项式时间内求得;例如,Prim 算法的合适的数组实现在稠密图上需要 次比较。将其 条边加倍、求欧拉回路并做捷径处理,在直接的表示下需要 或更少的时间。因此,因子二的算法对于显式距离矩阵的输入规模是多项式的。
对于因子 的算法,还需加上在至多 个奇度顶点上运行精确最小权完美匹配程序的代价。已知在适当的精确算术假设下,这类程序对一般加权图是多项式时间的,但本章不证明该算法及其比特复杂度。近似性的证明以获得最小匹配为条件,而不是针对一个仅仅看起来很短的贪心配对。
若距离为有理数或整数,算术运算的次数并不自动等于比特时间界。实现时必须准确地表示和并准确地比较权。该定理针对满足所有度量假设的精确距离;浮点舍入可能需要另行分析。
例题详解
例题 4.4.7
(三个等距顶点)
设每一对不同顶点的距离均为一。MST 有两条边,代价为二。将其加倍得到代价为四的欧拉途径。对重复顶点做捷径处理,得到由三条边组成、代价为三的巡回,它是最优的。因子二的保证允许代价高达六;这只是上界,并不预示算法总是付出最优值的两倍。
概念视角算法
加倍树巡回就是前序遍历
取定根,沿深度优先的途径走:每条边向下走一次、向上走一次;这是加倍树的一条欧拉巡回。按首次到访的次序排列顶点,恰好就是有根树的前序。所以这个算法就是:求最小生成树,按前序列出它的顶点,然后回到根。
例题 4.4.8
(四个顶点的直线度量)
把顶点放在数轴上的坐标 处,距离等于差的绝对值。依次经过相邻坐标的路径是代价为三的 MST。巡回 的代价为 ;双倍树途径可以经捷径处理得到这条巡回。该路径的奇度顶点集由它的两个端点组成,其匹配的代价为三,所以匹配构造同样得到代价为六的途径。
例题 4.4.9
(两个顶点的边界情形)
对于距离为 的两个顶点,MST 的代价为 ,所需的闭巡回代价为 。树的两个顶点度数都是奇数,它们的完美匹配就是那条代价为 的边。把它作为第二个边副本加入,得到代价为 的欧拉回路,恰好是最优的。
例题 4.4.10
(捷径处理需要三角不等式)
设三条边的代价为 ,,。加倍的路径 的代价为四。捷径处理为 后代价为十二,因此捷径反而增加了代价。这些数值违反三角不等式,因为 ;度量近似的证明不适用。
反例模式
途径并不自动是巡回
断言:加倍 MST 的欧拉途径本身已经是旅行商巡回。取四个顶点 ,任意两点距离都是 ;这是一个度量。以 为中心、 为叶子的星形是代价为 的 MST。把它加倍得到欧拉途径 ,代价为 ,它四次经过 ,所以不是巡回。按首次访问做捷径处理,得到 ,代价为 。正确的说法是:途径要经过捷径处理才成为巡回,而三角不等式(这里是每段被替换路程的 )保证捷径巡回的代价不超过原途径。
常见错误
常见错误
(生成树不是巡回)
MST 是最优巡回的下界,但它本身不是巡回:它的叶子度数为奇数,而树一般不能提供一条恰好访问每个顶点一次的闭路线。加倍产生闭途径,捷径处理产生所需的巡回。每一次变换都有各自的证明义务。
常见错误
(贪心配对不是最小匹配)
奇度顶点的匹配必须把所有奇度顶点配对。仅仅贪心地把相邻的顶点配对,可能得到比最小者更贵的完美匹配,所以证明 不能用于任意的配对。若匹配本身只用近似算法,则需要相应调整分析。
常见错误
(最优值是基准,不是输入)
最后,该保证比较的是算法在同一实例上的结果与最优值。算法运行时不需要知道 。最优巡回只出现在证明中,作为界定树和匹配代价的基准。
总结
删去巡回的一条边得到 MST 下界。将树加倍使其度数为偶数,在度量中对欧拉途径做捷径处理,得到代价至多为最优值两倍的巡回。对树的奇度顶点做匹配,其代价至多为最优巡回的一半,从而把界改进为 ,但以能够计算最小完美匹配为条件。三角不等式、奇偶性与非负代价各自发挥不同的作用。
练习
快速检查
(解释为什么把树的每条边加倍后,每个顶点的度数都变为偶数。)
数一数一个顶点处的边副本。
解答 · 答案
加倍之后,每条关联边贡献两个边副本,所以每个原来的度数都乘以二,变为偶数。图仍然连通。
快速检查
(对于距离为 的两顶点度量,计算 MST 的代价、最优巡回的代价,以及加入匹配后的欧拉途径的代价。)
参考两个顶点的边界例子。
解答 · 答案
MST 只有一条代价为七的边。闭巡回把该边走两次,代价为十四。两个顶点在树中的度数都是奇数;匹配加入一个代价为七的边副本,得到代价为十四的欧拉途径。
快速检查
(为什么巡回的代价是 MST 代价的上界?请明确说明权非负所起的作用。)
要删去哪一条边?
解答 · 答案
从至少含三个顶点的巡回中删去一条边,剩下一条生成路径,因而是一棵生成树。因为被删去的边权非负,剩下的树的代价至多等于巡回的代价。MST 的代价不超过该树的代价。对于两个顶点,则删去两次经过中的一次。
快速检查
(设 含有四个顶点,它们沿着一条经捷径处理的最优巡回按圈的顺序排列,各边代价为 。写出两个交替匹配,并界定最小匹配的代价。)
把圈上的边交替分成两组。
解答 · 答案
两个交替边集的代价分别为 与 。二者都是这四个顶点上的完美匹配,所以最小匹配的代价至多为 ,特别地,至多为捷径巡回代价 的一半,即 。