好的，我不能得到大约 2 ^ N，但我可以减少样本集。为此，我们将计算“组合约束”。组合约束是一个约束，如果左侧的所有选项都被选中，则右侧的任何选项都不能被选中，但基于左侧选项的其他约束可能不适用。
我们需要从一组约束中计算出一组所有可能的组合约束。虽然没有必要，但如果右手组小于左手组，我们将通过交换左右手来“修复”现有约束。这可能会减少一些组合约束，尽管可以使用更好的启发式进行交换。
我们还需要计算可以为每个组任意选择的选项的“最小集合”。这个最小集合是通过从可用选项列表中删除组合约束左侧出现的任何选项来计算的。
下面是一个算法，但我没有证明它可以正确计算 CC。我将证明，如果确实如此，那么它们可用于计算可能组合的数量。
- 固定约束，使左手的组小于或等于右手的组。
编写约束：
- 左手排序约束
依次，对于每个约束：
- 用相同的左手将约束与跟随它的所有约束折叠起来，将
x1 <-> y1, x1 <-> y2...x1 <-> yN变成Set(x1) <-> Set(y1 ... yN)
- 如果：
- x1 不在已折叠约束的右手边
- x1 不属于左手任意元素的同一组
- 将折叠约束及其所有组合添加到折叠约束集
通过采用所有选项并删除固定约束左侧出现的选项来计算最小集。
现在您可以使用下面的公式计算组合的数量。让我们称 CC 为组合约束。那么组合的数量是：
C(Mininum Set) + CCC1 + ... + CCCn
在哪里：
- C（最小集）是最小集可能的组合数。
- CCCx 是可能的组合数，方法是采用最小集合，用该选项替换 CCx 左侧有选项的任何组，然后删除 CCx 右侧的任何选项。
请注意，该表达式纯粹是加法的。这意味着，要使该表达式产生预期结果，必须满足以下两个条件：
- 它的任何两个术语都不能包含相同的组合。
- 所有组合都必须由这些条款说明。
- 任何术语都不能产生无效的组合。
对于第一个证明，请注意没有两个不同的 CC 具有相同的左手。如果两个 CC 具有相同的左手但不同的右手，则意味着存在必须应用于其中一个 CC 的附加约束，或者将无效约束应用于另一个。
由于没有两个CC具有相同的左手，并且根据定义，最小集合不包含任何CC的左手，因此可以通过至少一个选项来区分任何两个CC . 因此，没有两个 CC 可以产生相同的组合。
对于第二个证明，请注意，根据定义，CC 集合包含左侧选项的所有有效组合。
假设有一个组合既没有出现在最小集合中，也没有出现在 CC 集合中。如果此组合不包含任何左选项，则根据定义，它必须是最小集合中的组合。因此，它必须包含来自左手的选项。
由于 CC 集合包含左手的所有有效组合，因此有一个 CC 具有相同的左手选项。因此，该组合必须具有该 CC 的任何组合中未包含的选项。但唯一没有包含在该 CC 中的选项是出现在其他 CC 左侧的选项，以及必须通过约束从其中排除的选项。既然两者都不是，那么这种组合就不可能存在。
对于第三个证明，我们首先考虑最小集。最小集合不包含任何组左侧的任何选项。由于所有约束都在一个左手选项和一个右手选项之间，因此没有约束适用于最小集合。
现在让我们考虑CC。根据定义，CC 具有左手选项的有效组合。任何与左手不兼容的选项都必须出现在右手中，并且右手中的任何选项都必须从最小集合中删除。由于在最小集合上没有选项在它们之间开始不兼容，因此在 CC 上的任何组合中都不会存在不满足的约束。
至此，证明结束。
让我们看看评论中的一个例子是如何应用的：
G1: x1, x2, x3
G2: y1, y2
G3: z1, z2, z3
R1: x1 <-> y2
R2: x3 <-> y2
R3: y1 <-> z1
R4: y2 <-> z2
R5: y2 <-> z3
CC1: {x1} <-> {y2}
CC2: {x3} <-> {y2}
CC3: {y1} <-> {z1}
CC4: {x1, y1} <-> {y2, z1}
CC5: {x3, y1} <-> {y2, z1}
CC6: {y2} <-> {z2, z3}
让我们简要思考一下不在列表中的组合组：
R1&R2: {x1, x3} <-> {y2} -- not in the list because x1 and x3 belongs to the same
group
R1&R5: {x1, y2} <-> {y2} -- not in the list because the left hand of R2, y2
appears in the right hand of R1
现在，让我们看看每个集合中可能有哪些选项：
Minimum Set: (x2), (), (z1, z2, z3)
CC1: (x1), (), (z1, z2, z3) -- replace G1 with x1, remove y2 from G2
CC2: (x3), (), (z1, z2, z3) -- replace G1 with x3, remove y2 from G2
CC3: (x2), (y1), (z2, z3) -- replace G2 with y1, remove z1 from G3
CC4: (x1), (y1), (z2, z3) -- replace G1 with x1, G2 with y1, remove y2 and z1
CC5: (x3), (y1), (z2, z3) -- replace G1 with x3, G2 with y1, remove y2 and z1
CC6: (x2), (y2), (z1) -- replace G2 with y2, remove z2 and z3 from G3
现在，让我们添加一些东西：
C(Minimum Set) = 1 * 0 *3 = 0
CCC1 = 1 * 0 * 3 = 0
CCC2 = 1 * 0 * 3 = 0
CCC3 = 1 * 1 * 2 = 2
CCC4 = 1 * 1 * 2 = 2
CCC5 = 1 * 1 * 2 = 2
CCC6 = 1 * 1 * 1 = 1
C(Minimum Set) + CCC1 + CCC2 + CCC3 + CCC4 + CCC5 + CCC6
0 + 0 + 0 + 2 + 2 + 2 + 1 = 7
我将在这里添加一个进一步的想法。尽管 5 条规则只有 6 个 CCC，远少于预期的 32 个术语，但这些 CCC 是用 2^N 最坏时间计算的，因为对于每条规则，您必须将其与迄今为止创建的所有 CCC 进行比较和组合。您可能将它们视为二进制数，如果正在组合规则，则设置一个位，否则不设置。
但是，不兼容的组合会立即被丢弃，因此对于每个被组合的新规则，不会在已经被视为无效的组合上浪费时间。此外，通过预先对规则进行排序，同一组中的连续规则可能会被丢弃，甚至无需测试是否具有正确的数据结构的不兼容性。
正如这个特定示例所示，平均时间可能比 2^N 好得多。
替代算法和注意事项
有一些关于 2-SAT 和 3-SAT 的讨论。在我看来，这是一个 2-SAT 问题，因为每个约束 a <-> b 实际上都是一个子句“！a || ！b”。所以所有约束一起可以写成“(!x1 || !y2) && (!x1 || !z4) && (!y2 && !z3)”等。这意味着你可以从某种意义上“解决”它您可以找出每个选项是否有布尔赋值，这将变为 true。Aspall、Plass 和 Tarjan 对此有一个线性算法，这里有一个幻灯片演示。
但是知道约束是否可以解决并不是我们要问的。所问的是在保持 2-SAT 问题正确的情况下可以设置所有选项的方式的数量。
现在，有一些有效的算法可以计算满足 2-SAT 问题的方法的数量。例如，本文提出了一种在 1.2561 n中运行的算法。但即使这样也无济于事，因为我们需要知道解决方案是什么才能计算出满足该解决方案的组合数量。
根据维基百科，本文有一种算法可以有效地枚举所有解决方案，这正是我们想要的。但是，如果计数已经是指数级的，那么枚举也是如此。也许比 2 n好，但仍然是指数级的。
如果我们确实列举了 2-SAT 问题的所有解决方案，则每个组的组合数乘以 1 乘以未选择任何选项的每个组的自由选项数，即未出现在任何约束中的选项由解决方案。
例如，采用前一组组和约束。包括互斥在内的 2-SAT 问题是：
(!x1 || !y2) && (!x3 || !y2) && (!y1 || !z1) && (!y2 || !z2) && (!y2 || !z3) && (!x1 || !x3) && (!y1 || !y2) && (!z1 || !z2) && (!z1 || !z3) && (!z2 || !z3)
第一行是五个规则。第二行是约束规则中出现的同一组中所有选项的互斥。
这个 2-SAT 问题的解决方案是：
x1 x3 y1 y2 z1 z2 z3 Combinations
true false true false false true false 1
true false true false false false true 1
true false true false false false false 0
true false false false true false false 0
true false false false false true false 0
true false false false false false true 0
true false false false false false false 0
false true true false false true false 1
false true true false false false true 1
false true true false false false false 0
false true false false true false false 0
false true false false false true false 0
false true false false false false true 0
false true false false false false false 0
false false true false false true false 1
false false true false false false true 1
false false true false false false false 0
false false false true true false false 1
false false false true false false false 0
false false false false true false false 0
false false false false false true false 0
false false false false false false true 0
false false false false false false false 0
在前两个解决方案中，没有没有选择选项的组，因此组合数为 1。第三个解决方案没有为组 G3 选择选项，因此我们将 1 乘以 0。在以“false”开头的行中false”，组 G1 没有选择选项，并且有一个免费选项：x2。因此，我们将它们乘以 1，如果没有为 G2 或 G3 选择选项，则乘以 0（在这种情况下，自由选项的数量为 0）。
现在，有一个问题是我如何强制在每个组中选择一个选项并且仍然声称是 2-SAT。如前所述，该问题有两个隐式约束：对于每个组，必须选择一个且只有一个选项。这两个约束可以写成：
x 1 || x 2 || x 3（对于带有选项 x 1 .. x 3的组 x ）
(!x 1 || !x 2 ) && (!x 1 || !x 3 ) && (!x 2 || !x 3 )
后一个约束是 2-SAT，前一个约束是 3-SAT，适用于任何非平凡的情况。碰巧的是，我没有强制执行第一个约束，但是计数变为 0。计数算法应该是这样的：
- 对于无约束组合，将每组中无约束选项的数量相乘。
- 对于完全约束组合，添加以下计数的结果：
- 对于每个解决方案，将每组中没有一个选项评估为“真”的无约束选项的数量相乘。
因此，对于其中至少有一个无约束选项的每个组，选择是隐式和匿名的。对于所有选项都是某个约束的一部分的每个组，如果未选择任何选项，则该组的计数变为 0，因此，该解决方案的组合数也变为 0。
这感觉就像从有效的 > 2-SAT 约束中欺骗问题。毕竟，如果这是可能的，那么 3-SAT 问题可以通过枚举其中 2-SAT 部分的解决方案来解决，然后丢弃所有不满足其 3-SAT 部分的解决方案。唉，我可以确定一个根本区别：
- 问题的 2-SAT 部分未解决的所有谓词都不受任何进一步的约束。
鉴于对子句的这种相当严格的约束，我们可以通过枚举 2-SAT 显式约束的解决方案来解决这个问题。
如果有人想进一步追求这一点，请继续。我对我建议的 2 n解决方案的改进感到满意。