11:Approximation
本讲我们将尝试解决 NP-C 问题。之前我们说我们找不到一个多项式时间内针对一个 NP-C 问题的算法，那是因为我们同时要求了解的精度，也就是我们希望这个解是最优的。要是我们允许最终结果与最优解之间有一定的误差，我们或许就能找到一个比较优秀的算法。
那么这些算法我们最关心的变成了它所能得到解的精确程度，越是精确，我们认为这个算法就越好。于是我们定义近似比：
definition
如果一个算法的近似比是 \(\rho(n)\)，那么说明，对于任意规模为 \(n\) 的输入，该算法得到的解为 \(C\)，最优解为 \(C^*\)，有：
换言之，我们得到的解在比例上与最优解相差不超过 \(\rho(n)\) 倍。
那么如果一个算法能够达到近似比 \(\rho(n)\)，我们就称之为 \(\rho(n)-\) 近似算法。
同时我们考虑到有些最优解问题会限制一个 \(\epsilon\)，要求我们得到的解不要超过最优解的 \((1+\epsilon)\) 倍。因此我们定义最优化问题的近似方案为 \((1+\epsilon)-\) 近似的算法。同时，从时间复杂度上，我们可以将它分成如下几类：
- 多项式时间近似方案(polynomial-time approximation scheme, PTAS)：时间复杂度可以被写成 \(O(n^{f(1/\epsilon)})\) 的形式；
- 满多项式时间近似方案(fully polynomial-time approximation scheme, FPTAS)：在 PTAS 基础上，要求与 \(\frac{1}{\epsilon}\) 也是多项式关系。即时间复杂度可以写成 \(O(n^{c_1}(\frac{1}{\epsilon})^{c_2})\)。
同样的，我们依然举几个例子，来深入解析近似算法以及近似比的证明。
Bin Packing¶
问题描述
给出 \(n\) 个物品 \(s_1,s_2,\cdots,s_n\)，每个物品体积满足 \(0<s_i\leq 1\)。若有容量为 \(1\) 的箱子，来装这些物品，则最少需要多少箱子。
这个问题本身是 NP-hard 的，如果我们通过给出 \(K\) 问是否存在一种方式只需用不多于 \(K\) 个箱子，那么它就变成了一个 NP-C 问题，因为我们可以验证一种方式是否只用了不多于 \(K\) 个箱子。想要证明它是 NP-C 的，可以通过 number partition 问题来归约。
proof of NP-C
number partition 问题是说，给定一个集合的数，希望能够将它划分成两个集合使得各个集合的和是相等的。在已知 number partition 是 NP-C 的情况下，我们如何证明 Bin packing 的判定版本也是 NP-C 的呢？对于 number partition 问题的一个实例 \(S=\{a_i\}\)，我们先取 \(A=\sum a_i\)，然后构造实例 \(s_i=\frac{2a_i}{A},K=2\) 作为 Bin packing 问题的实例，若 Bin packing 得到一组解，那么这组解也就对应这 number partition 问题的一个解。因此 \(number pairtition\leq_p Bin packing\)。
顺带一提，number partition 问题有着伪多项式时间的 dp 做法，同时我们也能用启发式算法求出非常优秀的解。因此该问题也被称为“最简单的难题”。
总之这个问题非常困难，于是我们提出了一些近似的算法，我们的任务就是理解这些做法，并求出近似比。
Online Algorithm¶
最直观的做法，当前这个装不下了就装下一个。
近似比可以通过如下结论获得：如果最优情况下需要箱子 \(M\) 个，则该做法需要的箱子不超过 \(2M-1\)，且是上确界。利用反证，假如我们使用了 \(2M\) 个箱子，那么我们知道任意相邻两个箱子所装物品体积之和应当大于 \(1\)，那么将所有箱子内物品加起来应当大于 \(M\)，但是总体积至多为 \(M\)，否则不能在 \(M\) 个箱子里装下，因此至多 \(2M-1\) 个箱子。同时我们可以构造 \(0.5,0.6,0.5\)，该情况需要 \(2\times 2-1\) 个 箱子。
每次放不下时，从前往后找到第一个能放下当前物品的箱子。
该做法是一个 \(1.7-\) 近似的算法，同时，它能够取到 \(\dfrac{17(M-1)}{10}\) 的上界。
这个算法涉及两个问题。第一个是时间复杂度，我们事实上能够做到 \(O(n\log n)\)，因为在取第一个能放下当前物品的箱子时，可以通过平衡树等数据结构来维护，做到 \(O(\log n)\) 的查找。第二个问题是，如果我们从物品中删去一个数，First Fit 做法的结果是不增的吗？其实不一定，考虑 \(\{0.55,0.7,0.55,0.1,0.45,0.15,0.3,0.2\}\)，需要 \(3\) 个箱子，但是去掉 \(0.1\) 后，却需要 \(4\) 个箱子。
每次放不下时，找到能放下当前物品余量最小的箱子。
该做法看似比 First Fit 优秀，实则它仍然是一个 \(1.7-\) 近似的。
可以看到这三种做法的近似比都比较大，我们也容易构造出令这三者都难以得到好的解的情况。事实上，可以构造一种情况使得任何在线的做法都最好只能做到 \(\frac{5}{3}-\) 近似，因此我们转向离线的做法，如果我们提前知道了所有物品，并可以通过合理的规划来求解呢？
Offline Algorithm¶
考虑到体积大的物品更容易浪费空间，于是我们将物品降序排序，然后采取 First Fit 或者 Best Fit（事实上二者相差不大）。如果我们采用 First Fit，在排序后，可以证明所需要箱子不会超过 \(\frac{11}{9}M+\frac{6}{9}\) 个，也就是说，离线的 First Fit 是个 \(1.2-\) 近似的做法，大大优于在线的版本。