非详尽的最坏情况 NP 完全求解算法
Non-exhaustive worst-case NP-complete solving algorithm
免责声明：
首先，我知道并非所有的 NP 完全问题都有很大的 'search space' 必须在其中寻找解决方案，但是很多最著名的问题都有，所以我会做出这个假设，因为这个是关于（已知）算法的问题，而不是关于复杂性理论的问题。所以它可能更适用于离散优化问题，但我不会将其限制在这些问题上。
上下文： 我所知道的大多数解决此类 NP 完全问题的算法通常都有一种在搜索中抛出可能解决方案的方法 space 而该算法是 运行 （例如，在这里考虑分支定界）。然而，虽然在平均和最好的情况下，这总是会产生或多或少有效的减少，但在我能想到的所有例子中，有一种方法可以构建一个最坏情况的问题，你必须遍历搜索中的所有点space。如此之多，以至于我的一位同事认为这至少是 NP 完全问题的基本 属性（当然，如果 P = NP 那么整个讨论都是微不足道的）。
问题：我相信必须有一个 NP 完全问题的例子和解决它的算法，你可以总是 找到搜索的缩减 space，即使在 最坏的情况下 一旦你是 运行 算法，即使这可能只会让你得到一个常数与穷举搜索算法相比，最坏情况下的运行时间（或更一般的多项式）减少。当然，我可以想到一些简单的例子，你可以综合扩展搜索 space，但你可以减少搜索 a priori，所以我正在寻找一个真正的算法问题，这意味着您通常只能在算法执行期间减少space。
示例： 我将用一个例子来说明这一切。已知混合整数线性规划是 NP 难的。然而，对用于分支定界松弛的单纯形算法的大量研究通常会让您丢弃大部分搜索 space。一个非常简单的例子是：
max x_1 + ... x_n
w.r.t.
0 <= x_1 <= x_2 <= x_n <= N*Pi
x_2,x_4,x_6,..., x_(floor(n/2)*2) integers
很明显，您总是想要尽可能大的 x_i，因此您可以忽略其余部分。从最初的松弛开始，您会选择最大的 x_n 并忽略所有其余部分。但是，您可以想出它没有的例子：
max v_1 * x_1 + ... + v_n * x_n
w.r.t.
0 <= x_1,x_2, ..., x_n <= 1
w_1 * x_1 + ... + w_n * x_n <= W
x_1, ..., x_n integers
这是一个0-1的背包问题。根据权重、值和分支定界的顺序，您可能必须测试 x_i 的每个组合以找到最大值。
我不确定“非详尽无遗”有一个很好的定义。反正我会尽量回答。
拿problem of finding a maximum clique。我们可以通过布尔向量来参数化搜索 space，指示每个顶点是否属于 clique，从而使 2n 种可能性，none 先验可排除，但每 n -顶点图最多有 3n/3 ≤ 1.5n 个最大派系，甚至像 Bron–Kerbosch 这样相当简单的算法也能实现这一点绑定到多项式的因素。 （维基百科文章描述了指数基数的后续改进。）
另一个例子是Hamiltonian path。有 n!完全图中的不同解决方案，none 先验排他性，但存在一个动态程序来找到具有 运行 时间 2n poly(n) 的解决方案。
另一方面，Strong Exponential Time Hypothesis 是我们不能比 2n 做的更好 n 变量可满足性，这排除了已知算法有更好的最坏情况 运行 时间 。在实践中，启发式非常好，我们使用可满足性作为减少目标，例如，检查组合电路的有效性。就我而言，“NP-hard 意味着穷举搜索是最好的”是一种有害的过度简化。
免责声明： 首先，我知道并非所有的 NP 完全问题都有很大的 'search space' 必须在其中寻找解决方案，但是很多最著名的问题都有，所以我会做出这个假设，因为这个是关于（已知）算法的问题，而不是关于复杂性理论的问题。所以它可能更适用于离散优化问题，但我不会将其限制在这些问题上。
上下文： 我所知道的大多数解决此类 NP 完全问题的算法通常都有一种在搜索中抛出可能解决方案的方法 space 而该算法是 运行 （例如，在这里考虑分支定界）。然而，虽然在平均和最好的情况下，这总是会产生或多或少有效的减少，但在我能想到的所有例子中，有一种方法可以构建一个最坏情况的问题，你必须遍历搜索中的所有点space。如此之多，以至于我的一位同事认为这至少是 NP 完全问题的基本 属性（当然，如果 P = NP 那么整个讨论都是微不足道的）。
问题：我相信必须有一个 NP 完全问题的例子和解决它的算法，你可以总是 找到搜索的缩减 space，即使在 最坏的情况下 一旦你是 运行 算法，即使这可能只会让你得到一个常数与穷举搜索算法相比，最坏情况下的运行时间（或更一般的多项式）减少。当然，我可以想到一些简单的例子，你可以综合扩展搜索 space，但你可以减少搜索 a priori，所以我正在寻找一个真正的算法问题，这意味着您通常只能在算法执行期间减少space。
示例： 我将用一个例子来说明这一切。已知混合整数线性规划是 NP 难的。然而，对用于分支定界松弛的单纯形算法的大量研究通常会让您丢弃大部分搜索 space。一个非常简单的例子是：
max x_1 + ... x_n
w.r.t.
0 <= x_1 <= x_2 <= x_n <= N*Pi
x_2,x_4,x_6,..., x_(floor(n/2)*2) integers
很明显，您总是想要尽可能大的 x_i，因此您可以忽略其余部分。从最初的松弛开始，您会选择最大的 x_n 并忽略所有其余部分。但是，您可以想出它没有的例子：
max v_1 * x_1 + ... + v_n * x_n
w.r.t.
0 <= x_1,x_2, ..., x_n <= 1
w_1 * x_1 + ... + w_n * x_n <= W
x_1, ..., x_n integers
这是一个0-1的背包问题。根据权重、值和分支定界的顺序，您可能必须测试 x_i 的每个组合以找到最大值。
我不确定“非详尽无遗”有一个很好的定义。反正我会尽量回答。
拿problem of finding a maximum clique。我们可以通过布尔向量来参数化搜索 space，指示每个顶点是否属于 clique，从而使 2n 种可能性，none 先验可排除，但每 n -顶点图最多有 3n/3 ≤ 1.5n 个最大派系，甚至像 Bron–Kerbosch 这样相当简单的算法也能实现这一点绑定到多项式的因素。 （维基百科文章描述了指数基数的后续改进。）
另一个例子是Hamiltonian path。有 n!完全图中的不同解决方案，none 先验排他性，但存在一个动态程序来找到具有 运行 时间 2n poly(n) 的解决方案。
另一方面，Strong Exponential Time Hypothesis 是我们不能比 2n 做的更好 n 变量可满足性，这排除了已知算法有更好的最坏情况 运行 时间 。在实践中，启发式非常好，我们使用可满足性作为减少目标，例如，检查组合电路的有效性。就我而言，“NP-hard 意味着穷举搜索是最好的”是一种有害的过度简化。