从现有解决方案到 2-SAT 的生成解决方案
Generation solutions to 2-SAT from an existing one
涉及SCC的2-SAT的多项式时间算法告诉我们解是否存在，也帮助我们生成问题的解。但是可以有不止一种解决方案。我想知道是否可以使用现有解决方案有效地生成其他解决方案？
我想这取决于您对“其他解决方案”的定义，例如 optimization problem of 2SAT（变量数量最少的解决方案为 1 的解决方案）是 NP-Complete。
如果您想要 任何 解决方案，并且“高效”是指多项式时间 - 您可以在赋值中将变量从 true->false 翻转，反之亦然（一种简单的方法要做到这一点是添加 (x OR x) 或 false (^x OR ^x) 作为子句）。然后，重新运行 2SAT 求解器将为您提供不同的解决方案（如果存在）。您最多需要重新运行您的 2SAT 求解器 n 次，其中 n 是变量的数量，并且由于您的 2SAT 求解器也是多项式时间，因此该解决方案以多项式时间运行。
涉及SCC的2-SAT的多项式时间算法告诉我们解是否存在，也帮助我们生成问题的解。但是可以有不止一种解决方案。我想知道是否可以使用现有解决方案有效地生成其他解决方案？
我想这取决于您对“其他解决方案”的定义，例如 optimization problem of 2SAT（变量数量最少的解决方案为 1 的解决方案）是 NP-Complete。
如果您想要 任何 解决方案，并且“高效”是指多项式时间 - 您可以在赋值中将变量从 true->false 翻转，反之亦然（一种简单的方法要做到这一点是添加 (x OR x) 或 false (^x OR ^x) 作为子句）。然后，重新运行 2SAT 求解器将为您提供不同的解决方案（如果存在）。您最多需要重新运行您的 2SAT 求解器 n 次，其中 n 是变量的数量，并且由于您的 2SAT 求解器也是多项式时间，因此该解决方案以多项式时间运行。