2-可满足性问题的算法

Question

任何人都可以解释 2-可满足性问题的算法或提供相同的链接吗？我找不到很好的链接来理解它。

Answer 1

如果你有 n 个变量和 m 个子句:

创建一个有 2n 个顶点的图:直观上，每个顶点类似于每个变量的真实或非真实文字。对于每个子句 (a v b)，其中 a 和 b 是文字，创建从 !a 到 b 和从 !b 到 a 的边。这些边意味着如果 a 不为真，则 b 必须为真，反之亦然。

创建此有向图后，遍历该图并查看是否存在包含某个变量 a 的 a 和 !a 的循环。如果存在，则 2SAT 不可满足(因为 a 暗示 !a 并且反之亦然)。否则，它是可满足的，这甚至可以给你一个令人满意的假设(选择一些文字 a，这样 a 就不会暗示!a，从那里强制所有暗示，重复)。您可以使用任何标准图形算法来完成此部分，ala Breadth-First Search , Floyd-Warshall ，或任何类似的算法，具体取决于您对算法的时间复杂度的敏感程度。