2-SAT（精选）.ppt

由对称性解2-SAT问题
2-SAT:
2-SAT就是2判定性问题,是一种特殊的逻辑判定问题。
2-SAT问题有何特殊性?该如何求解?
我们从一道例题来认识2-SAT问题,并提出对一类2-SAT问题通用的解法。
Poi 0106 mission [和平委员会]
某国有n个党派,每个党派在议会中恰有2个代表。
现在要成立和平委员会,该会满足:
每个党派在和平委员会中有且只有一个代表
如果某两个代表不和,则他们不能都属于委员会
代表的编号从1到2n,编号为2a-1、2a的代表属于第a个党派
输入n(党派数),m(不友好对数)及m对两两不和的代表编号
其中1≤n≤8000,0≤m ≤20000
求和平委员会是否能创立。
若能,求一种构成方式。
例:输入:3 2 输出:1
1 3 4
2 4 5
分析:
原题可描述为:
有n个组,第i个组里有两个节点Ai, Ai' 。需要从每个组中选出一个。而某些点不可以同时选出(称之为不相容)。任务是保证选出的n个点都能两两相容。
(在这里把Ai, Ai' 的定义稍稍放宽一些,它们同时表示属于同一个组的两个节点。也就是说,如果我们描述Ai,那么描述这个组的另一个节点就可以用Ai')
初步构图
如果Ai与Aj不相容,那么如果选择了Ai,必须选择Aj‘;同样,如果选择了Aj,就必须选择Ai’。
Ai Aj'
Aj Ai‘
这样的两条边对称
我们从一个例子来看:
假设4个组,不和的代表为:1和4,2和3,7和3,那么构图:
1
3
2
4
5
6
7
8
假设:
首先选1
3必须选,2不可选
8必须选,4、7不可选
5、6可以任选一个
矛盾的情况为:
存在Ai,使得Ai既必须被选又不可选。
得到算法1:
枚举每一对尚未确定的Ai, Ai‘,任选1个,推导出相关的组,若不矛盾,则可选择;否则选另1个,同样推导。若矛盾,问题必定无解。
1
3
2
4
5
6
7
8
此算法正确性简要说明:
由于Ai,Ai' 都是尚未确定的,它们不与之前的组相关联,前面的选择不会影响Ai, Ai' 。
算法的时间复杂度在最坏的情况下为O(nm)。
在这个算法中,并没有很好的利用图中边的对称性
先看这样一个结构:
更一般的说:
在每个一个环里,任意一个点的选择代表将要选择此环里的每一个点。不妨把环收缩成一个子节点(规定这样的环是极大强连通子图)。新节点的选择表示选择这个节点所对应的环中的每一个节点。
此图中1和3构成一个环,这样1和3要么都被选择,要么都不被选。
2和4同样如此。
图的收缩
1
3
2
4
5
6
7
8