解决多个假设
Solving with multiple assumptions
假设我有一个带有变量 (a,b,c,d,e,f,g) 的 CNF 表达式。鉴于 {a,b,c,g} = {1,0,0,1} 和 {a,b,c,g} = {1,1,1,1}，我将如何使用 SAT 求解器找到 (d,e,f) 的作业？如果这是一个假设，调用 sat 求解器来查找 {d,e,f} 的赋值将是直截了当的（例如，通过向 CNF 添加单元子句）。但是，如果我有多个假设怎么办？这可能吗？
以下是哈罗德（我认为）试图向您描述的步骤。您对变量 a、b、c、d、e、f 和 g 有一些 CNF 公式 F。
- 复制公式，调用复制的 G。
- 在G中，将变量a替换为aa，b替换为bb，c替换为cc，g替换为gg。
- 在 F 中添加单元子句，使得 (a,b,c,g) = (1,0,0,1)。
- 向 G 添加单位子句，使得 (aa,bb,cc,gg) = (1,1,1,1)。
- 连接公式 F 和 G，并将结果输入 SAT 求解器。
求解器将找到与 (a,b,c,g) 和 (aa,bb,cc,gg) 的预设值一致的令人满意的分配。
不太清楚你是想要一个实用的答案还是一个有趣的理论答案。我会去实践。
对于每组假设，调用一个 sat 求解器，该求解器支持基于该组假设的假设求解 (example)。在同一个求解器实例上按顺序执行此操作。
优点：
- 您不要混合互斥假设集的可满足性。如果一组假设 A 满足公式 F 而另一组 A' 不满足 F，每次调用求解器都会告诉您这些假设是否 sat/unsat.
- 第一次通话中学到的条款可能会在第二次通话中保留下来。中间学到的子句谈论相同的变量。 （注意：如果您有一个不相交的公式
F & G，其中 F 在变量 X 上，G 在变量 Y 上，并且 X 和 Y 不共享任何变量，则解析 - CDCL 中使用的推理规则 - 无法导出混合 F 的子句和 G。将两者混合在一起而不是将它们分开没有明显的好处，除非一个实例更容易证明不饱和并提前停止。）
缺点：
- 如果实例 A 在实践中很难解决，但 A' 很简单，您可能会卡在 A 上。
- 它不是并行的，所以如果您想尽快解决的实例多于两个，则需要额外的机制。
我知道这是一个显而易见的答案，但值得一试。如果失败，您可以尝试做一些更有趣的事情，例如解决 w.r.t。假设 A union A'，并且只有在不满意的情况下才能解决退回到 A 然后 A' 的策略。这对您的示例没有帮助，因为 (a,b,c,g) = (1,0,0,1) 和 (a,b,c,g) = (1,1,1,1) 是互斥的。
假设我有一个带有变量 (a,b,c,d,e,f,g) 的 CNF 表达式。鉴于 {a,b,c,g} = {1,0,0,1} 和 {a,b,c,g} = {1,1,1,1}，我将如何使用 SAT 求解器找到 (d,e,f) 的作业？如果这是一个假设，调用 sat 求解器来查找 {d,e,f} 的赋值将是直截了当的（例如，通过向 CNF 添加单元子句）。但是，如果我有多个假设怎么办？这可能吗？
以下是哈罗德（我认为）试图向您描述的步骤。您对变量 a、b、c、d、e、f 和 g 有一些 CNF 公式 F。
- 复制公式，调用复制的 G。
- 在G中，将变量a替换为aa，b替换为bb，c替换为cc，g替换为gg。
- 在 F 中添加单元子句，使得 (a,b,c,g) = (1,0,0,1)。
- 向 G 添加单位子句，使得 (aa,bb,cc,gg) = (1,1,1,1)。
- 连接公式 F 和 G，并将结果输入 SAT 求解器。
求解器将找到与 (a,b,c,g) 和 (aa,bb,cc,gg) 的预设值一致的令人满意的分配。
不太清楚你是想要一个实用的答案还是一个有趣的理论答案。我会去实践。
对于每组假设，调用一个 sat 求解器，该求解器支持基于该组假设的假设求解 (example)。在同一个求解器实例上按顺序执行此操作。
优点：
- 您不要混合互斥假设集的可满足性。如果一组假设 A 满足公式 F 而另一组 A' 不满足 F，每次调用求解器都会告诉您这些假设是否 sat/unsat.
- 第一次通话中学到的条款可能会在第二次通话中保留下来。中间学到的子句谈论相同的变量。 （注意：如果您有一个不相交的公式
F & G，其中 F 在变量 X 上，G 在变量 Y 上，并且 X 和 Y 不共享任何变量，则解析 - CDCL 中使用的推理规则 - 无法导出混合 F 的子句和 G。将两者混合在一起而不是将它们分开没有明显的好处，除非一个实例更容易证明不饱和并提前停止。）
缺点：
- 如果实例 A 在实践中很难解决，但 A' 很简单，您可能会卡在 A 上。
- 它不是并行的，所以如果您想尽快解决的实例多于两个，则需要额外的机制。
我知道这是一个显而易见的答案，但值得一试。如果失败，您可以尝试做一些更有趣的事情，例如解决 w.r.t。假设 A union A'，并且只有在不满意的情况下才能解决退回到 A 然后 A' 的策略。这对您的示例没有帮助，因为 (a,b,c,g) = (1,0,0,1) 和 (a,b,c,g) = (1,1,1,1) 是互斥的。