6.20. 应对 NP 完全问题¶

发现你的问题是 NP 完全，可能并不意味着你就可以对它置之不理。无论问题复杂度如何，推销员都需要找到合理的销售路线；箱子需要打包并运输；网络需要构建起来。（事实上，最初正是美国电话系统遇到的问题启发了 NP 完全性理论的发展。）当你面对一个必须解决的 NP 完全问题时，你会怎么做？

有几种技术可以尝试。一种方法是只运行问题的小规模实例。对某些问题来说，这是不可接受的。例如，TRAVELING SALESMAN（推销员问题）的规模增长如此之快，以至于在问题规模超过 30 个城市左右时，现代计算机也无法运行，而在现实生活场景中这并非不合理的规模。不过，NP 中的其他一些问题虽然在理论上需要指数级时间，但其增长仍然足够慢，因而能够解决具有实用规模的问题。

考虑 背包问题（knapsack problem）。 我们有一个 动态规划（dynamic programming） 算法，对于把 \(n\) 个物体装入大小为 \(K\) 的背包，其成本为 \(\Theta(nK)\)。 但事实证明背包问题是 NP 完全的。 这难道不矛盾吗？ 当我们考虑 \(n\) 与 \(K\) 之间的关系时，就不矛盾了。 \(K\) 有多大？ 输入规模通常为 \(O(n \lg K)\)，因为物品的大小取值都小于 \(K\)。 因此，\(\Theta(nK)\) 实际上是输入规模的指数级。

只要所用规模"合理"，我们的背包问题动态规划算法就是可行的。也就是说，当 \(nK\) 在数千量级时，我们可以成功地找到问题的解。这样的算法被称为 伪多项式 时间算法。这与 TRAVELING SALESMAN 不同：在现有算法下，当 \(n = 100\) 时，后者根本不可能求解。

处理 NP 完全问题的第二种方法是求解该问题的某个并不那么困难的特殊实例。例如，图上的许多问题都是 NP 完全的，但在某些受限类型的图上，相同的问题就不那么困难了。例如，VERTEX COVER（顶点覆盖）和 K-CLIQUE 问题在一般情况下是 NP 完全的，但对于二部图（即这样的图：其顶点能被分成两个子集，同一子集中的任意两个顶点之间都没有边）存在多项式时间解法。 2-SATISFIABILITY（其中布尔表达式中的每个子句最多包含两个文字）有一个多项式时间解法。若干几何问题在二维情况下只需多项式时间，但在三维或更高维度下却是 NP 完全的。

一般来说，如果我们要保证为 NP 完全问题得到正确（或最优）的答案， 就潜在可能需要对所有（指数级数量的）可能解进行检验。 不过，经过一些组织安排，我们或许能够快速进行检验，或者在有些情况下避免检验大量的可能答案。 例如， 动态规划（dynamic programming） 试图组织对一个问题所有子问题的处理，使工作得以高效完成。

如果需要对整个 解空间 进行蛮力搜索，我们可以使用 回溯 来访问以 解树 形式组织的所有可能解。例如，SATISFIABILITY（可满足性）有 \(2^n\) 种为待满足布尔表达式中的 \(n\) 个变量赋真值的方式。我们可以把第一个变量设为 TRUE 或 FALSE 的选择看作一棵解树。因此，可以把第一个变量为 TRUE 的所有解放在树的一侧，其余解放在另一侧。然后，我们沿树的某一分支向下检验解，直到某个点我们知道该解不可能是正确的（例如当前的赋值部分已经使表达式不可满足）。此时我们回溯，在树中向上返回一个结点，再沿另一分支向下。如果这也不行，我们就知道需要在树中进一步向上回溯并根据需要沿其他分支继续，直到最终要么找到满足表达式的解，要么穷尽整棵树。在某些情况下，我们会避免处理大量可能的解，或很快找到一个解；在另一些情况下，我们最终可能要访问 \(2^n\) 个可能解中的大部分。

分支限界算法 是回溯的一种扩展，适用于 优化问题，例如 TRAVELING SALESMAN 这种我们试图找到贯穿各城市最短路线的问题。我们像回溯一样遍历解树。不过，我们会记住迄今为止找到的最佳值。沿给定分支下行等价于决定访问城市的顺序。因此，解树中的任何结点都代表到目前为止已访问的城市集合。如果这些距离之和超过了迄今找到的最佳路线，那么我们就知道应该停止追寻树的这一分支。此时我们可以立即回溯并转向另一个分支。如果我们有快速找到一个好的（但不一定是最佳的）解的方法，就可以把它作为初始界值，从而有效地对树的某些部分进行剪枝。

另一种应对策略是求问题的近似解，这种算法称为 近似算法。寻找近似解的方法有很多。一种方法是使用 启发式 来求解问题，也就是基于"经验法则（rule of thumb）"的算法，它并不总是给出最佳答案。例如，TRAVELING SALESMAN 问题可以近似求解，方法是使用这样的启发式：从任意城市出发，然后总是前往最近的下一个未访问城市。这很少给出最短路径，但解可能已经足够好。这个解之所以可能足够好，一个原因是它可能是运行分支限界算法的一个良好起点。对 TRAVELING SALESMAN 问题还有很多其他效果更好的启发式方法。

有些近似算法具有有保证的性能，答案会在最佳可能答案的一定百分比之内。例如，考虑 VERTEX COVER 问题的这个简单启发式：设 \(M\) 为 \(G\) 中的一个极大（未必最大） 匹配。匹配（借助连接边）把顶点配成对，使得每个顶点最多与一个伙伴配对。极大意味着尽可能多地选择配对，按某种顺序选取，直到没有更多可选的配对为止。最大则意味着对于给定图能给出最多配对的匹配。如果 OPT 是最小顶点覆盖的大小，那么 \(|M| \leq 2 \cdot \mbox{OPT}\)，因为每条匹配边至少有一个端点必须在 任意 顶点覆盖中。

关于解有保证界的一个更好的例子，来自求解 BIN PACKING（装箱）问题的简单启发式。

BIN PACKING 的判定形式（即询问这些物品能否装入少于 \(k\) 个箱子）已知是 NP 完全的。求解该问题的一个简单启发式是使用"首次适应（first fit）"的方法。我们把第一个数放入第一个箱子；然后，如果第二个数能放进第一个箱子就放进第一个箱子，否则放入第二个箱子。对之后的每个数，我们只是按照生成顺序依次检查各箱子，把它放入第一个能装下的箱子中。所用箱子数不会超过这些数总和的 2 倍，因为每个箱子（也许除一个之外）都必须至少装到一半满。不过，这种"首次适应"启发式给出的结果可能远差于最优解。考虑下面这组数：六个 \(1/7 + \epsilon\)、六个 \(1/3 + \epsilon\) 和六个 \(1/2 + \epsilon\)，其中 \(\epsilon\) 是一个小的正数。如果组织得当，只需六个箱子。但如果做得不好，我们最终可能需要把数放进 10 个箱子。

更好的启发式是使用递减首次适应（decreasing first fit）。 它与首次适应基本相同，区别在于我们不断按从最满到最空的顺序对箱子排序。 这样，在决定把下一项放在哪里时，我们会把它放入能容纳它的最满的箱子里。 这类似于用于 内存管理 的 最佳适应 启发式。 这个启发式不仅仅倾向于比简单首次适应表现更好。 递减首次适应启发式已被证明只需不超过最优箱子数的 11/9。 因此，使用该启发式带来的低效程度是有保证的（不超过约 22%）。

NP 完全性理论提供了一种把易处理问题与（可能）难处理问题区分开来的技术。当面对一个新问题时，我们可能会在检查它是否易处理（也就是尝试寻找多项式时间解法）与检查它是否难处理（也就是尝试证明该问题是 NP 完全的）之间交替进行。虽然证明某个问题是 NP 完全并不会真正让我们的算法上界与问题的下界确定地吻合，但它几乎一样好。一旦我们意识到某个问题是 NP 完全的，那么我们就知道，下一步要么重新定义问题使其更容易，要么使用本节讨论的某种"应对"策略。