2020-2021:teams:legal_string:lgwza:2-sat
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:2-sat [2020/08/25 19:17] lgwza [例题] |
2020-2021:teams:legal_string:lgwza:2-sat [2020/08/25 19:21] (当前版本) lgwza [现实意义] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| 比如邀请人来吃喜酒，夫妻二人必须去一个，然而某些人之间有矛盾（比如 A 先生与 B 女士有矛盾，C 女士不想和 D 先生在一起），那么我们要确定能否避免来人之间没有矛盾，有时需要方案。这是一类生活中常见的问题。 | 比如邀请人来吃喜酒，夫妻二人必须去一个，然而某些人之间有矛盾（比如 A 先生与 B 女士有矛盾，C 女士不想和 D 先生在一起），那么我们要确定能否避免来人之间没有矛盾，有时需要方案。这是一类生活中常见的问题。 | ||
| - | 使用布尔方程表示上述问题。设 $a$ 表示 $A$ 先生去参加，那么 $B$ 女士就不能参加 $(\neg a);b$ 表示 $C$ 女士参加，那么 $\neg b$ 也一定成立（D 先生不参加）。总结一下，即 $(a \or b)$（变量 $a,b$ 至少满足一个）。对这些变量关系建有向图，则有：$ab ba $（$a$ 不成立则 $b$ 一定成立；同理，$b$ 不成立则 $a$ 一定成立）。建图之后，我们就可以使用缩点算法来求解 2-SAT 问题了。 | + | 使用布尔方程表示上述问题。设 $a$ 表示 $A$ 先生去参加，那么 $B$ 女士就不能参加 $(\neg a);b$ 表示 $C$ 女士参加，那么 $\neg b$ 也一定成立（D 先生不参加）。总结一下，即 $(a \vee b)$（变量 $a,b$ 至少满足一个）。对这些变量关系建有向图，则有：$\neg a\Rightarrow b\ \wedge \neg b\Rightarrow a $（$a$ 不成立则 $b$ 一定成立；同理，$b$ 不成立则 $a$ 一定成立）。建图之后，我们就可以使用缩点算法来求解 2-SAT 问题了。 |
| ===== 常用解决方法 ===== | ===== 常用解决方法 ===== | ||
2020-2021/teams/legal_string/lgwza/2-sat.1598354259.txt.gz · 最后更改: 2020/08/25 19:17 由 lgwza
