javascript - 是否有快速算法来解决难题

Question

我有一个拼图，可以用碎片拼出一些形状。我用数字枚举形状中的所有位置，然后为每件作品组成一组数字，这件作品可以采用。所以我有自然数的集合A集合B集合C集合，例如，

[
  [ [1,3,5], [2,4,8], [1,5,9] ],
  [ [1,2,3,9], [3,5,19], [10,12,33], [14] ],
  ...
  [22,46,50], [13,15,33,44,57], ..., [7,17]
]

我需要从每组 B 中选择一组 C，这样所有数字都是唯一的，这将是拼图的解决方案，例如，

[1,3,5] from first set,
[10,12,33] from second and so on,
where [1,3,5,10,12,33,..] <== contains unique numbers

是否有任何算法(比蛮力更快)来解决这个任务？

Answer 1

如您所料，它是 NP 完全的。这并不意味着它没有希望(蛮力设置了一个非常低的阈值)，请参阅下面的方法，它确实意味着预计不会存在在多项式时间内在 最坏情况下执行此操作的算法。所以你不会得到一个很好的答案，比如“做一个二分匹配”或类似的东西。

无论如何，它是 NP 完全的，分两步:

在NP中

很明显，给定“对于每个 B，选择哪个集合 C”(多项式大小)的特定选择，很容易(多项式时间)验证集合 C 是从每个 B 中挑选出来的，并且没有重叠。

它是 NP 难的

有很多方法可以做到这一点，但这里有一个例子:减少图形着色来解决这个问题。

对于图的每个顶点，创建一个集合 B。对于每个顶点 i 的每个颜色 k，在 B(i) 中创建一个集合 C(i,k)。

这个想法是，如果在集合 B(i) 中选择一个特定的集合 C(i,k)，那么它会为顶点 i 选择颜色 k，并且我们使用全局“唯一性”约束来防止相邻获得相同颜色的顶点。所以:

在对应于用颜色 k 着色 B(i) 的集合 C(i,k) 中，添加数字 pairToInt(i, k)。对于对应于用 k(输入图中与 i 相邻的 j)着色 B(j) 的集合 C(j,k)，也添加该数字。这禁止用相同的颜色为 i 和 j(相邻的)着色，因为这些集合 C 包含相同的数字并且不能同时选择。它不会禁止不相邻的顶点具有相同的颜色。 pairToInt 可以是 Cantor 配对函数或更简单的东西，只要唯一对映射到唯一整数就没关系。

---

例如，您可以使用 SAT 公式:

• 为每个集合C引入一个变量x[i]
• 对于每个集合 B，创建一个子句强制选择 B 中的至少一个集合
• 对于 C 中共享一个数字的每对集合，创建一个子句强制选择这些集合中的至多一个

这不是太大，只是二次方大小。顺便说一下，求解器可能会为一个 B 选择多个集合 C，但是您可以丢弃多余的部分，直到每个 B 只选择一个 C。以这种方式丢弃不会破坏其他约束。如果存在必须选择每个数字的约束条件，那么这将是危险的，但我们没有该约束条件。

那么问题是，这比蛮力更快吗？实际上它应该是，例如基于 CDCL 的求解器会快速发现不兼容选择的模式并在将来避免它们，并且 bool 约束传播用于快速填充决策的结果而不是暴力强制它们，所以时间主要花在问题实例的硬“核心”上。暴力破解也会在简单的部分花费大量时间。