优化2: 一般斯坦纳树问题的近似
1. 近似度量斯坦纳树问题在 优化1 中我们定义了度量斯坦纳树问题:
输入是一个点集 https://www.zhihu.com/equation?tex=X+%3D+R+%5Ccup+S, 其中是必要点集,是可选点集, 同时我们还有一个对称距离函数使得每条边的距离为非零值 https://www.zhihu.com/equation?tex=d%28x%2C+y%29+%3D+d%28y%2C+x%29+%5Cgeq+0. 最后, 还有一个额外的约束条件, 即需要满足三角不等式:
https://www.zhihu.com/equation?tex=d%28x%2C+z%29+%5Cleq+d%28x%2C+y%29+%2B+d%28y%2C+z%29+%5Cquad+%5Cforall+x%2C+y%2C+z+%5Cin+X
在这个例子中,被称为度量. 该问题的目标是找到树 , 其中是包含所有必要点和可能包含一些可选点的任意点集 , 使得代价 https://www.zhihu.com/equation?tex=cost_d+%28%5Cmathcal+T%29+%3A%3D+%5Csum_%7B%28u%2C+v%29+%5Cin+E%7D+d%28u%2C+v%29 最小. 优化1的最后 我们讨论了一种完全无视中可选点的算法, 该算法找到具有 必要点集和由定义的边权重 的加权图的最小生成树 (spanning tree).
现在让我们证明这一算法是2-approximate, 也就是, 它可以找到最多2倍最优解代价的解.
引理 1 令为度量斯坦纳树问题的一个实例, 并且是具有性质的斯坦纳树. 则存在另一树 https://www.zhihu.com/equation?tex=%5Cmathcal+T%27+%3D+%28R%2C+E%27%29 覆盖了中的顶点, 并且只有中的顶点使得 https://www.zhihu.com/equation?tex=cost_d%28%5Cmathcal+T%27%29+%5Cleq+2+%5Ccdot+cost_d%28%5Cmathcal+T%29.
特别是将该引理应用于最优斯坦纳树, 我们可以发现存在的生成树, 其成本至多是最优斯坦纳树成本的2倍.
证明 1 考虑使用深度优先搜索 (Depth-First-Search, DFS) 来遍历树 , 也就是, 一个序列:
https://www.zhihu.com/equation?tex=%5CBig%5Bx_0%2C+x_1%2C+x_2%2C+...%2C+x_m%5CBig%5D+%5Cquad+x_m+%3D+x_0
按照在DFS期间考虑它们的顺序, 列出的顶点, 包括每次递归调用结束时我们返回的一个顶点. 该序列描述了元素的循环, 其总长度是 https://www.zhihu.com/equation?tex=%5Csum_%7Bi%3D0%7D%5Em+d%28x_i%2C+x_%7Bi%2B1%7D%29 恰好是 , 因为这一循环恰好使用这个树的每条边2次.
现在令为从获取的序列 (通过移除中顶点和保留只在中第一次出现的顶点). 那么包含中所有顶点的路径, 当然此序列中也没有其他顶点, 且它的代价 https://www.zhihu.com/equation?tex=%5Csum_%7Bi%3D0%7D%5Ek+d%28+y_i%2C+y_%7Bi%2B1%7D+%29+ 最多 是循环的代价 (这儿我们需要用到三角不等式), 那么我们可以得到的代价最多为 . 注意是个路径, 也是个树, 因此我们可以将视作树 https://www.zhihu.com/equation?tex=%28R%2C+E%27%29, 其中 https://www.zhihu.com/equation?tex=E%27 是边集 https://www.zhihu.com/equation?tex=%5C%7B%28y_i%2C+y_%7Bi%2B1%7D%29%5C%7D_%7Bi+%3D+0%2C+...%2C+k%7D. https://www.zhihu.com/equation?tex=%5Csquare
举个例子, 如果我们有一个实例: https://www.zhihu.com/equation?tex=R+%3D+%5C%7Ba%2C+b%2C+c%2C+d%2C+e%2C+f%5C%7D%2C~S+%3D+%5C%7Bg%2C+h%5C%7D, 距离函数对存在连接的两点的边赋值1的距离, 如果两点间不存在连接, 则我们赋值2的距离.
下图是一斯坦纳树, 其代价为8:
我们使用 证明 1 中的论证来证明存在一个成本最多为16的的生成树. 而且事实上我们可以做得更好:
首先我们以DFS遍历 , 也就是如下顺序:
https://www.zhihu.com/equation?tex=a+%5Cto+g+%5Cto+d+%5Cto+g+%5Cto+f+%5Cto+g+%5Cto+a+%5Cto+h+%5Cto+c+%5Cto+h+%5Cto+b+%5Cto+h+%5Cto+a+%5Cto+e+%5Cto+a
如果我们将它视作一个从开始, 并在遍历所有顶点后返回的循环, 一些顶点访问了不止一次, 那么这个循环有代价16, 因为每条边都需要使用两次.
现在如果我们仍以DFS遍历, 但跳过所有的可选点和之前访问过的点, 那么我们会得到一个只访问所有必要点的顺序, 也就是:
https://www.zhihu.com/equation?tex=a+%5Cto+d+%5Cto+f+%5Cto+c+%5Cto+b+%5Cto+e
代价为10
因为这条路径是通过 "裁剪" 一条成本最多为2倍的路径获得的, 并且因为我们有三角不等式, 所以我们找到的路径也最多是代价的2倍.
引理 1 中的因子2是 不能进一步提升的, 因为存在代价较高的度量斯坦纳树问题的实例, 其中 的最小生成树的代价接近最小斯坦纳树代价的2倍. 举个例子, 考虑如下实例:
https://www.zhihu.com/equation?tex=S+%3D+%5C%7Bv_0%5C%7D%2C+%5Cquad+R+%3D+%5C%7Bv_1%2C+...%2C+v_n%5C%7D
https://www.zhihu.com/equation?tex=%5Cbegin%7Bcases%7D+%5C%3Ad%28v_0%2C+v_i%29+%3D+1+%26+i+%3D+1%2C+...%2C+n+%5C%5C+%5C%3Ad%28v_i%2C+v_j%29+%3D+2+%26+1+%5Cleq+i+%5Cleq+j+%5Cleq+n+%5Cend%7Bcases%7D
也就是所有必要点间的距离都是2, 但是他们对于另一端点为可选点的距离为1. 则最小斯坦纳树会有 https://www.zhihu.com/equation?tex=v_0 作为根, 节点 https://www.zhihu.com/equation?tex=v_1%2C+...%2C+v_n 作为树叶. 该树的代价为, 但的最小生成树代价为 https://www.zhihu.com/equation?tex=2n+-2, 因为最小生成树有个节点, https://www.zhihu.com/equation?tex=n+-+1 条边, 每条边代价是2.
2. 度量 vs 一般 斯坦纳树问题
一般斯坦纳树问题与度量斯坦纳树问题相似, 但我们允许任意的距离函数. 在这个情况中,的最小生成树 不再 能够给出不错的近似解. 比如这个极端实例:
https://www.zhihu.com/equation?tex=R+%3D+%5C%7Ba%2C+b%5C%7D%2C+%5Cquad+S%3D+%5C%7Bc%5C%7D++
https://www.zhihu.com/equation?tex=%5Cbegin%7Bcases%7D+d%28a%2C+b%29+%3D+10%5E%7B100%7D+%5C%5C+d%28a%2C+c%29+%3D+1+%5C%5C+d%28b%2C+c%29+%3D+1+%5Cend%7Bcases%7D
则的最小生成树有代价 https://www.zhihu.com/equation?tex=10%5E%7B100%7D 然而最小斯坦纳树的代价是2. 但是可以证明我们的度量斯坦纳树问题的2-approximate算法可以通过一些谨慎的方式转换为一般斯坦纳树问题的2-approximate算法.
引理 2 对每个 https://www.zhihu.com/equation?tex=c+%5Cgeq+1, 若存在一个可以在多项式时间内求解度量斯坦纳树问题的-approximate算法, 则同样存在一个可以在多项式时间内求解一般斯坦纳树问题的-approximate算法.
证明 2 假设我们有一个多项式时间的-approximate算法来求解度量斯坦纳树问题, 并且我们的输入为一般斯坦纳树问题的一个实例: . 我们将展示如何在多项式时间内找到一个-approximate的解.
对于每两点 https://www.zhihu.com/equation?tex=x%2C+y+%5Cin+X, 令为加权图 ( 顶点集合 , 权重) 中从到的最短路径长度 (注意不是代价!). 需要注意是满足三角不等式的函数, 因为在一个图中, 对于每三个点 https://www.zhihu.com/equation?tex=x%2C+y%2C+z, 从到的最短路径长度一定不能超过到的最短路径长度加上到的最短路径长度. 这使得 https://www.zhihu.com/equation?tex=%28X%2C+d%27%29 是度量斯坦纳树问题的一个实例, 且我们可以应用来找到树 https://www.zhihu.com/equation?tex=%5Cmathcal+T%27+%3D+%28V%27%2C+E%29, 它的代价为:
https://www.zhihu.com/equation?tex=cost_%7Bd%27%7D%28%5Cmathcal+T%27%29+%5Cleq+c+%5Ccdot+opt%28X%2C+d%27%29
注意, 对于每对点, https://www.zhihu.com/equation?tex=d%27%28x%2C+y%29+%5Cleq+d%28x%2C+y%29, 如此, 若 https://www.zhihu.com/equation?tex=%5Cmathcal+T%5E%5Cast 是原始输入 https://www.zhihu.com/equation?tex=%28X%2C+d%29 的最优树, 则我们有:
https://www.zhihu.com/equation?tex=opt%28X%2C+d%27%29+%5Cleq+cost_%7Bd%27%7D%28%5Cmathcal+T%5E%5Cast%29+%5Cleq+cost_d+%28%5Cmathcal+T%5E%5Cast%29+%3D+opt%28X%2C+d%29
结合上述两式, 可得:
https://www.zhihu.com/equation?tex=cost_%7Bd%27%7D+%28%5Cmathcal+T%27%29+%5Cleq+c+%5Ccdot+opt%28X%2C+d%29
现在, 从出发, 我们根据将每条边 https://www.zhihu.com/equation?tex=%28x%2C+y%29 代替为从到的最短路径来构造图 https://www.zhihu.com/equation?tex=%5Cmathcal+G+%3D+%28V%2C+E%29. 我们有:
https://www.zhihu.com/equation?tex=cost_%7Bd%7D+%28%5Cmathcal+G%29+%3D+%5Csum_%7B%28x%2C+y%29+%5Cin+E%7D+d%28x%2C+y%29+%5Cleq+%5Csum_%7B%28x%2C+y%29+%5Cin+E%27%7D+d%27%28x%2C+y%29+%3D+cost_%7Bd%27%7D%28%5Cmathcal+T%27%29
我们有不等式而不是等式的原因是的某些边可能属于多个最短路径, 所以在左边只数一次. 最后, 根据权重获取的生成树 . 现在树是一个合格的斯坦纳树, 我们有:
https://www.zhihu.com/equation?tex=cost_d%28%5Cmathcal+T%29+%5Cleq+cost_%7Bd%7D+%28%5Cmathcal+G%29+%5Cleq+c+%5Ccdot+opt%28X%2C+d%29 https://www.zhihu.com/equation?tex=%5Cquad+%5Cquad+%5Csquare
3. 旅行商问题 (Traveling Salesman Problem, TSP)
在旅行商问题中, 我们的输入是一个点集和一个对称距离函数 . 这个问题的目标是找到一个能够访问所有中的节点的循环, 且总距离尽可能短.
例如, 一个司机在机场接了7名乘客, 司机需要把他们送到家并返回机场, 这就构成了一个TSP的实例, 其中包含8个节点 (7个乘客住址和1个机场地址) 和距离函数 (或者我们可以理解成两个地点间的开车时间). 再例如, 一个DHL货车司机要进行一系列的货物配送, 然后返回仓库, 他也会遇到类似的问题. 事实上TSP是许多具体问题的基本模型, 它是组合优化中研究最多的问题之一.
我们可以区分四种TSP的版本. 一个区别是我们是否使用度量, 其中我们将限制输入中的满足三角不等式; 或者使用任意的的一般版本. 另一个区别是我们是否想在循环中至少访问每个节点一次, 或者说我们是否在找每个节点都恰好只访问一次解.
可以被证明, 除非 https://www.zhihu.com/equation?tex=P+%3D+NP, 否则对于一般无重复的TSP, 是没有可行的近似算法的.
在 优化3 中我们将展示其他的三种版本 (无重复的度量TSP, 有重复的一般TSP和有重复的度量TSP) 从近似的角度看都是等价的.
4. 习题1
已知一无向图 https://www.zhihu.com/equation?tex=%5Cmathcal+G+%3D+%28V%2C+E%29+. 目标是移除最小数量的边使得剩下的图不包含三角形, 也就是没有没有三个顶点的集合 https://www.zhihu.com/equation?tex=%28a%2C+b%2C+c%29 使得边 https://www.zhihu.com/equation?tex=%28a%2C+b%29%2C+%28b%2C+c%29 和 https://www.zhihu.com/equation?tex=%28a%2C+c%29 都在剩余的图中. 提供一个能在多项式时间内运行的3-approximate算法.
4.1. 思路
基本的思路是重复在图中寻找三角形, 并从那个三角形移除所有的边. 因为任何最优算法都必须从三角形移除至少一条边, 那么我们也必然可以得到3-approximate算法.
4.2. 算法描述
首先, 我们需要一个子路径去寻找图中的一个三角形. 假设图以邻接矩阵的形式存储, 我们考虑一个简单算法, 它检查三个节点 https://www.zhihu.com/equation?tex=%28u%2C+v%2C+w%29 的每个 https://www.zhihu.com/equation?tex=we%28_%7B3%7D%5E%7Bn%7D%29 组合, 并检查是否有边与它们相连. 这种方式是的算法需要 https://www.zhihu.com/equation?tex=O%28n%5E3%29 的时间复杂度去找到一个三角形 (或者汇报没有三角形). 进一步优化也是可能的.
第二步, 这个算法进行如下运算:
[*]while ( 图中存在任意三角形 ):
[*]令 https://www.zhihu.com/equation?tex=%28u%2C+w%2C+v%29 为中的一个三角形
[*]从中移除边 https://www.zhihu.com/equation?tex=%28u%2C+v%29%2C+%28u%2C+w%29 和 https://www.zhihu.com/equation?tex=%28v%2C+w%29
4.3. 为什么该算法可行
首先, 易知当算法结束时, 不会存在三角形. 则我们仅需证明为什么该算法是3-approximate算法.
定义的一个 三角形集合 包含不相交的三角形, 也就是没有共边的三角形 (但是可以共顶点). 注意该算法会生成一个三角形集合, 因为在每次迭代之后, 它都会从图中删除 前一个三角形的所有边. 另外, 若我们表示该算法生成的三角形集合为 , 则被该算法移除的边的数量为 https://www.zhihu.com/equation?tex=3%5Ccdot%7CS%7C.
令为要从图中移除的最优边集 (以保证中没有三角形). 注意对于任意的三角形集合 , 我们都可以得到 https://www.zhihu.com/equation?tex=%7Copt%7C+%5Cgeq+%7CS%7C, 因为必须 至少 移除中的每个三角形的一条边. 因此我们可以得出结论, 被上述算法移除的边的数量是 https://www.zhihu.com/equation?tex=3%5Ccdot+%7CS%7C+%5Cleq+3+%5Ccdot+%7Copt%7C, 所以这个算法是3-approximate算法.
<hr/>原文链接
页:
[1]