algorithm - 从现有解决方案生成 2-SAT 解决方案

Question

涉及 SCC 的 2-SAT 的多项式时间算法告诉我们是否存在解决方案，也帮助我们生成问题的解决方案。但可以有不止一种解决方案。我想知道是否可以使用现有解决方案有效地生成其他解决方案？

Answer 1

我想这取决于您对“其他解决方案”的定义，例如2SAT 的优化问题（变量数量最少为 1 的解决方案）是 NP 完全的。

如果您想要任何解决方案，并且“高效”是指多项式时间 - 您可以将赋值中的变量从 true->false 翻转，反之亦然（一种简单的方法是添加(x OR x)or for false(^x OR ^x)作为子句）。然后，重新运行您的 2SAT 求解器将为您提供不同的解决方案（如果存在）。n大多数时候您需要重新运行您的 2SAT 求解器，其中n变量的数量是多少，并且由于您的 2SAT 求解器也是多项式时间，因此该解决方案在多项式时间内运行。