|||
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
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-27 08:29
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社