近似算法 | ka1的笔记本

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

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)

也证毕。