近似算法¶

约 2053 个字预计阅读时间 7 分钟

对于一个最优化问题的算法，主要有以下三个期望

Note

1.算法需要能找到确切的最优解 2.算法需要能高效(在多项式时间内)运行 3.算法是通用的,需要可以解决一类问题中的所有实例，而不仅仅是单个实例有效

然而，对于某些问腿，我们有可能无法实现以上三个期望，例如NPC问题，所以我们可以退而求其次，做一些妥协；

如果算法舍弃第二个期望，则是用例如回溯等方法在指数时间内解决问题，这对于输入不大的情况是可以接受的；
如果舍弃第三个期望，我们相当于为问题找到一些容易解决的特例；
如果舍弃第一个期望，但我们能保证高效找到的解是和真正的最优解 “相差不大” 的，那么我们称这类算法为近似算法。

基本概念¶

Definition

假设有某类问题 $\mathcal{I}$（例如背包问题），其中的一个具体实例记为 $I$（当给定问题的参数定义的时候即为一个实例），且有一个复杂度为多项式的近似算法 $A$。定义：

$A(I)$ 为算法 $A$ 在实例 $I$ 上得到的解；
$\mathbf{OPT}(I)$ 为实例 $I$ 的最优解。

考虑 $I$ 是最小化问题，若存在 $r > 1$，对任意的 $I$ 都有：

\[ A(I) \leqslant r \cdot \mathbf{OPT}(I), \]

那么称 $A$ 为该问题的 $r$-近似算法（即对于任何可能的问题实例，$A$ 给出的解都不会比最优解的 $r$ 倍大）。我们特别关心其中可以取到的最小 $r$，称：

\[ \rho = \inf\{r : A(I) \leqslant r \cdot \mathbf{OPT}(I), \forall I\} \]

为 近似比（approximation ratio），即算法 $A$ 最紧的近似界。它可以等价定义为：

\[ \rho = \sup_{\mathcal{I}} \frac{A(I)}{\mathbf{OPT}(I)} \]

即这个比值在多实例中的比值是最紧的界。反之，如果是最大化问题，那么上述公式改为：

\[ \rho = \sup_{\mathcal{I}} \frac{\mathbf{OPT}(I)}{A(I)} \]

将两者合并起来，可以统一写作：

\[ \rho = \sup_{\mathcal{I}} \left\{ \frac{\mathbf{OPT}(I)}{A(I)}, \frac{A(I)}{\mathbf{OPT}(I)} \right\}. \]

由于$OPT$算法一般是难以确定的，所以确定近似比一般有以下两个步骤

首先寻找到一个 $ r > 1 $，对于任何实例 $ I $，都有 $ A(I) \leqslant r \cdot \text{OPT}(I) $（可以首先找到 $ \text{OPT}(I) $ 的一个下界 $ \text{LB}(I) \leqslant \text{OPT}(I) $，然后让 $ A(I) \leqslant r \cdot \text{LB}(I) $ 即可）；
接下来证明 $ r $ 是不可改进的，即对于任意的 $ \epsilon > 0 $，都存在在一个实例 $ I_\epsilon $，使得 $ A(I_\epsilon) \geqslant (r-\epsilon) \cdot \text{OPT}(I_\epsilon) $。

PTAS¶

PTAS（多项式时间近似方案，Polynomial time approximation scheme）：存在算法 A，使得对每一个固定的 $\varepsilon > 0$，对任意的实例 $I$ 都有

\[ A(I) \leqslant (1+\varepsilon) \cdot \text{OPT}(I) \]

且算法 $ A $ 的运行时间可以被问题规模 $ |I| $ 的多项式上界所限制。则称 $ A $ 是该问题的一个 PTAS。

理论上，算法 $ A $ 在多项式时间内可以近似：不过不同的 $ \varepsilon $，$ A $ 的运行时间也可能不可能。例如，如果算法可以给出一个复杂度为 $ O(|I|^{1/\epsilon}) $ 的解，这样算法的表现就会很糟糕，因为指数很大。一般可以将 PTAS 的复杂度记为 $ O(|I|^{(1/\epsilon)}) $。

EPTAS和FPTAS¶

EPTAS (Efficient PTAS): 在 PTAS 的基础上，要求算法 $ A $ 的复杂度是 $ O(|I|^c) $，其中 $ c > 0 $ 是与$\varepsilon$无关的常数。可以将 EPTS 的复杂度记为 $ |I^{O(1)}| f(1/\varepsilon）$。

FPTAS (Fully PTAS): 在 PTAS 的基础上，要求算法 $ A $ 的运行时间关于 $ |I| $ 和 $\varepsilon$ 都是多项式项，即可以将 FPTAS 的复杂度记为 $|I|^{O(1)} (1/\varepsilon)^{O(1)}$

装箱问题(一维)¶

问题描述

有 $n$ 个物品，每个物品的大小为 $s_i$，有若干个箱子，每个箱子的大小为 $C$，要求将所有物品放入箱子中，使得每个箱子的大小不超过 $C$，并且使得所需的箱子数目尽可能少。

给定若干个物品，判断它们是否可由两个箱子装下是 NP 完全的

接下来我们默认$C=1$，即箱子的大小为1，方便讨论。

关于一维装箱问题，除非 $P=NP$，否则不存在多项式时间的算法满足

\[ A(I) \leqslant \alpha \cdot \text{OPT}(I) \]

其中 $\alpha < \frac{3}{2}$。

Proof

使用反证法，如果存在近似比小于 $\frac{3}{2}$ 的算法，那么可以用这个算法$A$来解决NPC的判断物品是否可以由两个箱子装下的问题。

如果物品可以由两个箱子装下，那么$OPT=2$，则$A(I) < \frac{3}{2} \cdot 2 = 3$，即$A(I) < 3$；此时$A(I)=2$，那么$A$可以判断；
如果物品不可以由两个箱子装下，那么$OPT \geqslant 3$，则$A(I)$至少为$3$，即$A(I) \geqslant 3$；但是由于近似比小于$\frac{3}{2}$，所以由$A(I)$可以判断此时OPT不可能是$2$。此时这个近似算法$A$就可以判断物品是否可以由两个箱子装下。

综上，我们用多项式算法$A$来解决NPC问题，所以只可能有P=NP。

在装箱问题中，我们一般不关心全部的实例，而关心 $OPT(I)$ 较大的那些实例。因此定义 “渐近近似比（asymptotic approximation ratio）” 如下：

Definition

对于一维装箱问题，定义渐近近似比为,对于任意常数 $\alpha \geqslant 1$,对于任意实例 $I$，存在常数 $k$，使得

\[ A(I) \leqslant \alpha \cdot OPT(I) + k \]

则称所有满足上式的 $\alpha$ 的下确界为$A$渐近近似比。

$k$可以是一个常数，也可以是$OPT(I)$的一个高阶无穷小。

Quote

装箱问题中，若所有的物品信息在开始装箱前已知，则它是离线（offline）问题；若初始时物品信息并不全部给出，例如物品在传送带上逐个到达，需要我们即时安排，而我们对未到达物品信息一无所知，同时做出的决定无法更改，此时称为在线（online）问题。“近似比” 通常用来描述离线问题近似算法的性能。而对于在线问题，一般用 “竞争比（competitive ratio）” 的概念。

Next Fit¶

Next Fit 算法是一种简单的装箱算法，其思想是：对于每个物品，尝试将其放入当前箱子，如果放不下，则关闭当前箱子，并开出一个新箱子，将其放入；

Next Fit 算法有一个性质：相邻两个箱子的大小之和肯定大于1，否则就不需要开新箱子；

根据这个，我们可以证明：

\[ NF(I) \leqslant 2 \cdot OPT(I) - 1 \]

即

\[ OPT(I) \geqslant \frac{NF(I) + 1}{2} \]

换句话说，如果我们的算法的箱子数目用了$2M$个，那么最优解至少要用$M+1$个箱子。

Proof

令 $ S(B_i) $ 为箱子 $ B_i $ 中物品的大小之和，那么有：

\[\begin{cases} S(B_1) + S(B_2) > 1 \\ S(B_3) + S(B_4) > 1 \\ \ldots \\ S(B_{2M-1}) + S(B_{2M}) > 1 \end{cases}\]

将所有不等式相加，得到：

\[ \sum_{i=1}^{2M} S(B_i) > M \]

所以总的大小严格大于 $M$，即最优解箱子数目至少为 $M+1$。

事实上$NF$装箱的近似比就是$2$,不会再有比这个小的了；

下确界的例子

考虑$M$组物品，每组物品的大小为$\dfrac{1}{2},\varepsilon$,最后再加一个$\dfrac{1}{2}$,且满足$M\varepsilon < 1$,此时$NF$算法需要$M+1$个箱子，而最优解需要$M/2+1$个箱子，所以$NF$算法的下确界为$2$。

Any Fit¶

这是一类的Fit方案，满足: 当物品到达时，除非所有目前打开的箱子都无法装下该物品，才允许打开一个新箱子

主要包括：

(FF)First Fit: 按箱子打开的顺序从早到晚检查,将物品放入第一个能放下的箱子中；
(BF)Best Fit: 将物品放入剩余空间最小的箱子中,最大化利用箱子空间；
(WF)Worst Fit: 将物品放入剩余空间最大的箱子中;

前面的所有 Fit 算法都是在线算法。此外，Any Fit 的三种算法都满足相邻两个箱子物品尺寸之和大于1，因此它们都不会比 NF 差。而前面 NF 的下界实例也适用于 WF，因此 WF 和 NF 一样差。

FF VS BF

从定义上来看，BF最大化利用了空间，似乎表现会比FF好，但是实际上并不能很好判断两者的优劣：

0.5、0.7、0.1、0.4、0.3，FF=2；BF=3；
0.5、0.7、0.3、0.5，FF=3；BF=2；

从上面的例子可以看出，BF并不一定比FF好，FF也不一定比BF好；

FF和BF的近似比都是1.7；

0-1背包问题¶

基础的2-近似算法¶

在贪心算法中，如果是解决分数背包问题，那么可以使用贪心算法，是让背包的每一单位重量的价值最大化；但是如果是整数的0-1背包问题，那么有以下反例：

有两个物品，第一个物品的价值为 1，重量为 1，第二个物品的价值为 2，重量为 3，背包的容量为 3。我们的贪心策略是让每单位重量的价值最大化，因此贪心算法的选择结果是选择第一个物品，但实际上最优解显然是选择第二个物品，这样背包的价值为 2，而贪心算法的解为 1。因此贪心算法并不是最优的。

为了得到近似比，我们需要进一步改进我们的贪心算法：我们有两个贪心策略，其一是根据这里的单位重量的价值（profit density），其二是直接贪心选择最大价值的物品，我们运行两个算法选择最优解，我们可以证明，这样结合后的近似比为 2

设

$P_{frac}$ 为分数背包问题的最优解；
$P_{OPT}$ 为0-1背包问题的最优解；
$P_{greedy}$ 为贪心算法的解；
$p_{max}$ 为装得下的物品中价值最大的物品的价值；

那么有

\[ P_{frac} \geqslant P_{OPT} \geqslant P_{greedy} \geqslant p_{max} \]

所以

\[ \dfrac{P_{OPT}}{P_{greedy}} \leqslant \dfrac{P_{frac}}{P_{greedy}} \leqslant \dfrac{P_{greedy}+p_{max}}{P_{greedy}} \leqslant 2 \]

其中的$P_{frac} \leqslant P_{greedy}+p_{max}$是因为按照贪心策略，我们选择了最大的物品，在即将满的时候，$P_{frac}$在$P_{greedy}$的基础上将$p_{max}$的截取了一部分装进去了；

Summary

如果已知最优解中价值最大的前k个，那么可以设计出近似比为$\dfrac{k+1}{k}$的算法

0-1背包的FPTAS算法¶

现在我们讨论一个更美好的算法，即一个可以无限近似的算法。利用动态规划一讲的算法我们知道 0-1背包问题是有伪多项式算法的，即其复杂度是 $O(nC)$ 的，其中 $n$ 是物品的数量，$C$ 是背包的容量。但我们可以换个角度进行动态规划，我们的数组第二个维度不再是背包的容量，而是价值，即我们原先的数组是 A[i][c]表达的是前 i 个物品放入容量为 c 的背包的最大价值，现在我们的数组是 A[i][v] 表达的是前 i 个物品放入价值为 v 的背包的最小重量。转移方程为：

Note

Let $ W_{i,p} $ be the minimum weight of a collection from $\{1, \ldots, i\}$ with total profit being exactly $ p $.

Take $ i $:

\[ W_{i,p} = w_i + W_{i-1,p - p_i} \]

Skip $ i $:

\[ W_{i,p} = W_{i-1,p} \]

\[ W_{i,p} = \begin{cases} \infty & \text{if } i = 0 \\ W_{i-1,p} & \text{if } p_i > p \\ \min \{ W_{i-1,p}, w_i + W_{i-1,p - p_i} \} & \text{otherwise} \end{cases} \]

显然，这一动态规划的复杂度是 $O(nV)$ 的，其中 $V$ 是所有物品的价值之和。我们做个简单的变换，设 $vmax$ 是所有物品的价值的最大值，那么显然有 $V \leqslant nvmax$因此我们的复杂度是 $O(n^2 vmax)$ 的。

如果发现 $vmax$ 的大小是 $n$ 的多项式级别的，那么我们将得到一个多项式时间的算法。然而并非所有实例都能满足这一条件，因此我们需要对输入的价值做一些技术性的处理，即对输入的所有价值做同比例的缩小，使得 $vmax$ 能缩小到 $n$ 的多项式级别

Key-point

给定想要的比例$\varepsilon$,取$b=\dfrac{\varepsilon v_{max}}{n}$ 将输入的全体价值同时缩放一个比例$b$,使得最大价值为$n$的多项式级别，做向上(或者向下)取整，然后使用动态规划做法，得到最优解$v$;最后再将结果放大回来，我们相信放大回来的价值和原价值是接近的，即$bv$是一个近似解。

可以证明上述算法是 0-1 背包的一个FPTAS算法

首先时间复杂度是显然的，我们缩小价值后的的动态规划算法是

\[ b=\dfrac{\varepsilon v_{max}}{n} \]

\[ O(n^2 \cdot \dfrac{v_{max}}{b})=O(n^2 \cdot \dfrac{n}{\varepsilon})=O(\dfrac{n^3}{\varepsilon}) \]

满足多项式时间的要求；

我们用多项式算法解决了$v_i'$价值下的问题：

我们还需要关注经过缩放再放大之后，原本价值的变化是怎么样的即 $v_i' = \lceil v_i / b \rceil b$ 和 $v_i$ 是接近的。事实上因为在向上取整时最多只会加上 1，因此我们有：

\[ v_i \leqslant v_i' \leqslant v_i + b. \]

设对于 $v_1, \ldots, v_n$ 而言的最优物品集合为 $S^*$，而对于 $v_1', \ldots, v_n'$ 而言的最优物品集合为 $S$，那么我们有：

\[ \sum_{i \in S} v_i' \geqslant \sum_{i \in S^*} v_i'. \]

这是因为 $S$ 是 $v_1', \ldots, v_n'$ 的最优解，而 $S^*$ 是一个可行解。然后结合上述含入的不等式我们有如下等式链：

\[ \sum_{i \in S^*} v_i \leqslant \sum_{i \in S^*} v_i' \leqslant \sum_{i \in S} (v_i + b) \leqslant \sum_{i \in S} v_i + nb = \sum_{i \in S} v_i + \varepsilon v_{\max} \]

比较首尾，只要能估计出 $v_{\max}$ 和 $\sum_{i \in S} v_i$ 的关系，我们就能得到近似化的上界。显然$v_{max} \leqslant \sum_{i \in S^*} v_i $

\[ (1 - \varepsilon) \sum_{i \in S^*} v_i = (1 - \varepsilon) OPT \leqslant \sum_{i \in S} v_i。 \]

因此我们的近似化满足 FPTAS 的要求。

K-Center问题¶

Greedy-KCenter问题的的解不大于最优解的两倍，即

\[ A(I) \leqslant 2 \cdot OPT(I) \]

证明：如果该算法的K个中心刚好在最优解的圆里面，证毕；如果不在，那么其至少有两个在同一个最优解的圆里面，由于每次选的都是最远的，所以这两个点(u,v)的距离大于其解。

\[ 2OPT(I) \geqslant d(u,v) \geqslant A(I) \]

也证毕。