[转]2-SAT问题及其算法

时间:2022-04-05 03:51:49

  转自:http://www.cppblog.com/MatoNo1/archive/2011/07/13/150766.html

【2-SAT问题】
现有一个由N个布尔值组成的序列A,给出一些限制关系,比如A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等,要确定A[0..N-1]的值,使得其满足所有限制关系。这个称为SAT问题,特别的,若每种限制关系中最多只对两个元素进行限制,则称为2-SAT问题。

由于在2-SAT问题中,最多只对两个元素进行限制,所以可能的限制关系共有11种:
A[x]
NOT A[x]
A[x] AND A[y]
A[x] AND NOT A[y]
A[x] OR A[y]
A[x] OR NOT A[y]
NOT (A[x] AND A[y])
NOT (A[x] OR A[y])
A[x] XOR A[y]
NOT (A[x] XOR A[y])
A[x] XOR NOT A[y]
进一步,A[x] AND A[y]相当于(A[x]) AND (A[y])(也就是可以拆分成A[x]与A[y]两个限制关系),NOT(A[x] OR A[y])相当于NOT A[x] AND NOT A[y](也就是可以拆分成NOT A[x]与NOT A[y]两个限制关系)。因此,可能的限制关系最多只有9种。

在实际问题中,2-SAT问题在大多数时候表现成以下形式:有N对物品,每对物品中必须选取一个,也只能选取一个,并且它们之间存在某些限制关系(如某两个物品不能都选,某两个物品不能都不选,某两个物品必须且只能选一个,某个物品必选)等,这时,可以将每对物品当成一个布尔值(选取第一个物品相当于0,选取第二个相当于1),如果所有的限制关系最多只对两个物品进行限制,则它们都可以转化成9种基本限制关系,从而转化为2-SAT模型。

【建模】
其实2-SAT问题的建模是和实际问题非常相似的。
建立一个2N阶的有向图,其中的点分为N对,每对点表示布尔序列A的一个元素的0、1取值(以下将代表A[i]的0取值的点称为i,代表A[i]的1取值的点称为i')。显然每对点必须且只能选取一个。然后,图中的边具有特定含义。若图中存在边<i, j>,则表示若选了i必须选j。可以发现,上面的9种限制关系中,后7种二元限制关系都可以用连边实现,比如NOT(A[x] AND A[y])需要连两条边<x, y'>和<y, x'>,A[x] OR A[y]需要连两条边<x', y>和<y', x>。而前两种一元关系,对于A[x](即x必选),可以通过连边<x', x>来实现,而NOT A[x](即x不能选),可以通过连边<x, x'>来实现。

【O(NM)算法:求字典序最小的解】
根据2-SAT建成的图中边的定义可以发现,若图中i到j有路径,则若i选,则j也要选;或者说,若j不选,则i也不能选;
因此得到一个很直观的算法:
(1)给每个点设置一个状态V,V=0表示未确定,V=1表示确定选取,V=2表示确定不选取。称一个点是已确定的当且仅当其V值非0。设立两个队列Q1和Q2,分别存放本次尝试选取的点的编号和尝试不选的点的编号。
(2)若图中所有的点均已确定,则找到一组解,结束,否则,将Q1、Q2清空,并任选一个未确定的点i,将i加入队列Q1,将i'加入队列Q2;
(3)找到i的所有后继。对于后继j,若j未确定,则将j加入队列Q1;若j'(这里的j'是指与j在同一对的另一个点)未确定,则将j'加入队列Q2;
(4)遍历Q2中的每个点,找到该点的所有前趋(这里需要先建一个补图),若该前趋未确定,则将其加入队列Q2;
(5)在(3)(4)步操作中,出现以下情况之一,则本次尝试失败,否则本次尝试成功:
<1>某个已被加入队列Q1的点被加入队列Q2;
<2>某个已被加入队列Q2的点被加入队列Q1;
<3>某个j的状态为2;
<4>某个i'或j'的状态为1或某个i'或j'的前趋的状态为1;
(6)若本次尝试成功,则将Q1中的所有点的状态改为1,将Q2中所有点的状态改为2,转(2),否则尝试点i',若仍失败则问题无解。
该算法的时间复杂度为O(NM)(最坏情况下要尝试所有的点,每次尝试要遍历所有的边),但是在多数情况下,远远达不到这个上界。
具体实现时,可以用一个数组vst来表示队列Q1和Q2。设立两个标志变量i1和i2(要求对于不同的i,i1和i2均不同,这样可以避免每次尝试都要初始化一次,节省时间),若vst[i]=i1则表示i已被加入Q1,若vst[i]=i2则表示i已被加入Q2。不过Q1和Q2仍然是要设立的,因为遍历(BFS)的时候需要队列,为了防止重复遍历,加入Q1(或Q2)中的点的vst值必然不等于i1(或i2)。中间一旦发生矛盾,立即中止尝试,宣告失败。

该算法虽然在多数情况下时间复杂度到不了O(NM),但是综合性能仍然不如下面的O(M)算法。不过,该算法有一个很重要的用处:求字典序最小的解!
如果原图中的同一对点编号都是连续的(01、23、45……)则可以依次尝试第0对、第1对……点,每对点中先尝试编号小的,若失败再尝试编号大的。这样一定能求出字典序最小的解(如果有解的话),因为一个点一旦被确定,则不可更改
如果原图中的同一对点编号不连续(比如03、25、14……)则按照该对点中编号小的点的编号递增顺序将每对点排序,然后依次扫描排序后的每对点,先尝试其编号小的点,若成功则将这个点选上,否则尝试编号大的点,若成功则选上,否则(都失败)无解。

【具体题目】HDU1814(求字典序最小的解)

#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
const int MAXN = , MAXM = , INF = ~0U >> ;
struct node {
int a, b, pre, next;
} E[MAXM], E2[MAXM];
int _n, n, m, V[MAXN], ST[MAXN][], Q[MAXN], Q2[MAXN], vst[MAXN];
bool res_ex;
void init_d()
{
re(i, n) E[i].a = E[i].pre = E[i].next = E2[i].a = E2[i].pre = E2[i].next = i;
m = n;
}
void add_edge(int a, int b)
{
E[m].a = a; E[m].b = b; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m;
E2[m].a = b; E2[m].b = a; E2[m].pre = E2[b].pre; E2[m].next = b; E2[b].pre = m; E2[E2[m].pre].next = m++;
}
void solve()
{
re(i, n) {V[i] = ; vst[i] = ;} res_ex = ;
int i, i1, i2, j, k, len, front, rear, front2, rear2;
bool ff;
re(_i, _n) {
if (V[_i << ] == || V[(_i << ) + ] == ) continue;
i = _i << ; len = ;
if (!V[i]) {
ST[len][] = i; ST[len++][] = ; if (!V[i ^ ]) {ST[len][] = i ^ ; ST[len++][] = ;}
Q[front = rear = ] = i; vst[i] = i1 = n + i; Q2[front2 = rear2 = ] = i ^ ; vst[i ^ ] = i2 = (n << ) + i; ff = ;
for (; front<=rear; front++) {
j = Q[front];
for (int p = E[j].next; p != j; p=E[p].next) {
k = E[p].b;
if (V[k] == || vst[k] == i2 || V[k ^ ] == || vst[k ^ ] == i1) {ff = ; break;}
if (vst[k] != i1) {
Q[++rear] = k; vst[k] = i1;
if (!V[k]) {ST[len][] = k; ST[len++][] = ;}
}
if (vst[k ^ ] != i2) {
Q2[++rear2] = k ^ ; vst[k ^ ] = i2;
if (!V[k]) {ST[len][] = k ^ ; ST[len++][] = ;}
}
}
if (!ff) break;
}
if (ff) {
for (; front2<=rear2; front2++) {
j = Q2[front2];
for (int p = E2[j].next; p != j; p=E2[p].next) {
k = E2[p].b;
if (V[k] == || vst[k] == i1) {ff = ; break;}
if (vst[k] != i2) {
vst[k] = i2; Q2[++rear] = k;
if (!V[k]) {ST[len][] = k; ST[len++][] = ;}
}
}
if (!ff) break;
}
if (ff) {
re(j, len) V[ST[j][]] = ST[j][];
continue;
}
}
}
i = (_i << ) + ; len = ;
if (!V[i]) {
ST[len][] = i; ST[len++][] = ; if (!V[i ^ ]) {ST[len][] = i ^ ; ST[len++][] = ;}
Q[front = rear = ] = i; vst[i] = i1 = n + i; Q2[front2 = rear2 = ] = i ^ ; vst[i ^ ] = i2 = (n << ) + i; ff = ;
for (; front<=rear; front++) {
j = Q[front];
for (int p = E[j].next; p != j; p=E[p].next) {
k = E[p].b;
if (V[k] == || vst[k] == i2 || V[k ^ ] == || vst[k ^ ] == i1) {ff = ; break;}
if (vst[k] != i1) {
Q[++rear] = k; vst[k] = i1;
if (!V[k]) {ST[len][] = k; ST[len++][] = ;}
}
if (vst[k ^ ] != i2) {
Q2[++rear2] = k ^ ; vst[k ^ ] = i2;
if (!V[k]) {ST[len][] = k ^ ; ST[len++][] = ;}
}
}
if (!ff) break;
}
if (ff) {
for (; front2<=rear2; front2++) {
j = Q2[front2];
for (int p = E2[j].next; p != j; p=E2[p].next) {
k = E2[p].b;
if (V[k] == || vst[k] == i1) {ff = ; break;}
if (vst[k] != i2) {
vst[k] = i2; Q2[++rear] = k;
if (!V[k]) {ST[len][] = k; ST[len++][] = ;}
}
}
if (!ff) break;
}
if (ff) {
re(j, len) V[ST[j][]] = ST[j][];
continue;
}
}
}
if (V[_i << ] + V[(_i << ) + ] != ) {res_ex = ; break;}
}
}
int main()
{
int _m, a, b;
while (scanf("%d%d", &_n, &_m) != EOF) {
n = _n << ; init_d();
re(i, _m) {
scanf("%d%d", &a, &b); a--; b--;
if (a != (b ^ )) {add_edge(a, b ^ ); add_edge(b, a ^ );}
}
solve();
if (res_ex) {re(i, n) if (V[i] == ) printf("%d\n", i + );} else puts("NIE");
}
return ;
}

【O(M)算法】
根据图的对称性,可以将图中所有的强连通分支全部缩成一个点(因为强连通分支中的点要么都选,要么都不选),然后按照拓扑逆序(每次找出度为0的点,具体实现时,在建分支邻接图时将所有边取反)遍历分支邻接图,将这个点(表示的连通分支)选上,并将其所有对立点(注意,连通分支的对立连通分支可能有多个,若对于两个连通分支S1和S2,点i在S1中,点i'在S2中,则S1和S2对立)及这些对立点的前趋全部标记为不选,直到所有点均标记为止。这一过程中必然不会出现矛盾(详细证明过程省略,论文里有)。
无解判定:若求出所有强分支后,存在点i和i'处于同一个分支,则无解,否则必定有解。
时间复杂度:求强分支时间复杂度为O(M),拓扑排序的时间复杂度O(M),总时间复杂度为O(M)。

该算法的时间复杂度低,但是只能求出任意一组解,不能保证求出解的字典序最小。当然,如果原题不需要求出具体的解,只需要判定是否有解(有的题是二分 + 2-SAT判有解的),当然应该采用这种算法,只要求强连通分支(Kosaraju、Tarjan均可,推荐后者)即可。

【具体题目】PKU3648(本题的特殊情况非常多,具体见Discuss)

#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
const int MAXN = , MAXM = , INF = ~0U >> ;
struct edge {
int a, b, pre, next;
} E[MAXM], E2[MAXM];
int n, n2, m, m2, stk[MAXN], stk0[MAXN], V[MAXN], w[MAXN], st[MAXN], dfn[MAXN], low[MAXN], sw[MAXN], L[MAXN], R[MAXN];
int V2[MAXN], Q[MAXN], de[MAXN], Q0[MAXN];
bool vst[MAXN], res[MAXN], res_ex;
void init_d()
{
re(i, n) E[i].a = E[i].pre = E[i].next = i;
m = n;
}
void init_d2()
{
re(i, n2) {E2[i].a = E2[i].pre = E2[i].next = i; de[i] = ;}
m2 = n2;
}
void add_edge(int a, int b)
{
E[m].a = a; E[m].b = b; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
de[b]++;
}
void add_edge2(int a, int b)
{
E2[m2].a = a; E2[m2].b = b; E2[m2].pre = E2[a].pre; E2[m2].next = a; E2[a].pre = m2; E[E[m2].pre].next = m2++;
}
void solve()
{
int tp, tp0, x0, x, y, ord = , ord0 = ; n2 = ;
bool fd;
res_ex = ; re(i, n) V[i] = ;
re(i, n) if (!V[i]) {
stk[tp = ] = stk0[tp0 = ] = i; V[i] = ; dfn[i] = low[i] = ++ord; st[i] = E[i].next;
while (tp0 >= ) {
x = stk0[tp0]; fd = ;
for (int p=st[x]; p != x; p = E[p].next) {
y = E[p].b;
if (!V[y]) {
stk[++tp] = stk0[++tp0] = y; V[y] = ; dfn[y] = low[y] = ++ord; st[y] = E[y].next; st[x] = E[p].next; fd = ; break;
} else if (V[y] == && dfn[y] < low[x]) low[x] = dfn[y];
}
if (!fd) {
V[x] = ;
if (low[x] == dfn[x]) {
L[n2] = ord0;
while ((y = stk[tp]) != x) {w[y] = n2; sw[ord0++] = y; tp--;}
w[stk[tp--]] = n2; sw[ord0] = x; R[n2++] = ord0++;
};
if (tp0) {x0 = stk0[tp0 - ]; if (low[x] < low[x0]) low[x0] = low[x];} tp0--;
}
}
}
re(i, n) if (w[i] == w[i ^ ]) {res_ex = ; return;}
init_d2();
re2(i, n, m) {
x = w[E[i].a]; y = w[E[i].b];
if (x != y) add_edge2(y, x);
}
int front = , rear = -, front0, rear0; re(i, n2) {if (!de[i]) Q[++rear] = i; V2[i] = ;}
for (; front<=rear; front++) {
int i = Q[front], j, j0;
if (!V2[i]) {
V2[i] = ; front0 = ; rear0 = -;
re(k, n2) vst[k] = ;
re3(x, L[i], R[i]) {
j = w[sw[x] ^ ]; Q0[++rear0] = j; vst[j] = ;
}
for (; front0<=rear0; front0++) {
j = Q0[front0]; V2[j] = ;
for (int p=E2[j].next; p != j; p=E2[p].next) {
j0 = E2[p].b;
if (!vst[j0]) {Q0[++rear0] = j0; vst[j0] = ;}
}
}
}
for (int p=E[i].next; p != i; p=E[p].next) {
j = E[p].b; de[j]--;
if (!de[j]) Q[++rear] = j;
}
}
re(i, n) res[i] = ;
re(i, n2) if (V2[i] == ) re3(j, L[i], R[i]) res[sw[j]] = ;
}
int main()
{
int n0, m0, x1, x2, N1, N2;
char c1, c2;
while () {
scanf("%d%d", &n0, &m0); if (!n0 && !m0) break; else {n = n0 << ; init_d();}
re(i, m0) {
scanf("%d%c%d%c", &x1, &c1, &x2, &c2);
if (c1 == 'h') N1 = x1 << ; else N1 = (x1 << ) + ;
if (c2 == 'h') N2 = x2 << ; else N2 = (x2 << ) + ;
add_edge(N1 ^ , N2); add_edge(N2 ^ , N1);
}
add_edge(, );
solve();
if (res_ex) {
bool spc = ;
re(i, n) if (i != && res[i]) {
if (spc) putchar(' '); else spc = ;
printf("%d%c", i >> , i & ? 'w' : 'h');
}
puts("");
} else puts("bad luck");
}
return ;
}