博文
3SAT求解什么情况下可以确定变量只有惟一值？
|||
3SAT求解什么情况下可以确定变量只有惟一值？
用分段子句消去法去求解3SAT，关键是找出变量的惟一值。下面4种情况都可以惟一地确定逻辑变量的值。
1. 动态子句块只有一个变量需要确定值；
2. 动态子句块2个变量需要确定值，这两个变量刚好组成了3种不同子句；
例如下表1可惟一确定x3和x5的值。
表1
X1=1 | X2=0 | X3 | X4 | X5 |
0 |
| 0 |
| 0 |
| 1 | 1 |
| 0 |
1 | 1 |
| 1 |
3. 子句块一个变量值相同，其余2个变量有4种不同子句；
例如下表2的子句块必需确定x1=0
表2
X1 | X2 | X3 | X4 | X5 |
0 |
| 0 |
| 0 |
0 |
| 1 |
| 0 |
0 |
| 0 |
| 1 |
0 |
| 1 |
| 1 |
4. 最简单的是子句块有7个不同的子句。
例如下表3的变量必需取x1=0,x3=0,x5=0。
表3
X1 | X2 | X3 | X4 | X5 |
0 |
| 0 |
| 0 |
0 |
| 1 |
| 0 |
0 |
| 0 |
| 1 |
0 |
| 1 |
| 1 |
1 |
| 0 |
| 0 |
1 |
| 0 |
| 1 |
1 |
| 1 |
| 0 |
求3SAT的解要优先处理有4个子句一个变量同值的子句块，选定该变量值消去相应子句。
掌握住这几种确定变量惟一值的情况，用分段子句消去法求3SAT的解就会得心应手。
姜咏江
2015-11-4
https://blog.sciencenet.cn/blog-340399-933224.html
上一篇：研究生微体系结构课程
下一篇：3-SAT求解基本方法
