优化2: 一般斯坦纳树问题的近似

RhinoFreak · 发表于 2022-3-30 14:49

1. 近似度量斯坦纳树问题

在优化1 中我们定义了度量斯坦纳树问题:
输入是一个点集 $X = R \cup S$ , 其中  是必要点集,  是可选点集, 同时我们还有一个对称距离函数  使得每条边的距离为非零值 $d(x, y) = d(y, x) \geq 0$ . 最后, 还有一个额外的约束条件, 即  需要满足三角不等式:

$d(x, z) \leq d(x, y) + d(y, z) \quad \forall x, y, z \in X$
在这个例子中,  被称为度量. 该问题的目标是找到树 , 其中  是包含所有必要点和可能包含一些可选点的任意点集 , 使得代价 $cost_d (\mathcal T) := \sum_{(u, v) \in E} d(u, v)$ 最小. 优化1的最后我们讨论了一种完全无视  中可选点的算法, 该算法找到具有 必要点集  和由  定义的边权重 的加权图的最小生成树 (spanning tree)  .
现在让我们证明这一算法是2-approximate, 也就是, 它可以找到最多2倍最优解代价的解.
引理 1 令为度量斯坦纳树问题的一个实例, 并且  是具有  性质的斯坦纳树. 则存在另一树 $\mathcal T' = (R, E')$ 覆盖了  中的顶点, 并且只有  中的顶点使得 $cost_d(\mathcal T') \leq 2 \cdot cost_d(\mathcal T)$ .
特别是将该引理应用于最优斯坦纳树, 我们可以发现存在  的生成树, 其成本至多是最优斯坦纳树成本的2倍.
证明 1 考虑使用深度优先搜索 (Depth-First-Search, DFS) 来遍历树 , 也就是, 一个序列:

$\Big[x_0, x_1, x_2, ..., x_m\Big] \quad x_m = x_0$
按照在DFS期间考虑它们的顺序, 列出  的顶点, 包括每次递归调用结束时我们返回的一个顶点. 该序列描述了  元素的循环, 其总长度是 $\sum_{i=0}^m d(x_i, x_{i+1})$ 恰好是 , 因为这一循环恰好使用这个树的每条边2次.
现在令  为从  获取的序列 (通过移除  中顶点和保留只在  中第一次出现的顶点). 那么  包含  中所有顶点的路径, 当然此序列中也没有其他顶点, 且它的代价 $\sum_{i=0}^k d( y_i, y_{i+1} )$ 最多是循环  的代价 (这儿我们需要用到三角不等式), 那么我们可以得到  的代价最多为 . 注意  是个路径, 也是个树, 因此我们可以将  视作树 $(R, E')$ , 其中 $E'$ 是边集 $\{(y_i, y_{i+1})\}_{i = 0, ..., k}$ . $\square$
举个例子, 如果我们有一个实例: $R = \{a, b, c, d, e, f\},~S = \{g, h\}$ , 距离函数  对存在连接的两点的边赋值1的距离, 如果两点间不存在连接, 则我们赋值2的距离.

下图是一斯坦纳树, 其代价为8:

我们使用 证明 1 中的论证来证明存在一个成本最多为16的  的生成树. 而且事实上我们可以做得更好:
首先我们以DFS遍历 , 也就是如下顺序:

$a \to g \to d \to g \to f \to g \to a \to h \to c \to h \to b \to h \to a \to e \to a$
如果我们将它视作一个从  开始, 并在遍历所有顶点后返回  的循环, 一些顶点访问了不止一次, 那么这个循环有代价16, 因为每条边都需要使用两次.
现在如果我们仍以DFS遍历, 但跳过所有的可选点和之前访问过的点, 那么我们会得到一个只访问所有必要点的顺序, 也就是:

$a \to d \to f \to c \to b \to e$

代价为10

因为这条路径是通过 &#34;裁剪&#34; 一条成本最多为  2倍的路径获得的, 并且因为我们有三角不等式, 所以我们找到的路径也最多是  代价的2倍.
引理 1 中的因子2是 不能进一步提升的, 因为存在代价较高的度量斯坦纳树问题的实例, 其中的最小生成树的代价接近最小斯坦纳树代价的2倍. 举个例子, 考虑如下实例:

$S = \{v_0\}, \quad R = \{v_1, ..., v_n\}$

$\begin{cases} \:d(v_0, v_i) = 1 & i = 1, ..., n \\ \:d(v_i, v_j) = 2 & 1 \leq i \leq j \leq n \end{cases}$
也就是所有必要点间的距离都是2, 但是他们对于另一端点为可选点的距离为1. 则最小斯坦纳树会有 $v_0$ 作为根, 节点 $v_1, ..., v_n$ 作为树叶. 该树的代价为  , 但  的最小生成树代价为 $2n -2$ , 因为最小生成树有  个节点, $n - 1$ 条边, 每条边代价是2.
2. 度量 vs 一般斯坦纳树问题

一般斯坦纳树问题与度量斯坦纳树问题相似, 但我们允许任意的距离函数. 在这个情况中,  的最小生成树不再能够给出不错的近似解. 比如这个极端实例:

$R = \{a, b\}, \quad S= \{c\}$

$\begin{cases} d(a, b) = 10^{100} \\ d(a, c) = 1 \\ d(b, c) = 1 \end{cases}$
则  的最小生成树有代价 $10^{100}$ 然而最小斯坦纳树的代价是2. 但是可以证明我们的度量斯坦纳树问题的2-approximate算法可以通过一些谨慎的方式转换为一般斯坦纳树问题的2-approximate算法.
引理 2 对每个 $c \geq 1$ , 若存在一个可以在多项式时间内求解度量斯坦纳树问题的-approximate算法, 则同样存在一个可以在多项式时间内求解一般斯坦纳树问题的-approximate算法.
证明 2 假设我们有一个多项式时间的-approximate算法  来求解度量斯坦纳树问题, 并且我们的输入为一般斯坦纳树问题的一个实例: . 我们将展示如何在多项式时间内找到一个-approximate的解.
对于每两点 $x, y \in X$ , 令  为加权图 ( 顶点集合 , 权重  ) 中从  到  的最短路径长度 (注意不是代价!). 需要注意  是满足三角不等式的函数, 因为在一个图中, 对于每三个点 $x, y, z$ , 从  到  的最短路径长度一定不能超过  到  的最短路径长度加上  到  的最短路径长度. 这使得 $(X, d')$ 是度量斯坦纳树问题的一个实例, 且我们可以应用  来找到树 $\mathcal T' = (V', E)$ , 它的代价为:

$cost_{d'}(\mathcal T') \leq c \cdot opt(X, d')$
注意, 对于每对点, $d'(x, y) \leq d(x, y)$ , 如此, 若 $\mathcal T^\ast$ 是原始输入 $(X, d)$ 的最优树, 则我们有:

$opt(X, d') \leq cost_{d'}(\mathcal T^\ast) \leq cost_d (\mathcal T^\ast) = opt(X, d)$
结合上述两式, 可得:

$cost_{d'} (\mathcal T') \leq c \cdot opt(X, d)$
现在, 从  出发, 我们根据  将每条边 $(x, y)$ 代替为从  到  的最短路径来构造图 $\mathcal G = (V, E)$ . 我们有:

$cost_{d} (\mathcal G) = \sum_{(x, y) \in E} d(x, y) \leq \sum_{(x, y) \in E'} d'(x, y) = cost_{d'}(\mathcal T')$
我们有不等式而不是等式的原因是  的某些边可能属于多个最短路径, 所以在左边只数一次. 最后, 根据权重  获取  的生成树 . 现在树  是一个合格的斯坦纳树, 我们有:

$cost_d(\mathcal T) \leq cost_{d} (\mathcal G) \leq c \cdot opt(X, d)$ $\quad \quad \square$
3. 旅行商问题 (Traveling Salesman Problem, TSP)

在旅行商问题中, 我们的输入是一个点集  和一个对称距离函数 . 这个问题的目标是找到一个能够访问所有  中的节点的循环, 且总距离尽可能短.
例如, 一个司机在机场接了7名乘客, 司机需要把他们送到家并返回机场, 这就构成了一个TSP的实例, 其中  包含8个节点 (7个乘客住址和1个机场地址) 和距离函数 (或者我们可以理解成两个地点间的开车时间). 再例如, 一个DHL货车司机要进行一系列的货物配送, 然后返回仓库, 他也会遇到类似的问题. 事实上TSP是许多具体问题的基本模型, 它是组合优化中研究最多的问题之一.
我们可以区分四种TSP的版本. 一个区别是我们是否使用度量, 其中我们将限制输入中的  满足三角不等式; 或者使用任意的  的一般版本. 另一个区别是我们是否想在循环中至少访问每个节点一次, 或者说我们是否在找每个节点都恰好只访问一次解.
可以被证明, 除非 $P = NP$ , 否则对于一般无重复的TSP, 是没有可行的近似算法的.
在优化3 中我们将展示其他的三种版本 (无重复的度量TSP, 有重复的一般TSP和有重复的度量TSP) 从近似的角度看都是等价的.
4. 习题1

已知一无向图 $\mathcal G = (V, E)$ . 目标是移除最小数量的边使得剩下的图不包含三角形, 也就是没有没有三个顶点的集合 $(a, b, c)$ 使得边 $(a, b), (b, c)$ 和 $(a, c)$ 都在剩余的图中. 提供一个能在多项式时间内运行的3-approximate算法.
4.1. 思路

基本的思路是重复在图  中寻找三角形, 并从那个三角形移除所有的边. 因为任何最优算法都必须从三角形移除至少一条边, 那么我们也必然可以得到3-approximate算法.
4.2. 算法描述

首先, 我们需要一个子路径去寻找图  中的一个三角形. 假设图以邻接矩阵的形式存储, 我们考虑一个简单算法, 它检查三个节点 $(u, v, w)$ 的每个 $we(_{3}^{n})$ 组合, 并检查是否有边与它们相连. 这种方式是的算法需要 $O(n^3)$ 的时间复杂度去找到一个三角形 (或者汇报没有三角形). 进一步优化也是可能的.
第二步, 这个算法进行如下运算:

while ( 图中存在任意三角形 ):
- 令 $(u, w, v)$ 为中的一个三角形
- 从中移除边 $(u, v), (u, w)$ 和 $(v, w)$

4.3. 为什么该算法可行

首先, 易知当算法结束时, 不会存在三角形. 则我们仅需证明为什么该算法是3-approximate算法.
定义的一个 三角形集合 包含不相交的三角形, 也就是没有共边的三角形 (但是可以共顶点). 注意该算法会生成一个三角形集合, 因为在每次迭代之后, 它都会从图中删除前一个三角形的所有边. 另外, 若我们表示该算法生成的三角形集合为 , 则被该算法移除的边的数量为 $3\cdot|S|$ .
令为要从图中移除的最优边集 (以保证中没有三角形). 注意对于任意的三角形集合 , 我们都可以得到 $|opt| \geq |S|$ , 因为必须至少移除中的每个三角形的一条边. 因此我们可以得出结论, 被上述算法移除的边的数量是 $3\cdot |S| \leq 3 \cdot |opt|$ , 所以这个算法是3-approximate算法.
<hr/>原文链接

		自动登录	找回密码
密码			立即注册

优化2: 一般斯坦纳树问题的近似

本帖子中包含更多资源