博文
3SAT的子句消去法求解方法介绍
|||
3SAT的子句消去法求解方法介绍
姜咏江
子句消去法求解用0和1表示的3SAT问题简单易学。这里以简单的例子来说明解法。
1. 独立子句块
由逻辑变量x1,x2,x3构成的3SAT有最多有8个子句，将其用阵列表示，即为表1所示。
表1子句块
序号 | x1 | x2 | x3 |
1 | 0 | 0 | 0 |
2 | 1 | 0 | 0 |
3 | 0 | 1 | 0 |
4 | 1 | 1 | 0 |
5 | 0 | 0 | 1 |
6 | 1 | 0 | 1 |
7 | 0 | 1 | 1 |
8 | 1 | 1 | 1 |
子句消去法的要点是将变量设定0或1的值，并将表中有这个值的子句全消去。如果全部变量值设定之后，表中无子句，则设定的变量值向量就是这个3SAT的解，如有剩余子句存在，则此3SAT无满足解。
从表1中可见我们无法确定x1,x2,x3为何值能够把这些子句全消去。由3个变量形成的子句叫子句块，3SAT子句块中子句数为8，那么这个3SAT一定无满足解。
将表1的子句随便删除一个（如有底纹一行），就构成了7个子句的子句块，这种子句块一定有唯一解。确定解的办法简单：
（1）选中有4个相同值的变量，并让该变量取这个值（x3=0，这是必选值，不然无解）。
（2）剩余子句块如表2 所示。在x3=0的情况下，只有选x1=1和x2=0才能够将这3个子句全部消去（变量选值最多的数码）。
表2 剩余子句块
序号 | x1 | x2 | x3 |
5 | 0 | 0 | 1 |
6 | 1 | 0 | 1 |
8 | 1 | 1 | 1 |
小结：有7个子句的子句块有唯一解。只要子句块有一个变量有4个相同值，就必选。子句数不足7的子句块必有多解。子句块解的数量为8-（块子句数）。
例如，表3可以有6个解｛100、010、001、101、011、111｝（操作时选x3＝1即可）。
表3 多解子句块
序号 | x1 | x2 | x3 |
1 | 0 | 0 | 1 |
2 | 1 | 1 | 1 |
2. 避免关联子句块无解
有共同变量的子句块形成关联段。3SAT求解要先求出唯一解子句块的解，这些块解求出来之后，会剩下一些相互关联的多解子句块。如果这些多解的关联子句块出现了表4的情况，那么必定产生无解。
表4 剩余关联多解子句块
序号 | x1=0 | x2 | x3 | x4=1 | x5=0 |
1 | 1 | 0 | 0 |
|
|
2 | 1 | 0 | 1 |
|
|
3 |
| 1 | 0 | 0 |
|
4 |
| 1 | 1 | 0 |
|
5 |
| 0 | 0 |
| 1 |
6 |
| 1 | 0 |
| 1 |
如果在此之前x1,x4,x5的值都是通过求唯一解的过程得到的，那么可以断定此3SAT无解。在求解中这些先确定的值变动一下能够避免图4中的有色的4个二进制数出现，那么就可以继续设定变量值求解。
一般的3SAT都有多解。子句消去法一次可以求出部分解，少数情况下可以一次求出全部解。
参考：http://blog.sciencenet.cn/blog-340399-928224.html
2015-12-11
https://blog.sciencenet.cn/blog-340399-942538.html
上一篇：悬赏百万美元千禧难题有了新进展
下一篇：3SAT剩余子句块多解表示方法
