有很多现实世界的问题被证明是NP -hard的。如果我们假设P ≠ NP，那么这些问题就没有多项式时间算法。
如果你必须解决其中一个问题，是否有希望能够有效地解决？还是你只是运气不佳？
1个回答
97
如果一个问题是NP-hard，根据假设P≠NP，那么就没有一种算法可以同时满足以下三个条件：
作为另一个例子，0/1背包问题被认为是NP-难的。在这个问题中，你有一个袋子和一堆不同重量和价值的物品。目标是将最大价值的物品装入袋子中，而不超过袋子的重量限制。即使在最坏情况下计算出精确答案需要指数时间，但可以在多项式时间内近似计算正确答案的任意精度。（执行此操作的算法称为完全多项式时间近似方案或FPTAS）。
很遗憾，对于某些NP-难问题，我们有一些理论上的近似限制。早先提到的Christofides算法可以在边满足三角不等式的情况下给出3/2的TSP近似解，但有趣的是，如果P ≠ NP，则不存在多项式时间的TSP近似算法，可以接近最优解的任何常数因子。通常需要进行一些研究，才能了解哪些问题可以很好地近似，哪些问题不能，因为许多NP-难问题可以很好地近似，而许多其他问题则不能。似乎没有统一的主题。
第二种选择：启发式算法。
在许多NP难问题中，像贪心算法这样的标准方法并不总是能够产生正确答案，但在“合理”的输入上通常会表现得很好。在许多情况下，攻击NP难问题需要使用启发式方法。启发式方法的精确定义因情境而异，但通常启发式方法是一种解决问题的方法，它“经常”以牺牲偶尔可能给出错误答案为代价获得良好答案，或者是一种实用的经验法则，即使可能并不总是以正确的方式指导搜索，也有助于加速搜索。
作为第一类启发式的例子，让我们看看图着色问题。这个 NP -难问题要求在给定图中找到涂色节点所需的最小颜色数，使得没有边的端点是相同的颜色。这被证明是一个特别棘手的问题，用许多其他方法都很难解决（已知的最佳逼近算法具有可怕的界限，不被认为具有参数化高效算法）。然而，有许多对于图的着色启发式算法在实践中表现得非常好。许多贪婪着色启发式算法存在于对节点进行合理排序并分配颜色的过程中，这些启发式算法通常在实践中表现得非常好。不幸的是，有时这些启发式算法返回糟糕的答案，但只要图不是病态构造的，这些启发式算法通常工作得很好。
作为第二种启发式的例子，看一下SAT求解器是很有帮助的。SAT，布尔可满足性问题，是第一个被证明是NP-难的问题。该问题要求，给定一个命题公式（通常写成合取范式），确定是否有一种方法可以为变量分配值，使得整个公式求值为true。现代SAT求解器通过使用启发式来指导其搜索可能的变量赋值，在许多情况下都能很好地解决SAT问题。一个著名的SAT求解算法DPLL，基本上尝试所有可能的分配，以确定公式是否可满足，并使用启发式来加速搜索。例如，如果它发现一个变量始终为true或始终为false，DPLL将在尝试其他变量之前尝试将该变量分配为强制值。DPLL还会找到单元子句（只有一个文字的子句）并设置这些变量的值，然后再尝试其他变量。这些启发式的净效应是，尽管已知具有指数最坏情况行为，但DPLL在实践中非常快。
该算法被称为伪多项式时间算法，因为运行时O(nN)“看起来”像一个多项式，但严格来说，它是指数级的输入大小。许多NP-难问题，特别是涉及数字值的问题，都有伪多项式时间算法，因此只要数字值不太大，就很容易解决。
这两种算法都是参数化算法的例子，用于解决 NP难问题，将问题的难度分为两个部分 - 一个“困难”部分取决于问题的某个输入参数，以及一个“简单”部分，随着输入大小的增加而逐渐扩展。当所涉及的参数较小时，这些算法可用于查找 NP 难问题的精确解。例如上面提到的着色算法在计算生物学中被证明非常有用。
如果你需要解决一个NP难问题，但是你知道输入的规模相对较小——比如说在50到70之间，那么标准的指数时间算法可能无法快速解决这些问题。如果你确实需要问题的精确解，并且其他方法都不能胜任，那该怎么办呢？
在某些情况下，对于NP难问题，存在“优化”的指数时间算法。这些算法的运行时间是指数级别的，但不像朴素解法那样糟糕。例如，对于3着色问题（给定一个图形，确定是否可以为节点着色为三种颜色之一，以使没有边缘的端点具有相同的颜色），一个简单的指数时间算法可能会检查图中每个节点着色的每种可能方式，测试它们是否是3-着色。这样做有3n种可能的方法，所以在最坏情况下，该算法的运行时间将是O(3n·poly(n))，其中poly(n)是某个小的多项式。然而，使用更聪明的技巧和技术，可以开发出一个运行时间为O(1.3289n)的3着色算法。这仍然是一个指数时间算法，但速度比较快。例如，319大约是109，因此，如果计算机每秒可以执行十亿次操作，它可以使用我们最初的暴力算法来（粗略地说）在一秒钟内解决最多有19个节点的图形的3着色问题。使用O((1.3289n)时间指数算法，我们可以在大约一秒钟内解决多达73个节点的实例。这是一个巨大的改进 - 我们已经将每秒处理的大小增加了三倍以上！
作为另一个著名的例子，考虑旅行商问题。TSP有一个明显的O(n! · poly(n))时间解决方案，通过枚举所有节点的排列并测试由这些排列导致的路径来工作。然而，通过使用类似于颜色编码算法所使用的动态规划算法，可以将运行时间提高到“仅”O(n2 2n)。考虑到13！大约是十亿，朴素的解决方案让您在大约一秒钟内解决13个节点图的TSP问题。相比之下，DP解决方案让您在大约一秒钟内解决28个节点图的TSP问题。
这些快速指数时间算法通常用于提高实际可精确解决的输入大小。当然，它们仍然以指数时间运行，因此这些方法通常不适用于解决非常大的问题实例。
第七种选择：解决一个简单特殊情况
许多在一般情况下是NP-难的问题，有些特殊情况下可以有效地解决。例如，虽然通常很难确定一个图是否有k着色，但在k=2的特殊情况下，这等价于检查一个图是否为二分图，可以使用修改后的深度优先搜索在线性时间内完成。布尔可满足性一般来说是NP-难的，但如果您有一个每个子句中最多只有两个文字的输入公式，或者该公式是使用XOR而不是包含OR的子句形成的，则可以在多项式时间内解决。在图中找到最大独立集通常是NP-难的，但如果图是二分图，则由于König定理，可以有效地完成。
因此，如果你发现自己需要解决一些看起来最初可能是 NP -难问题，首先检查一下实际上需要解决该问题的输入是否具有某些额外的受限结构。 如果是这样，你可能能够找到一个适用于你特定情况的算法，并且比完全通用问题的求解器运行得快得多。
- 确定性,
- 在所有输入上都完全正确，
- 在所有可能的输入上都高效。
如果你绝对需要以上所有保证，那么很遗憾，你几乎没戏了。然而，如果你愿意接受放宽其中一些限制的问题解决方案，那么还有希望！以下是一些可考虑的选项。
选项一：逼近算法
如果一个问题是NP-hard并且P ≠ NP，那么就没有一种算法可以始终有效地产生完全正确的答案。但是，如果你不需要精确答案，只需要接近正确的答案怎么办？有些情况下，你可以使用逼近算法来对抗NP-难度。
例如，一个典型的NP-难问题是旅行商问题。在这个问题中，输入是表示交通网络的完全图。图中的每条边都有一个相关的权重。目标是找到一条穿过图中每个节点恰好一次且总权重最小的循环。如果边权满足三角不等式（也就是说，从点A到点B的最佳路线总是沿着A到B的直接链接走），那么可以使用Christofides算法得到成本至少为最优解的3/2的循环。作为另一个例子，0/1背包问题被认为是NP-难的。在这个问题中，你有一个袋子和一堆不同重量和价值的物品。目标是将最大价值的物品装入袋子中，而不超过袋子的重量限制。即使在最坏情况下计算出精确答案需要指数时间，但可以在多项式时间内近似计算正确答案的任意精度。（执行此操作的算法称为完全多项式时间近似方案或FPTAS）。
很遗憾，对于某些NP-难问题，我们有一些理论上的近似限制。早先提到的Christofides算法可以在边满足三角不等式的情况下给出3/2的TSP近似解，但有趣的是，如果P ≠ NP，则不存在多项式时间的TSP近似算法，可以接近最优解的任何常数因子。通常需要进行一些研究，才能了解哪些问题可以很好地近似，哪些问题不能，因为许多NP-难问题可以很好地近似，而许多其他问题则不能。似乎没有统一的主题。
第二种选择：启发式算法。
在许多NP难问题中，像贪心算法这样的标准方法并不总是能够产生正确答案，但在“合理”的输入上通常会表现得很好。在许多情况下，攻击NP难问题需要使用启发式方法。启发式方法的精确定义因情境而异，但通常启发式方法是一种解决问题的方法，它“经常”以牺牲偶尔可能给出错误答案为代价获得良好答案，或者是一种实用的经验法则，即使可能并不总是以正确的方式指导搜索，也有助于加速搜索。
作为第一类启发式的例子，让我们看看图着色问题。这个 NP -难问题要求在给定图中找到涂色节点所需的最小颜色数，使得没有边的端点是相同的颜色。这被证明是一个特别棘手的问题，用许多其他方法都很难解决（已知的最佳逼近算法具有可怕的界限，不被认为具有参数化高效算法）。然而，有许多对于图的着色启发式算法在实践中表现得非常好。许多贪婪着色启发式算法存在于对节点进行合理排序并分配颜色的过程中，这些启发式算法通常在实践中表现得非常好。不幸的是，有时这些启发式算法返回糟糕的答案，但只要图不是病态构造的，这些启发式算法通常工作得很好。
作为第二种启发式的例子，看一下SAT求解器是很有帮助的。SAT，布尔可满足性问题，是第一个被证明是NP-难的问题。该问题要求，给定一个命题公式（通常写成合取范式），确定是否有一种方法可以为变量分配值，使得整个公式求值为true。现代SAT求解器通过使用启发式来指导其搜索可能的变量赋值，在许多情况下都能很好地解决SAT问题。一个著名的SAT求解算法DPLL，基本上尝试所有可能的分配，以确定公式是否可满足，并使用启发式来加速搜索。例如，如果它发现一个变量始终为true或始终为false，DPLL将在尝试其他变量之前尝试将该变量分配为强制值。DPLL还会找到单元子句（只有一个文字的子句）并设置这些变量的值，然后再尝试其他变量。这些启发式的净效应是，尽管已知具有指数最坏情况行为，但DPLL在实践中非常快。
方案三：伪多项式时间算法
如果P ≠ NP，那么没有任何NP难题可以在多项式时间内解决。然而，在某些情况下，“多项式时间”的定义并不一定符合多项式时间的标准直觉。严格来说，多项式时间意味着多项式时间复杂度与指定输入所需的位数成正比，这并不总是与我们认为的输入相同。
作为一个例子，考虑集合划分问题。在这个问题中，你会得到一组数字，并需要确定是否有一种方法将该集合分成两个较小的集合，每个集合的总和相同。这个问题的朴素解法运行时间为O(2n)，并通过暴力测试所有子集来工作。然而，通过动态规划，可以在时间O(nN)内解决此问题，其中n是集合中元素的数量，N是集合中的最大值。严格来说，运行时O(nN)不是多项式时间，因为数字值N仅用log2N位编写，但假设N的数值不太大，这是完全合理的运行时。该算法被称为伪多项式时间算法，因为运行时O(nN)“看起来”像一个多项式，但严格来说，它是指数级的输入大小。许多NP-难问题，特别是涉及数字值的问题，都有伪多项式时间算法，因此只要数字值不太大，就很容易解决。
要了解伪多项式时间的更多信息，请查看关于伪多项式时间的早期Stack Overflow问题。
选项四：随机算法
如果一个问题是NP-hard问题，且P ≠ NP，那么在最坏情况下用确定性算法来解决该问题是不可能的。但是如果我们允许引入随机性的算法会发生什么呢？如果我们愿意接受一种平均情况下能给出好答案的算法，那么我们通常可以在很短的时间内获得相对较好的NP-hard问题的答案。
作为一个例子，考虑最大割问题。在这个问题中，给定一个无向图，你想找到一种方法将图中的节点分成两个非空组A和B，使得两组之间运行的边的数量最大。这在计算物理学中有一些有趣的应用（不幸的是，我完全不理解它们，但你可以浏览这篇论文了解一些细节）。这个问题被认为是NP-难的，但是有一个简单的随机近似算法。如果你只是随机地将每个节点完全投入到两个组中的一个中，那么你会得到一个期望上接近最优解50%的割。回到SAT问题，许多现代SAT求解器使用一定程度的随机性来指导寻找满足分配。例如，WalkSAT和GSAT算法通过选择当前未满足的随机子句，并尝试通过翻转某些变量的真值来满足它。这通常会引导搜索朝着满意的分配方向，使得这些算法在实践中表现良好。
事实证明，使用随机化算法解决NP-难问题存在许多开放的理论问题。如果你感兴趣，请查看复杂度类别BPP以及与NP的关系的开放问题。
选项五：参数化算法
一些NP难题接受多个不同的输入。例如，长路径问题将图形和长度k作为输入，然后询问图形中是否存在长度为k的简单路径。子集和问题将数字集合和目标数字k作为输入，然后询问是否存在数字子集总和恰好为k。
有趣的是，在长路径问题中，有一个算法（color-coding algorithm），其运行时间为O((n3 log n) · bk)，其中n为节点数，k为所请求路径的长度，b为某个常数。该运行时间在k方面呈指数级增长，但在节点数n方面仅呈多项式级增长。这意味着，如果k是固定且预先已知的，则算法作为节点数的函数的运行时间仅为O(n3 log n)，这是一个相当不错的多项式。同样，在子集和问题中，有一个动态规划算法，其运行时间为O(nW)，其中n为集合元素数量，W为这些元素的最大权重。如果W预先固定为某个常数，则该算法将在O(n)时间内运行，这意味着可以在线性时间内准确解决子集和问题。这两种算法都是参数化算法的例子，用于解决 NP难问题，将问题的难度分为两个部分 - 一个“困难”部分取决于问题的某个输入参数，以及一个“简单”部分，随着输入大小的增加而逐渐扩展。当所涉及的参数较小时，这些算法可用于查找 NP 难问题的精确解。例如上面提到的着色算法在计算生物学中被证明非常有用。
然而，一些问题被推测没有任何好的参数化算法。例如，图形着色被怀疑没有任何有效的参数化算法。在存在参数化算法的情况下，它们通常非常有效，但您不能依靠它们解决所有问题。
有关参数化算法的更多信息，请查看此前的Stack Overflow问题。
第六种选择：快速指数时间算法
指数时间算法不具有良好的可扩展性——对于仅有100或200个元素的输入，它们的运行时间就会接近宇宙的寿命。如果你需要解决一个NP难问题，但是你知道输入的规模相对较小——比如说在50到70之间，那么标准的指数时间算法可能无法快速解决这些问题。如果你确实需要问题的精确解，并且其他方法都不能胜任，那该怎么办呢？
在某些情况下，对于NP难问题，存在“优化”的指数时间算法。这些算法的运行时间是指数级别的，但不像朴素解法那样糟糕。例如，对于3着色问题（给定一个图形，确定是否可以为节点着色为三种颜色之一，以使没有边缘的端点具有相同的颜色），一个简单的指数时间算法可能会检查图中每个节点着色的每种可能方式，测试它们是否是3-着色。这样做有3n种可能的方法，所以在最坏情况下，该算法的运行时间将是O(3n·poly(n))，其中poly(n)是某个小的多项式。然而，使用更聪明的技巧和技术，可以开发出一个运行时间为O(1.3289n)的3着色算法。这仍然是一个指数时间算法，但速度比较快。例如，319大约是109，因此，如果计算机每秒可以执行十亿次操作，它可以使用我们最初的暴力算法来（粗略地说）在一秒钟内解决最多有19个节点的图形的3着色问题。使用O((1.3289n)时间指数算法，我们可以在大约一秒钟内解决多达73个节点的实例。这是一个巨大的改进 - 我们已经将每秒处理的大小增加了三倍以上！
作为另一个著名的例子，考虑旅行商问题。TSP有一个明显的O(n! · poly(n))时间解决方案，通过枚举所有节点的排列并测试由这些排列导致的路径来工作。然而，通过使用类似于颜色编码算法所使用的动态规划算法，可以将运行时间提高到“仅”O(n2 2n)。考虑到13！大约是十亿，朴素的解决方案让您在大约一秒钟内解决13个节点图的TSP问题。相比之下，DP解决方案让您在大约一秒钟内解决28个节点图的TSP问题。
这些快速指数时间算法通常用于提高实际可精确解决的输入大小。当然，它们仍然以指数时间运行，因此这些方法通常不适用于解决非常大的问题实例。
第七种选择：解决一个简单特殊情况
许多在一般情况下是NP-难的问题，有些特殊情况下可以有效地解决。例如，虽然通常很难确定一个图是否有k着色，但在k=2的特殊情况下，这等价于检查一个图是否为二分图，可以使用修改后的深度优先搜索在线性时间内完成。布尔可满足性一般来说是NP-难的，但如果您有一个每个子句中最多只有两个文字的输入公式，或者该公式是使用XOR而不是包含OR的子句形成的，则可以在多项式时间内解决。在图中找到最大独立集通常是NP-难的，但如果图是二分图，则由于König定理，可以有效地完成。
因此，如果你发现自己需要解决一些看起来最初可能是 NP -难问题，首先检查一下实际上需要解决该问题的输入是否具有某些额外的受限结构。 如果是这样，你可能能够找到一个适用于你特定情况的算法，并且比完全通用问题的求解器运行得快得多。
结论
如果你需要解决一个 NP -难问题，请不要绝望！ 有许多伟大的选择可供选择，这可能会使你的棘手问题更容易处理。 上述技术中没有一种适用于所有情况，但通过使用这些方法的某些组合，即使面对 NP -难度，通常也可以取得进展。- templatetypedef
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接