现在的位置: 首页 > 综合 > 正文

2-sat问题

2017年12月12日 ⁄ 综合 ⁄ 共 5820字 ⁄ 字号 小 中 大 ⁄ 评论关闭

2-sat问题

2013
年 02 月 02 日 isnowfy algorithm

Go
to comment

Implication_graph

在这篇文章我们提到过sat问题，sat问题是第一个npc问题，具体是这样的SAT全称是satisfiability，他是问对于一个合取范式，是否有一种输入使得他的输出是1，具体点就是类似这样的布尔表达式（x1
or x2 or x3）and(x3 or x4)and(not x1 or x5)对于所有的x是否有一种01取值，使得最后的结果是1。而2-sat问题就是每一个由or连接的子式都只包含两个变量，比如这样(x1 or x2) and (not x3 or x1)，2-sat问题是有多项式解法的，而3-sat就是npc问题了，前段时间有人宣称证明了p=np就是因为他自己找到了3-sat的多项式解法，当然最后被证明解法是错误的。。。那么对于2-sat问题解法而言，经典的就是利用强连通分支的算法来解决，最近上的coursera上的algo2有个随机算法也很有趣这里我们也要讲一下。

先来看经典的利用强连通分支的图论解法。我们把每个变量x都拆成2个点，两个点x和~x分别表示这个点取1和这个点取0，所以最后我们就是在这2n个点中选择满足要求的n个点。对于每个子式，假设子式是(x1 or x2)，对于2-sat问题而言我们需要每个子式都得1，也就是对于这个子式而言，x1和x2至少要取一个，对应于图中就是，如果我们取~x1就必须取x2，取~x2就必须取x1，所以我们就在图中从~x1到x2和从~x2到x1连两条有向边。同样的如果子式中有not也是类似方法，比如(not x1 or x2)那么就是X1到x2和~x2到~x1两条有向边。一开始的图片构成的图表示的这个式子。

(x0∨x2)∧(x0∨¬x3)∧(x1∨¬x3)∧(x1∨¬x4)∧(x2∨¬x4)∧(x0∨¬x5)
∧(x1∨¬x5)∧(x2∨¬x5)∧(x3∨x6)∧(x4∨x6)∧(x5∨x6)

构建好图之后对图求强连通分支，很显然的如果xi和~xi在同一个强连通分支中那么就是不存在解的。之后进行染色判定，强连通分支缩点之后，把所有的边反向，然后按照拓扑排序的顺序遍历节点，如果节点没有被染色，就涂成红色，然后把和这个点互斥的点（所谓互斥的点就是如果x和~x所在的点），以及这个点的子孙都涂成蓝色，这样取出红色的点就是满足条件的解。这里就不证明了，详细的可以看伍昱的《由对称性解2-SAT问题》和赵爽的《2-SAT解法浅析》两篇。看证明的时候注意对称性，就是说如果x，y在同一个连通分支，那么~x，~y也在同一个连通分支，如果x到y有路，那么~y到~x也有路，注意这个对称性的特点的话，那两篇文章里的证明也就不难看懂了。

talk is easy，show me the code，那么让我们看一下代码吧，这里就用poj 3648来举例。

  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. const int maxn=10010;
  5. int n, m, nxt[maxn],
    head[maxn],
    pnt[maxn],
    ne, e, a, b, a0, b0;
  6. char c1, c2;
  7. int nnxt[maxn],
    nhead[maxn],
    npnt[maxn];
  8. int order[maxn],
    norder, id[maxn],
    v[maxn];
  9. int ans[maxn],
    op[maxn];
  10.  
  11. void dfs(int d){
  12.     v[d] = 1;
  13.     for(int i=head[d];
    i!=-1;
    i=nxt[i])
  14.         if(!v[pnt[i]])
  15.             dfs(pnt[i]);
  16.     order[norder++] = d;
  17. }
  18. void ndfs(int d, int k){
  19.     v[d] = 1;
  20.     id[d] = k;
  21.     for(int i=nhead[d];
    i!=-1;
    i=nnxt[i])
  22.         if(!v[npnt[i]])
  23.             ndfs(npnt[i],
    k);
  24. }
  25. void addedge(int s, int t){
  26.     pnt[e] = t;
    nxt[e] = head[s];
    head[s] = e++;
  27. }
  28. void addnedge(int t, int s){
  29.     npnt[ne] = s;
    nnxt[ne] = nhead[t];
    nhead[t] = ne++;
  30. }
  31. void color(int d){
  32.     ans[d] = 2;
  33.     for(int i=head[d];
    i!=-1;
    i=nxt[i])
  34.         if(!ans[pnt[i]])
  35.             color(pnt[i]);
  36. }
  37. int main(){
  38.     while(1){
  39.         norder = e = ne = 0;
  40.         memset(head, -1, sizeof head);
  41.         memset(nhead, -1, sizeof nhead);
  42.         scanf("%d%d", &n, &m);
  43.         if(!n&&!m)
  44.             break;
  45.         for(int i=0;
    i<m; ++i){
  46.             scanf("%d%c%d%c", &a, &c1, &b, &c2);
  47.             if(c1=='h')
  48.                 a0 = n+a;
  49.             else{
  50.                 a0 = a;
  51.                 a += n;
  52.             }
  53.             if(c2=='h')
  54.                 b0 = n+b;
  55.             else{
  56.                 b0 = b;
  57.                 b += n;
  58.             }
  59.             addedge(a0, b);
  60.             addnedge(b, a0);
  61.             addedge(b0, a);
  62.             addnedge(a, b0);
  63.         }
  64.         addedge(0,
    n);
  65.         addnedge(n, 0);
  66.         memset(v, 0, sizeof v);
  67.         for(int i=0;
    i<2*n; ++i)
  68.             if(!v[i])
  69.                 dfs(i);
  70.         int k=0;
  71.         memset(v, 0, sizeof v);
  72.         memset(id, -1, sizeof id);
  73.         for(int i=norder-1;
    i>=0; --i)
  74.             if(!v[order[i]])
  75.                 ndfs(order[i],
    k++);
  76.         int mark = 1;
  77.         for(int i=0;
    i<n; ++i)
  78.             if(id[i]==id[i+n])
  79.                 mark = 0;
  80.         if(!mark){
  81.             printf("bad
    luck\n"    );
  82.             continue;
  83.         }
  84.         for(int i=0;
    i<n; ++i){
  85.             op[id[i]] = id[i+n];
  86.             op[id[i+n]] = id[i];
  87.         }
  88.         e = norder = 0;
  89.         memset(head, -1, sizeof head);
  90.         memset(v, 0, sizeof v);
  91.         memset(ans, 0, sizeof ans);
  92.         for(int i=0;
    i<n; ++i)
  93.             for(int j=nhead[i];
    j!=-1;
    j=nnxt[j])
  94.                 addedge(id[i],
    id[npnt[j]]);
  95.         for(int i=0;
    i<k; ++i)
  96.             if(!v[i])
  97.                 dfs(i);
  98.         for(int i=norder-1;
    i>=0; --i)
  99.             if(!ans[order[i]]){
  100.                 ans[order[i]] = 1;
  101.                 color(op[order[i]]);
  102.             }
  103.         for(int i=1;
    i<n; ++i){
  104.             if(ans[id[i]] == 1)
  105.                 printf("%dh",
    i);
  106.             else
  107.                 printf("%dw",
    i);
  108.             if(i<n-1)
  109.                 printf("
    "    );
  110.             else
  111.                 printf("\n");
  112.         }
  113.     }
  114.     return 0;
  115. }

代码自我感觉还是比较清晰的就不解释了，整个过程就是按照上面说的算法进行的。ok，到这里而言acmer的内容已经足够了，下面我们来说说algo2里提到的随机算法。

在讲随机算法之前，首先要介绍“random walks on a line”，假设我们在数轴的点0的位置，在点0的话，下一个时刻我们会移动到点1上，如果在其他的点x，我们有50%的概率下一个时刻移动到点x-1上，有50%的概率移动到x+1上。现在让我们来算一下，从点0开始移动到点n，期望需要移动多少步。这个期望的算法和之前写的这篇的方法差不多。设E(i)是从点i(i<=n)移动到点n所需要的期望的步数。于是我们有

E(n)=0
E(0)=E(1)+1
E(i)=0.5∗(1+E(i+1))+0.5∗(1+E(i−1))

有上面的式子我们可以得到最后的结果，推导比较简单，就不赘述了

E(0)=n2

设Tn表示从0走到n的步数，于是我们有

n2=E(Tn)=∑2n2k=0(k∗P(Tn=k))+∑∞k=2n2+1(k∗P(Tn=k))
因为∑2n2k=0(k∗P(Tn=k))≥0
所以n2≥∑∞k=2n2+1(k∗P(Tn=k))
≥∑∞k=2n2+1((2n2)∗P(Tn=k))
=2n2∗P(Tn>2n2)

于是我们得到

P(Tn>2n2)≤12

也就是说我们从0开始走2*n*n步，我们有大于1/2的概率已经经过n这个点了。

ok回到我们的2-sat问题。

我们的算法是这样的，我们开始时随机给变量赋值0或者1，然后迭代足够多的次数（大于2*n*n的次数），如果某次迭代，我们找到了答案就可以返回结果了，如果我们迭代足够多的次数都没找到答案就返回无解。每次迭代，我们找一个不满足要求的子式，然后两个变量随机挑一个改变他的值。

假设我们现在的解是a，满足要求的解是a*，那么我们的解和满足要求的解，值不同的变量的个数是x，某次迭代，我们找到一个子式(xi or xj)不满足条件，因为子式不满足条件，所以xi和xj不可能同时和a*里值是相同的，如果两个值都不同，那么我们这次改动使得x=x-1，如果有一个值不同，那么我们有50%的概率使得x=x-1有50%的概率使得x=x+1，所以，答案变好的概率要大于50%，所以迭代2*n*n次能得到解的概率就会小于1/2。

很有趣的算法，并且我们用这个算法，可以AC掉poj 3648这道题！看代码

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <ctime>
  5.  
  6. const int maxn=10010;
  7. int n, m, a, b;
  8. char c1, c2;
  9. int ans[maxn],
    record[maxn][2];
  10.  
  11. int get(int x){
  12.     if(x<n)
  13.         return ans[x];
  14.     return !ans[x-n];
  15. }
  16. int main(){
  17.     //srand(time(NULL));这里如果调用time，poj会报 runtime error的错误
  18.     srand(7);
  19.     while(1){
  20.         scanf("%d%d", &n, &m);
  21.         memset(ans, 0, sizeof ans);
  22.         if(!n&&!m)
  23.             break;
  24.         for(int i=0;
    i<m; ++i){
  25.             scanf("%d%c%d%c", &a, &c1, &b, &c2);
  26.             if(c1=='w')
  27.                 a += n;
  28.             if(c2=='w')
  29.                 b += n;
  30.             record[i][0] = a;
  31.             record[i][1] = b;
  32.         }
  33.         int mark = 0;
  34.         for(int i=0;
    i<5*n*n; ++i){
  35.             mark = 1;
  36.             for(int j=0;
    j<m; ++j)
  37.                 if((record[j][0]%n!=record[j][1]%n)&&!(get(record[j][0])||get(record[j][1]))){
  38.                     int tmp = rand()%2;
  39.                     if(record[j][0]%n==0)
  40.                         tmp = 1;
  41.                     if(record[j][1]%n==0)
  42.                         tmp = 0;
  43.                     ans[record[j][tmp]%n] = 1-ans[record[j][tmp]%n];
  44.                     mark = 0;
  45.                     break;
  46.                 }
  47.             if(mark)
  48.                 break;
  49.         }
  50.         if(!mark){
  51.             printf("bad
    luck\n"    );
  52.             continue;
  53.         }
  54.         for(int i=1;
    i<n; ++i){
  55.             if(ans[i])
  56.                 printf("%dh",
    i);
  57.             else
  58.                 printf("%dw",
    i);
  59.             if(i<n-1)
  60.                 printf("
    "    );
  61.             else
  62.                 printf("\n");
  63.         }
  64.     }
  65.     return 0;
  66. }

记得之前gcj曾经有道题目需要用到生日悖论来解决，感觉和这个随机算法都是很有趣的算法阿。

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞