问题标签 [np-complete]

当我想出一个似乎是解决它的通用算法时，我正在阅读子集和问题：

“set”是一个不包含重复项的列表，“sum”是搜索子集的总和。“subsets”是一个 cons 单元的列表，其中“car”是一个子集列表，“cdr”是该子集的总和。只需将元素放在前面，就可以在 O(1) 时间内从旧子集创建新子集。

我不确定它的运行时复杂性是多少，但似乎随着每个元素“总和”的增长，“子集”的大小加倍，加一，所以在我看来至少是二次的。

我发布这个是因为我之前的印象是 NP 完全问题往往是棘手的，并且通常可以希望的最好的问题是启发式的，但这似乎是一个通用的解决方案，假设你有 CPU 周期，总是给你正确的答案。像这样可以解决多少其他 NP 完全问题？

我的理解是，拉德纳定理基本上是这样的：

P != NP 意味着存在一个集合 NPI，其中 NPI 不在 P 中并且 NPI 不是 NP 完全的

如果我们假设 P = NP 而不是 P != NP，这个定理会发生什么？我们知道如果 NP Intermediate 不存在，那么 P = NP。但是如果 P = NP，NP Intermediate 是否存在？

正式的光学字符识别 (OCR) 有多难？让我们假设一个与人类相当的容错能力（我相信，大约 98%）。

换句话说，它在问题复杂性和难处理性的 P/NP 量表中的位置是什么？

或者它适合那个规模吗？这是一个什么样的问题？

我对问题复杂性的正式定义不是很熟悉。我只是好奇。

我会使用什么算法（暴力与否）在停车场中放置尽可能多的汽车（假设所有汽车的大小相同），以便至少有一个出口（来自集装箱）并且不能阻止汽车。或者有人可以向我展示以编程方式解决此问题的示例。

停车场的形状不同会很好，但如果你想假设它是一些不变的形状，那很好。

另一个编辑：假设停车场的行驶距离不是一个因素（尽管如果它是加权因素到停车场的汽车数量，那将是非常棒的）。

另一个编辑：假设 2 维（没有起重机或在汽车上行驶）。

另一个编辑：一旦停放汽车，您就不能四处移动（这不是代客泊车场）。

是否有某种语言是 NP 完全的，但我们知道一些“快速”算法？我的意思不是像背包那样我们平均可以做得很好，我的意思是即使在最坏的情况下，运行时间也类似于 2^n^epsilon，结果对于任何 epsilon>0 都成立，所以我们可以让它任意接近0。

如果您将 3-cnf-sat 问题更改如下：
对于每个 c _i， c _i = -x _i1 OR -x _i2 OR x _i3意味着恰好有一个变量出现而没有否定。
您还可以为某些（或全部）x 赋予值（0 或 1）。
您应该能够在多项式时间内解决问题（找到满足问题或证明问题不可满足的 x 值）。

1. 解决这个问题的多项式运行时间算法是什么？
2. 证明它在多项式时间内运行。

提示：表明 c _i = -x _i1 OR -x _i2 OR x _i3等于 c = (x _i1 AND -x _i2 ) -> x _i3

假设有一排x 个装满小饰品（随机数量）的箱子，一目了然（你可以看到每个箱子里有多少小饰品）。现在有两名玩家可以在轮到他们时从任一端选择一个垃圾箱。他们不能放弃转弯。想出一个策略让玩家获得最大数量的小饰品。

x是偶数。

这是一个 np 完全问题吗？它类似于布尔SAT吗？

对于我正在制作的游戏，我有一个数字列表——比如 [7, 4, 9, 1, 15, 2]（以此命名A）——还有另一个数字列表——比如 [11, 18 , 14, 8, 3]（命名为B）——提供给我。目标是找到所有数字组合A，加起来等于B. 例如：

• 1 + 2 = 3
• 1 + 7 = 8
• 2 + 9 = 11
• 4 + 7 = 11
• 1 + 2 + 4 + 7 = 14
• 1 + 2 + 15 = 18
• 2 + 7 + 9 = 18

...等等。（为此，1 + 2与 相同2 + 1。）

对于像这样的小列表，仅暴力组合是微不足道的，但我面临着看到数千到数万个这样的数字的可能性，并且将在应用程序的生命周期内重复使用此例程。是否有任何优雅的算法可以在合理的时间内以 100% 的覆盖率完成此任务？如果做不到这一点，我能找到任何一种体面的启发式方法，可以在合理的时间内给我一个“足够好”的组合吗？

我正在寻找一种伪代码或任何相当流行且可读的语言的算法（注意那里的“和”......；），甚至只是关于如何实施这种搜索的英文描述。

编辑添加：

到目前为止提供了很多很好的信息。谢了，兄弟们！暂时总结一下：

• 问题是 NP-Complete，所以要在合理的时间内获得 100% 的准确率，没有任何办法。
• 该问题可以看作是子集和或背包问题的变体。两者都有众所周知的启发式方法，它们可能适用于这个问题。

让想法不断涌现！再次感谢！

我想将域名分解为组成词和数字，例如

iamadomain11.com = ['i', 'am', 'a', 'domain', '11']

我该怎么做呢？我知道可能有多组可能，但是，我目前还可以，只获得一组可能性。

输入：图 G 输出：几个独立的集合，这样一个节点对所有独立集合的成员资格是唯一的。因此，一个节点与它自己集合中的任何节点都没有连接。这是一个示例路径。

由于这里需要进行澄清，因此需要重新改写：

将给定的图划分为集合，使得

1. 我可以通过集合中的成员身份将节点与所有其他节点区分开来，例如，如果节点 i 仅存在于集合 A 中，则其他节点不应仅存在于集合 A 中

   如果节点 j 存在于集合 A 和 B 中，则其他节点不应仅存在于集合 A 和 B 中。如果节点的成员资格由位模式编码，那么这些位模式的汉明距离至少为 1

2. 如果两个节点在图中相邻，它们不应该出现在同一个集合中，因此是一个独立的集合

示例：B 没有相邻节点 D=>A, A=>D

解决方案：

1. 乙/
2. / BD

A 的位模式为 10，并且在其集合中没有相邻节点。B 具有位模式 11 且没有相邻节点，D 具有 01 因此所有节点的汉明距离至少为 1 且没有相邻节点 => 正确

错了，因为 D 和 A 是相连的：

1. 亚行
2. / D B

A 在其集合中有位模式 10 和 D，它们是相邻的。B 有 11 位模式且没有相邻节点，D 有 11 和 B 一样，所以这个解决方案有两个错误，因此它不被接受。

当然，随着图中节点数量的增加，这应该扩展到更多的集合，因为您至少需要log(n)集合。

我已经写了一个到 MAX-SAT 的转换，为此使用 sat-solver。但是子句的数量太大了。更直接的方法会很好。到目前为止，我有一个近似值，但我想要一个精确的解决方案或至少一个更好的近似值。

我尝试了一种方法，我使用粒子群将任意解决方案优化为更好的解决方案。然而，运行时间非常糟糕，结果远非很好。我正在寻找动态算法或其他东西，但是我无法理解如何分而治之。