近似算法
1 近似算法与近似比¶
1.1 近似算法的定义¶
定义：近似算法
\(A\) 是一个多项式时间算法且对组合优化问题 \(P\) 的每一个实例 \(I\) 输出一个可行解 \(s\)。记 \(A(I) = c(s)\)，\(c(s)\) 是 \(s\) 的值。
近似算法的性能估计：
- 当 \(P\) 是 最小化 问题时，记 \(r_A(I) = A(I) / OPT(I)\)
- 当 \(P\) 是 最大化 问题时，记 \(r_A(I) = OPT(I) / A(I)\)
最优化算法：恒有 \(A(I) = OPT(I)\)，即 \(r_A(I) = 1\)。
\(A\) 的近似比为 \(r\)（\(A\) 是 \(r\)-近似算法）：对每一个实例 \(I\)，\(r_A(I) \leq r\)。
\(A\) 具有常数近似比：\(r\) 是一个常数。
1.2 可近似性分类¶
假设 \(P \neq NP\)，NP 难的组合优化问题按可近似性可分成 3 类：
| 类别 | 说明 | 代表问题 |
|---|---|---|
| 完全可近似的 | 对任意小的 \(\varepsilon > 0\)，存在 \((1 + \varepsilon)\)-近似算法 | 背包问题 |
| 可近似的 | 存在具有常数比的近似算法 | 最小顶点覆盖、多机调度 |
| 不可近似的 | 不存在具有常数比的近似算法 | 货郎问题（一般情况） |
2 最小顶点覆盖问题¶
2.1 问题描述¶
问题：任给图 \(G = \langle V, E \rangle\)，求 \(G\) 的顶点数最少的顶点覆盖。
2.2 MVC 算法¶
算法：MVC
开始时令 \(V' = \emptyset\)。任取一条边 \((u, v)\)，把 \(u\) 和 \(v\) 加入 \(V'\) 并删去 \(u\) 和 \(v\) 及其关联的边。重复上述过程，直至删去所有的边为止。\(V'\) 为所求的顶点覆盖。
例
一个最优解：\(\{1, 3, 6, 9\}\)，MVC 的解：\(\{1, 2, 3, 4, 5, 6\}\)。
2.3 MVC 算法分析¶
时间复杂度：\(O(m)\)，\(m = |E|\)。
近似比：
- 记 \(|V'| = 2k\)，\(V'\) 由 \(k\) 条互不关联的边的端点组成。为了覆盖这 \(k\) 条边需要 \(k\) 个顶点，从而 \(OPT(I) \geq k\)。于是：
- 设图 \(G\) 由 \(k\) 条互不关联的边构成，显然 \(MVC(I) = 2k\)，\(OPT(I) = k\)。
结论
MVC 是 2-近似算法，且这个近似比已经是最好的、不可改进的了。
2.4 近似算法的分析框架¶
近似算法的分析包含两个方面：
- 算法的运行时间
- 近似比
分析近似比的方法：
- 估计最优解的值（建立最优值与近似解的值之间的关系）
- 构造使算法产生最坏的解的实例。如果这个解的值与最优值的比达到或者可以任意地接近得到的近似比（这样的实例称作 紧实例），那么说明这个近似比已经是最好的、不可改进的了；否则说明还有进一步的研究余地
研究问题本身的可近似性：即在 \(P \neq NP\)（或其他更强）的假设下，该问题近似算法的近似比的下界。
3 多机调度问题¶
3.1 问题描述¶
多机调度问题：任给有穷的作业集 \(A\) 和 \(m\) 台相同的机器，作业 \(a\) 的处理时间为正整数 \(t(a)\)，每一项作业可以在任一台机器上处理。如何把作业分配给机器才能使完成所有作业的时间最短？
即，如何把 \(A\) 划分成 \(m\) 个不相交的子集 \(A_i\) 使得：
最小？
3.2 贪心法 G-MPS¶
负载：分配给一台机器的作业的处理时间之和。
算法：G-MPS
按输入的顺序分配作业，把每一项作业分配给 当前负载最小 的机器。如果当前负载最小的机器有 2 台或 2 台以上，则分配给其中的任意一台（比如标号最小的一台）。
例
3 台机器，8 项作业，处理时间为 \(3, 4, 3, 6, 5, 3, 8, 4\)。
- G-MPS 的分配方案：\(\{1, 4\}, \{2, 6, 7\}, \{3, 5, 8\}\)，负载分别为 \(3+6=9\)，\(4+3+8=15\)，\(3+5+4=12\)，完成时间 15
- 最优分配方案：\(\{1, 3, 4\}, \{2, 5, 6\}, \{7, 8\}\)，负载分别为 \(3+3+6=12\)，\(4+5+3=12\)，\(8+4=12\)，完成时间 12
3.3 G-MPS 的性能¶
定理
对多机调度问题的每一个有 \(m\) 台机器的实例 \(I\)：
证明
两个事实：
- \(m\) 个机器的最大负载不小于平均负载：\(OPT(I) \geq \frac{1}{m} \sum_{a \in A} t(a)\)
- \(m\) 个机器的最大负载不小于单个任务负载：\(OPT(I) \geq \max_{a \in A} t(a)\)
设机器 \(M_j\) 的负载最大，记作 \(t(M_j)\)。又设 \(b\) 是最后被分配给机器 \(M_j\) 的作业。根据算法，在考虑分配 \(b\) 时 \(M_j\) 的负载最小，故：
于是：
紧实例
\(m\) 台机器，\(m(m-1)+1\) 项作业，前 \(m(m-1)\) 项作业的处理时间都为 1，最后一项作业的处理时间为 \(m\)。
- G-MPS 把前 \(m(m-1)\) 项作业平均地分配给 \(m\) 台机器，每台 \(m-1\) 项，最后一项任意地分配给一台机器：\(G\text{-}MPS(I) = 2m - 1\)
- 最优分配方案把前 \(m(m-1)\) 项作业平均地分配给 \(m-1\) 台机器，每台 \(m\) 项，最后一项分配给留下的机器：\(OPT(I) = m\)
比值为 \(\frac{2m-1}{m} = 2 - \frac{1}{m}\)，达到上界。
3.4 改进的贪心近似算法¶
算法：DG-MPS（递降贪心法）
首先按处理时间从大到小重新排列作业，然后运用 G-MPS。
分析：DG-MPS 增加排序时间 \(O(n \log n)\)，仍然是多项式时间。
定理
对多机调度问题的每一个有 \(m\) 台机器的实例 \(I\)：
证明
设作业按处理时间从大到小排列为 \(a_1, a_2, \ldots, a_n\)，仍考虑负载最大的机器 \(M_j\) 和最后分配给 \(M_j\) 的作业 \(a_i\)。
- 若 \(M_j\) 只有一个作业，则 \(i = 1\)，必为最优解
- 若 \(M_j\) 有 2 个或 2 个以上作业，则 \(i \geq m+1\)（\(n \geq m+1\)）
于是：
与 G-MPS 的证明相同，由分配 \(a_i\) 时 \(M_j\) 的负载最小可得：
4 货郎问题（TSP）¶
本节考虑 满足三角不等式 的货郎问题。
4.1 最邻近法 NN¶
算法：NN
从任意一个城市开始，在每一步取离当前所在城市最近的尚未到过的城市作为下一个城市。若这样的城市不止一个，则任取其中的一个。直至走遍所有城市，最后回到开始出发的城市。
NN 性能很坏的实例
\(NN(I) = 27\)，\(OPT(I) = 15\)。
定理
对于货郎问题所有满足三角不等式的 \(n\) 个城市的实例 \(I\)，总有：
而且，对于每一个充分大的 \(n\)，存在满足三角不等式的 \(n\) 个城市的实例 \(I\) 使得：
结论
NN 算法不是常数近似比的算法，不能实际应用。
问题
对于货郎问题（或者满足三角不等式的子问题）是否存在常数近似比的算法？
4.2 最小生成树法 MST¶
算法：MST
- 求图的一棵最小生成树 \(T\)
- 沿着 \(T\) 走两遍得到图的一条欧拉回路
- 顺着这条欧拉回路，跳过已走过的顶点，抄近路得到一条哈密顿回路
求最小生成树和欧拉回路都可以在多项式时间内完成，故算法是多项式时间的。
定理
对货郎问题的所有满足三角不等式的实例 \(I\)：
证明
因为从哈密顿回路中删去一条边就得到一棵生成树，故 \(T\) 的权小于 \(OPT(I)\)。沿 \(T\) 走两遍的长小于 \(2 \cdot OPT(I)\)。因为满足三角不等式，抄近路不会增加长度，故：
结论
MST 是 2-近似算法。
紧实例
\(OPT(I) = 2n\)，\(MST(I) = 4n - 2\)。
4.3 最小权匹配法 MM¶
算法：MM
- 求图的一棵最小生成树 \(T\)
- 记 \(T\) 的所有奇度顶点在原图中的导出子图为 \(H\)，\(H\) 有偶数个顶点，求 \(H\) 的最小匹配 \(M\)
- 把 \(M\) 加入 \(T\) 得到一个欧拉图，求这个欧拉图的欧拉回路
- 沿着这条欧拉回路，跳过已走过的顶点，抄近路得到一条哈密顿回路
求任意图最小权匹配的算法是多项式时间的，因此 MM 是多项式时间的。
定理
对货郎问题的所有满足三角不等式的实例 \(I\)：
证明
由于满足三角不等式，导出子图 \(H\) 中的最短哈密顿回路 \(C\) 的长度不超过原图中最短哈密顿回路的长度 \(OPT(I)\)。沿着 \(C\) 隔一条边取一条边，得到 \(H\) 的一个匹配。总可以使这个匹配的权不超过 \(C\) 长的一半。因此，\(H\) 的最小匹配 \(M\) 的权不超过 \(OPT(I)/2\)，求得的欧拉回路的长小于 \((3/2) \cdot OPT(I)\)。抄近路不会增加长度，得证。
结论
MM 是 3/2-近似算法。
4.4 货郎问题的不可近似性¶
定理
货郎问题（不要求满足三角不等式）是 不可近似的，除非 \(P = NP\)。
证明
假设不然，设 \(A\) 是货郎问题的近似算法，其近似比 \(r \leq K\)，\(K\) 是常数。任给图 \(G = \langle V, E \rangle\)，如下构造货郎问题的实例 \(I_G\)：
- 城市集 \(V\)
- \(\forall u, v \in V\)：
其中 \(|V| = n\)。
若 \(G\) 有哈密顿回路，则 \(OPT(I_G) = n\)，\(A(I_G) \leq r \cdot OPT(I_G) \leq Kn\)。
否则 \(OPT(I_G) > Kn\)，\(A(I_G) \geq OPT(I_G) > Kn\)。
所以，\(G\) 有哈密顿回路当且仅当 \(A(I_G) \leq Kn\)。
下述算法可以判断图 \(G\) 是否有哈密顿回路：
- 由 \(I\) 构造货郎问题的实例 \(I_G\)
- 对 \(I_G\) 运用近似算法 \(A\)
- 若 \(A(I_G) \leq Kn\)，则输出 "Yes"；否则输出 "No"
由于 \(K\) 是固定的常数，构造 \(I_G\) 可在 \(O(n^2)\) 时间内完成且 \(|I_G| = O(n^2)\)。\(A\) 是多项式时间的，\(A\) 对 \(I_G\) 可在 \(n\) 的多项式时间内完成计算，所以上述算法是 HC 的多项式时间算法。而 HC 是 NP 完全的，推得 \(P = NP\)。
5 0-1 背包问题¶
5.1 问题描述¶
0-1 背包问题的优化形式：任给 \(n\) 件物品和一个背包，物品 \(i\) 的重量为 \(w_i\)，价值为 \(v_i\)（\(1 \leq i \leq n\)），背包的重量限制为 \(B\)，其中 \(w_i, v_i\) 以及 \(B\) 都是正整数。把哪些物品装入背包才能在不超过重量限制的条件下使得价值最大？
即，求子集 \(S^* \subseteq \{1, 2, \ldots, n\}\) 使得：
下面不妨设所有物品的重量 \(w_i \leq B\)，否则将这个物品排除在外。
5.2 简单的贪心算法 G-KK¶
算法：G-KK
- 按单位重量的价值从大到小排列物品。设 \(v_1/w_1 \geq v_2/w_2 \geq \cdots \geq v_n/w_n\)
- 顺序检查每一件物品，只要能装得下就将它装入背包，设装入背包的总价值为 \(V\)
- 求 \(v_k = \max\{ v_i \mid i = 1, 2, \ldots, n \}\)。若 \(v_k > V\)，则将背包内的物品换成物品 \(k\)
例
\((w_i, v_i)\)：\((3, 7), (4, 9), (5, 9), (2, 2)\)；\(B = 6\)。
G-KK 给出的解是装入 \((3, 7)\) 和 \((2, 2)\)，总价值为 9。若把第3件物品改为 \((5, 10)\)，则装入第3件，总价值为 10。这两个实例的最优解都是装入 \((4, 9)\) 和 \((2, 2)\)，总价值为 11。
定理
对 0-1 背包问题的任何实例 \(I\)：
证明
设物品 \(l\) 是第一件未装入背包的物品，由于物品按单位重量的价值从大到小排列，故有：
结论
G-KK 是 2-近似算法。
5.3 多项式时间近似方案 PTAS¶
算法：PTAS
输入：\(\varepsilon > 0\) 和实例 \(I\)
- 令 \(m = \lceil 1/\varepsilon \rceil\)
- 按单位重量的价值从大到小排列物品。设 \(v_1/w_1 \geq v_2/w_2 \geq \cdots \geq v_n/w_n\)
- 对每一个 \(t = 1, 2, \ldots, m\) 和 \(t\) 件物品，检查这 \(t\) 件物品的重量之和。若它们的重量之和不超过 \(B\)，则接着用 G-KK 把剩余的物品装入背包
- 比较得到的所有装法，取其中价值最大的作为近似解
PTAS 是一簇算法。对每一个固定的 \(\varepsilon > 0\)，PTAS 是一个算法，记作 \(PTAS_\varepsilon\)。
定理
对每一个 \(\varepsilon > 0\) 和 0-1 背包问题的实例 \(I\)：
且 \(PTAS_\varepsilon\) 的时间复杂度为 \(O(n^{1/\varepsilon + 2})\)。
证明
设最优解为 \(S^*\)。若 \(|S^*| \leq m\)，则算法必得到 \(S^*\)。设 \(|S^*| > m\)。考虑计算中以 \(S^*\) 中 \(m\) 件价值最大的物品为基础，用 G-KK 得到的结果 \(S\)。设物品 \(l\) 是 \(S\) 中第一件未装入背包的物品，则：
因为 \(S\) 已包含 \(S^*\) 中 \(m\) 件价值最大的物品，它们的价值都不小于 \(v_l\)，所以：
因而：
时间复杂度方面，从 \(n\) 件物品中取 \(t\) 件（\(1 \leq t \leq m\)）的取法总数为：
每种取法再调用一次 \(O(n)\) 的 G-KK，因此时间复杂度为 \(O(n^{m+1})\)。又 \(m=\lceil 1/\varepsilon\rceil \leq 1/\varepsilon+1\)，所以：
5.4 伪多项式时间算法¶
动态规划算法：
记 \(G_k(d)\) 表示只考虑前 \(k\) 件物品时，为了得到不小于 \(d\) 的价值，至少要装入的物品重量：
其中 \(0 \leq k \leq n\)，\(0 \leq d \leq D\)，\(D=v_1+v_2+\cdots+v_n\)，约定 \(\min \emptyset = +\infty\)。
目标值为：
递推公式：
其中 \(0 \leq k \leq n-1\)，\(0 \leq d \leq D\)。
时间复杂度：\(O(nD) = O(n^2 v_{\max})\)，是 伪多项式时间算法。
5.5 完全多项式时间近似方案 FPTAS¶
算法：FPTAS
输入：\(\varepsilon > 0\) 和实例 \(I\)
- 令 \(b = \max\left\{\left\lfloor \frac{v_{\max}}{(1 + 1/\varepsilon)n} \right\rfloor, 1\right\}\)
- 令 \(v_i' = \lceil v_i / b \rceil\)（\(1 \leq i \leq n\)）。把所有 \(v_i\) 换成 \(v_i'\)，记新得实例为 \(I'\)
- 对 \(I'\) 应用动态规划算法 \(A\) 得到解 \(S\)，把 \(S\) 取作实例 \(I\) 的解
定理
对每一个 \(\varepsilon > 0\) 和 0-1 背包问题的实例 \(I\)：
并且 FPTAS 的时间复杂度为 \(O(n^3(1 + 1/\varepsilon))\)。
证明
由于 \(v_i' = \lceil v_i / b \rceil\)，有：
对任意的 \(T \subseteq \{1, 2, \ldots, n\}\)：
设 \(I\) 的最优解为 \(S^*\)，注意到 \(S\) 是 \(I'\) 的最优解，故有：
对每一个 \(\varepsilon > 0\)，若 \(b = 1\)，则 \(I'\) 就是 \(I\)，\(S\) 是 \(I\) 的最优解。设 \(b > 1\)，则：
得 \(OPT(I) < (1 + \varepsilon) \cdot FPTAS(I)\)。
时间：主要是 \(A\) 对 \(I'\) 的运算。因为 \(v_{\max}' = \lceil v_{\max}/b\rceil = O(n(1+1/\varepsilon))\)，所以时间复杂度为：
6 总结¶
| 问题 | 算法 | 近似比 | 可近似性 |
|---|---|---|---|
| 最小顶点覆盖 | MVC | 2 | 可近似 |
| 多机调度 | G-MPS | \(2 - 1/m\) | 可近似 |
| 多机调度 | DG-MPS | \(3/2 - 1/(2m)\) | 可近似 |
| TSP（三角不等式） | NN | 非常数 | — |
| TSP（三角不等式） | MST | 2 | 可近似 |
| TSP（三角不等式） | MM | 3/2 | 可近似 |
| TSP（一般） | — | 不可近似 | 不可近似（除非 P=NP） |
| 0-1 背包 | G-KK | 2 | 完全可近似 |
| 0-1 背包 | PTAS | \(1 + \varepsilon\) | 完全可近似 |
| 0-1 背包 | FPTAS | \(1 + \varepsilon\) | 完全可近似 |