博文
3-SAT求解中几种无解情况及回避
|||
3-SAT求解中几种无解情况及回避
姜咏江
表格式给出的3-SAT用子句消去法求解很方便，但应该记住无解的情况。无解的情况有：
（1）有8个子句的子句块存在；
（2）两个相互关联的子句块，一个关联变量有0和1的值各4个；
（3）动态子句块不可避免的全2-SAT可选值；
（4）子句块中两个变量的值确定，无法避免第三个变量同时有0和1的值。
在这4种当中只有（3）和（4）需要先确定其它变量的值，因而是有可能避免的。我们在求解过程中首先要回避无解，然后求唯一解，连续唯一解过程碰到了不可解决的无解，则3-SAT无解。
快速求解练习1：
X1 | X2 | X3 | X4 | X5 | X6 |
0 | 0 | 0 |
|
|
|
1 | 0 | 0 |
|
|
|
0 | 1 | 0 |
|
|
|
1 | 1 | 0 |
|
|
|
0 | 0 | 1 |
|
|
|
0 |
|
| 0 |
| 0 |
1 |
|
| 0 |
| 0 |
0 |
|
| 0 |
| 1 |
0 | 1 |
| 1 |
|
|
|
| 0 | 0 | 0 |
|
|
| 1 | 0 | 0 |
|
|
| 0 | 1 | 0 |
|
|
| 1 | 1 | 0 |
|
|
| 0 | 0 | 1 |
|
|
|
| 0 | 0 | 0 |
|
|
| 1 | 0 | 0 |
|
|
| 0 | 1 | 0 |
|
|
| 1 | 1 | 0 |
|
|
| 0 | 0 | 1 |
| 0 |
| 1 |
| 1 |
| 1 |
| 0 |
| 1 |
| 1 |
| 1 |
| 1 |
快速求解练习2：
X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 |
0 | 0 | 1 |
|
|
|
|
|
|
|
1 | 0 | 1 |
|
|
|
|
|
|
|
0 | 1 | 1 |
|
|
|
|
|
|
|
1 | 1 | 0 |
|
|
|
|
|
|
|
1 | 1 | 1 |
|
|
|
|
|
|
|
0 |
|
| 0 |
| 0 |
|
|
|
|
1 |
|
| 0 |
| 0 |
|
|
|
|
0 |
|
| 0 |
| 1 |
|
|
|
|
0 | 1 |
| 1 |
|
|
|
|
|
|
|
| 0 | 1 | 0 |
|
|
|
|
|
|
| 1 | 0 | 0 |
|
|
|
|
|
|
| 1 | 1 | 0 |
|
|
|
|
|
|
| 0 | 1 | 1 |
|
|
|
|
|
|
| 1 | 1 | 1 |
|
|
|
|
|
|
|
| 0 | 0 | 0 |
|
|
|
|
|
|
| 0 | 1 | 0 |
|
|
|
|
|
|
| 0 | 0 | 1 |
|
|
|
|
| 0 |
| 1 |
| 1 |
|
|
|
|
| 1 |
| 0 |
| 1 |
|
|
|
|
| 1 |
| 1 |
| 1 |
|
|
|
|
| 0 |
| 0 |
| 1 |
|
|
|
|
|
|
|
|
| 1 | 1 | 0 | ||
|
|
|
|
| 1 | 1 | 1 | ||
|
|
|
|
| 0 | 1 | 1 | ||
|
|
|
|
|
| 0 |
| 0 | 1 |
|
|
|
|
|
| 1 |
| 0 | 1 |
|
|
|
|
|
| 0 |
| 1 | 1 |
|
|
|
|
|
| 1 |
| 1 | 1 |
参考：http://blog.sciencenet.cn/blog-340399-928224.html
2015-11-29
https://blog.sciencenet.cn/blog-340399-939648.html
上一篇：如今该如何给科学家下定义？
下一篇：谈3SAT特殊的唯一解
