近似算法¶
对于 NP 完全问题，我们通常无法找到一个多项式时间的算法来解决它。但是，我们可以找到一个近似算法，它可以在多项式时间内给出一个接近最优解的解。近似算法常用于优化问题，它们通常会牺牲最优解的精确性，以换取更快的运行时间。
设 \(C\) 为最优解，\(C^*\) 为近似解，我们定义近似比 \(\rho(n)\) 为：
如果一个近似算法的近似比为 \(\rho(n)\)，则称该算法是一个 \(\rho(n)\)-approximation algorithm。
一个近似模式是这样一种近似算法，它不仅接受问题的实例作为输入，还接受一个 \(\epsilon > 0\) 的值，使得对于任意固定的 \(\epsilon\)，该模式是一个 \((1 + \epsilon)\)-approximation 算法。
如果对于任意固定的 \(\epsilon > 0\)，该模式的运行时间都是输入规模 \(n\) 的多项式时间，则称该模式是一个多项式时间近似模式 (Polynomial-Time Approximation Scheme, PTAS)，例如 \(O(n^{2/\epsilon})\) 和 \(O((1/\epsilon)^2 n^3)\)，其中后者是完全多项式时间近似模式 (Fully Polynomial-Time Approximation Scheme, FPTAS)。
装箱问题¶
给定 \(N\) 个物品，它们的体积依次为 \(S_1, \cdots, S_n, 0 < S_i \le 1\)，我们希望将它们装入尽可能少的箱子中，每个箱子的容量为 \(1\)。
这是一个 NP 完全问题，可以通过以下近似算法来求解。
Next Fit: 对每个物品，如果它可以放入当前箱子，则放入；否则，新开一个箱子。如果最优解为 \(M\)，则该算法的解最多为 \(2M - 1\)，证明如下：
若 Next Fit 算法产生了 \(2M\) 或 \(2M+1\) 个箱子，则设这些箱子的装量为 \(S(B_1), \cdots, S(B_{2M})\)，然后显然有 \(S(B_1) + S(B_2) > 1\), \(S(B_3) + S(B_4) > 1\), \(\cdots\), \(S(B_{2M-1}) + S(B_{2M}) > 1\)，因此 \(\sum_{i=1}^{2M} S(B_i) > M\)，因此最优解至少产生 \(M+1\) 个箱子。
First Fit: 对每个物品，将其放入第一个可以放入的箱子中。该算法的近似比为 \(1.7\)，可以实现 \(O(N \log N)\) 的时间复杂度。
Best Fit: 对每个物品，将其放入剩余空间最小的箱子中。该算法的近似比为 \(1.7\)，可以实现 \(O(N \log N)\) 的时间复杂度。可以看到，在近似算法中，不一定是越复杂越好，往往不需要考虑边界情况。
以上这些算法都是 On-line 算法，即只能看到当前物品，不能看到后续物品。可以证明所有 On-line 算法的近似比都不小于 \(5/3\)。
Off-line 算法可以看到所有物品，一种简单的 Off-line 算法是先将物品按体积从大到小排序，然后再使用 First/Best Fit 算法。可以证明该算法会产生不多于 \(11M/9 + 6/9\) 个箱子。
背包问题¶
设背包的容量为 \(M\)，现给定 \(N\) 个物品，每个物体有重量 \(w_i\) 和价值 \(p_i\)，可以选择放入物品的一部分，比例为 \(x_i \in [0, 1]\)。我们希望找到一种放置方案，使得放入背包的物品价值最大，即：
对于这个 fractional knapsack 问题，我们可以使用贪心算法来求解，即依次放入性价比最高的物品，直到背包装满。但是如果不能放入物品的一部分，\(x_i\) 只能为 0 或者 1，这个问题就变成了 NP-Hard 问题。
此时，一个可行的近似算法为，每一步都贪婪地选择能装入的性价比最高的物品，直到无法装下为止。可以证明该算法的近似比为 2：设 \(p_{max}\) 为能装入的价值最高的物品的价值，\(P_{opt}\) 为最优解的价值，\(P_{greedy}\) 为该算法的解的价值，首先显然有 \(p_{max} \le P_{greedy}\)，然后因为 \(P_{opt}\) 和 \(P_{greedy}\) 仅有最后一个物品可能不同，因此有 \(P_{opt} \le P_{greedy} + p_{max} \le 2P_{greedy}\)，从而得证。
该问题也可以用动态规划来求解，设 \(f(i, w)\) 代表仅考虑前 \(i\) 个物品，背包容量为 \(w\) 时的最大价值，则状态转移方程为：
该算法的时间复杂度为 \(O(N \cdot N w_{max}) = O(N^2 w_{max})\)，其中 \(w_{max} = 2^l\)，所以该复杂度是一个伪多项式复杂度。
K-center 问题¶
给定 \(n\) 个地点 \(s_1, \cdots, s_n\) 的位置，我们希望输出 \(K\) 个中心 \(c_1, \cdots, c_k\) 的位置，使得所有地点到最近的中心的距离的最大值最小，即最小化
在这个问题中，常规的算法都无法取得很好的效果，因此可以选择使用近似算法，近似方法为只允许中心在给定地点的位置上。
首先考虑这样一种近似算法，它输入中心数目 \(K\) 和半径 \(r\)。在算法中，我们每次随机选择一个地点作为中心，然后以此为圆心，将周围距离在 \(r\) 以内的地点删除，如是循环，直到所有地点都被删除。循环结束以后，如果选出的中心数目小于等于 \(K\)，则返回，继续二分查找更小的 \(r\)；如果选出的中心数目大于 \(K\)，那么可得最优解 \(r(C^*) > r\)，此时必须要扩大 \(r\)。这是因为，在 \(|C| > k\) 而 \(|C^*| = k\) 的情况下，\(C^*\) 中一定存在一个中心，使得 \(C\) 中有两个中心 \(c_1, c_2\) 与它的距离小于 \(r(C^*)\)，根据算法又有 \(\text{dist}(c_1, c_2) > 2r\)，然后由三角不等式可得，\(r(C^*)\) 一定大于 \(r\)。
另一种近似算法是，每次都选出离现有中心集最远的的地点作为新的中心，即选出使得 \(\text{dist}(s, C)\) 最大的地点，直至选出 \(K\) 个中心。该算法不需要输入半径 \(r\)，且可以证明，选出的中心集满足 \(r(C) \le 2r(C^*)\)。