Chapter11 Approximation 近似算法

11.1 基本概念

对于一些HARD问题，无法在多项式时间内得到精确的最优解，因此使用能用多项式时间求解的近似算法得到近似解。

近似比（Approximation Ratio）

设精确最优解为$C^*$，近似最优解为$C$，若存在常数$\rho$，使得

$$\max(\frac{C}{C^*},\frac{C^*}{C})\leqslant \rho$$

则$\rho$即为近似比，取值范围为$(1,+\infty)$。

Note

有时候近似比也和输入规模$N$有关，一般规模$N$越大，近似比$\rho(N)$越大，因为求解更加困难，与最优解的差距越大。

近似模式（Approximation Scheme）

除了必要的输入以外，还需要输入一个正值$\varepsilon$，使得近似比恒为$1+\varepsilon$，此时算法的时间复杂度与$n$和$\varepsilon$都有关。

多项式时间近似方案（PTAS）：对于每一个固定的$\varepsilon>0$和任意的实例，都有近似比为$1+\varepsilon$，算法的运行时间为$n$的多项式
完全多项式时间近似方案（FPTAS）：在PTAS的基础上，进一步要求算法的运行时间为$n$和$\frac{1}{\varepsilon}$的多项式

11.2 装箱问题（Bin Packing）

问题描述：

给定$N$个物体，体积依次为$S_1,S_2,···,S_N\in(0,1]$，箱子容积为1，至少需要多少个箱子放物体？（NPC问题）

近似算法1：Next Fit

假设要放入第$k$个物体时，已经有$m$个箱子，那么检查第$m$个箱子是否还能放下这个物体。如果可以，则放入；如果不行，则增加第$m+1$个箱子。

若$M$为问题的精确最优解，则Next Fit算法得到的近似最优解不超过$2M-1$。

Proof

若近似最优解为$2M$（或$2M+1$）
设$S(B_i)$为第$i$个箱子里放置的物体总体积，则：
$S(B_1)+S(B_2)>1$
$S(B_3)+S(B_4)>1$
···
$S(B_{2M-1})+S(B_{2M})>1$
累加可得：
$\sum\limits_{i=1}^{2M}S(B_i)>M$
即所有物体的体积总和必然超过$M$
而对应的，箱子的总数也必然超过$M$，至少为$M+1$,证毕。

近似算法2：First Fit

假设要放入第$k$个物体时，已经有$m$个箱子，那么从第一个箱子开始检查，直到找到一个可以放下这个物体的箱子，把物体放进去；若当前所有箱子都无法放下，则增加第$m+1$个箱子。

若$M$为问题的精确最优解，则First Fit算法得到的近似最优解不超过$1.7M$。

近似算法3：Best Fit

假设要放入第$k$个物体时，已经有$m$个箱子，那么从第一个箱子开始检查所有箱子，找到其中能放下这个物体的且放下后最满的箱子，把物体放进去；若当前所有箱子都无法放下，则增加第$m+1$个箱子。

若$M$为问题的精确最优解，则Best Fit算法得到的近似最优解不超过$1.7M$。

以上三种近似算法都是在线算法。

在线算法（On-line Algorithm）： 每来一个输入就确定下来，无法回溯更改
离线算法（Off-line Algorithm）： 全局观察，得到分析所有输入后再进行决策

11.3 背包问题（Knapsack problem）

可切分版本：

假设有一个限重为$M$的背包，有$N$个物体，第$i$个物体的重量为$w_i$，价值为$p_i$，$x_i$为将第$i$个物体放入背包的比例（如0.5表示将第$i$个物体切一半放如背包，0.3表示将第$i$个物体切30%放入背包），相应的该物体的重量和价值也要乘上对应的比例，怎样能在不超过背包限重的情况下放入最多价值的物体？

该问题是NP问题，解决方法是贪心算法算性价比（$p_i/w_i$），越大的物体越先被放入背包，直到最后要放的物体被切分。

不可切分版本：

此时若所有物体的比例要么为0要么为1，即要么放入要么不放入，则最多价值为多少？

该问题是NPC问题。常见的思路是价值优先贪心算法、重量优先贪心算法、性价比优先贪心算法各自求出一个近似最优解，然后在三个解中取最优解。

如果使用上述的贪心算法，那么得到的近似比约为2。

Proof

记$P_{opt}$为不可切分版本的理论最优解；
$P_{greedy}$为不可切分版本的近似最优解；
$P_{frac}$为可切分版本的最优解；
$p_{max}$为所有物体里最大的价值。
则$P_{opt}\leqslant P_{frac}\leqslant P_{greedy}+p_{max}$
其中，第一个$\leqslant$是因为不可切分版本的最优解肯定不会比可切分版本的最优解好；第二个$\leqslant$是因为可切分版本的最优解最多只有一个物体被切分，这个被切分的物体是被放入背包且价值最小的物体，可以把这个物体的切块部分放缩替换为完整且价值最高的物体。
$\frac{P_{opt}}{P_{greedy}}\leqslant 1+\frac{p_{max}}{P_{greedy}}\leqslant 2$，证毕。

动态规划思路：

设状态函数$F[N][M]$表示在给定前$N$个物体，且放好物体后背包剩余限重为$M$的最优解。

状态转移方程：

$$F[N][M]=\max{F[N-1][M+w_N]+p_N,F[N-1][M]}$$

其中前一个为放入第$N$个物体，后面为不放第$N$个物体。

数据处理：

当$p_{max}$较大时，可考虑同时缩小一定比例，之后再放大，便于节约存储空间和加快算法速度，但是由于存在舍入问题，因此只能得到近似解。

11.4 K中心问题（K-center Problem）

问题描述：

给定平面上的若干个点，以及$K$，在平面上找$K$个点作为圆心，求最短半径，使得以这$K$个点为圆心的$K$个圆能覆盖所有点。（NPC问题）

近似思路：

若我们已知取精确最优解时$K$个圆心的位置，对应$K$个半径为$r$的圆，那么我们想到一种近似算法，让这$K$个圆心都取在待覆盖点上，那么这个近似算法至少能得到$2r$的近似最优解，因为我们可以在原本$K$个半径为$r$的圆中各自取一个待覆盖点作为新的圆心，这个点到圆内其他待覆盖点的距离最多为$2r$。

简而言之，若已知精确最优解为$r$，则一定可以找到一个取圆心取在待覆盖点上的方法，使得得到的近似最优解不会超过$2r$（近似比为2）。

伪代码：

Centers Greedy-2r(待覆盖点集S[],int n,int K,double r)
{
    定义空的圆心集C;
    while(S'非空)
    {
        从点集S中随机挑选一个点放入圆心集C;
        将以该点为圆心，半径为2r的圆内的所有点从S'删除；
    }
    if(圆心集C中的元素≤K)return C;
    else ERROR;
}

如果选出了超过$K$个圆心，则说明精确最优解大于$r$。

然而，实际问题是：我们并不知道精确最优解$r$，因此我们可以考虑二分，即一开始代码的输入$r$非常的大，然后依次二分，直到跑出来的中心数大于$K$为止，说明上一次的半径输入已经最靠近精确最优解了。

Far Away算法：

除了选择第一个圆心，其它圆心的选择不再随机，而是从剩余待覆盖点中选择与上一圆心距离最远的待覆盖点做为圆心。Far Away算法的近似比依然为2。