近似算法¶
- PTAS：Poly-Time Approx Scheme，多项式时间近似算法。
- EPTAS：在 PTAS 的基础上，要求 A 的复杂度是 \(O(|I|^c)f(1/\epsilon)\)，即 A 的运行时间和问题规模 \(|I|\) 呈简单的多项式关系，与近似比无关。
- FPTAS：要求 A 的运行时间关于 \(|I|\) 还有 \(1/\epsilon\) 都呈多项式关系，即复杂度为 \(|I|^{O(1)} (1/\epsilon)^{O(1)}\).
装箱问题¶
- NextFit: 第二个能够和第一个装进箱子就装，否则开一个新的
-
假设 \(M\) 是最优解，NextFit 最多用 \(2M - 1\) 个箱子
-
FirstFit: 查找之前所有装过东西的箱子，装到第一个能装进去的，没有就开一个新的
-
假设 \(M\) 是最优解，FirstFit 最多用 \(\dfrac{17M}{10}\) 个箱子，可以构造序列让 FirstFit 使用 \(\dfrac{17(M - 1)}{10}\) 个箱子
-
BestFit: 查找之前所有装过东西的箱子，装到装进去后最满的那个箱子里，没有就开一个新的
- 时间复杂度 \(T(N) = O(N \log N)\)
-
假设 \(M\) 是最优解，BestFit 最多用 \(\dfrac{17M}{10}\) 个箱子
-
不存在近似比优于 \(\dfrac{3}{2}\) 的算法：
使用反证法，如果存在近似比小于 \(\dfrac{3}{2}\) 的算法，那么可以用这个算法 \(A\) 来解决 NPC 的判断物品是否可以由两个箱子装下的问题。
如果物品可以由两个箱子装下，那么 \(\text{OPT} = 2\)，则 \(A(I) < \dfrac{3}{2} \cdot 2 = 3\)，即 \(A(I) < 3\)；此时 \(A(I) = 2\)，那么 \(A\) 可以判断；
如果物品不可以由两个箱子装下，那么 \(\text{OPT} \geq 3\)，则 \(A(I) \geq 3\)；但是由于近似比小于 \(\dfrac{3}{2}\)，所以由 \(A(I)\) 可以判断此时 \(\text{OPT}\) 不可能是 2。此时这个近似算法 \(A\) 就可以判断物品是否可以由两个箱子装下。
综上，我们用多项式算法 \(A\) 来解决 NPC 问题，所以只可能有 \(\text{P} = \text{NP}\)。
背包问题——分数形式¶
- 你可以选择装一个物品的一定比例，而非全部装入，还是求背包内的总价值最大的装法
- 贪心算法，让背包的每一单位重量的价值最大化，第二种是直接贪心选择价值最大的物品，运行两个算法取最优解，可以证明结合比近似为 2
设
- \(P_{\text{frac}}\) 为分数背包问题的最优解；
- \(P_{\text{OPT}}\) 为 0-1 背包问题的最优解；
- \(P_{\text{greedy}}\) 为贪心算法的解；
- \(p_{\text{max}}\) 为装得下的物品中价值最大的物品的价值；
那么有
所以
其中的 \(P_{\text{frac}} \leq P_{\text{greedy}} + p_{\text{max}}\) 是因为按照贪心策略，我们选择了最大的物品，在即将满的时候，\(P_{\text{frac}}\) 在 \(P_{\text{greedy}}\) 的基础上将 \(p_{\text{max}}\) 的一部分装进去。
K-center 问题¶
- 在一个点集中，找 k 个点，使得所有点到这些点的最小距离组成的集合中的最大值最小。
- 如果我们提前知道最优解，那么我们可以有一个 2-近似算法
每次随机选择一个剩余的点作为中心， 2r(C∗) 为半径的圆至少会带走一个真正的最优解中的点为中心，r(C∗) 为半径的圆内所有点，因此 K 步之后必然最优解覆盖的所有点都被我们的算法覆盖，因此必然停止。
那么如果不知道，可不可以得到近似算法呢？
我们首先从输入点集中随机选取一个点作为第一个中心，加入中心点集 C。然后每轮循环在 剩余的点中找到一个点 s 的 dist(s,C) 最大，即 s 是到现有中心最短距离最大的点，将其加入中心点集 C，直到 C 中有 K 个点。
还是一样的道理，我们选完以后，每个选的点张开 2r 的圆，如果还有点没被选到，那么说明这个点距离每个点的距离都 >2r，因为他还没被选，说明被选的 K 个点两两距离也 >2r，矛盾。