博文
多解的子句块关联段求解
|||
多解的子句块关联段求解
姜咏江
都是多解的子句块形成的关联段，求解时要先解决有可能形成无解的情况。表1中可能形成无解的情况只有底纹暗色的部分，那么选取x1和x4及x5的值，就要注意不能够产生无解的剩余子句块。
图1中用子句消去法若选择x1＝1，x4＝1就会出现无解的情况。因而求解中要避开无解。
表1 多解的子句块关联
|
|
|
|
|
|
|
|
|
|
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 |
0 | 0 | 0 |
|
|
|
|
|
|
|
0 | 0 | 1 |
|
|
|
|
|
|
|
1 | 1 | 0 |
|
|
|
|
|
|
|
1 | 1 | 1 |
|
|
|
|
|
|
|
| 1 | 0 | 1 |
|
|
|
|
|
|
| 1 | 0 | 0 |
|
|
|
|
|
|
| 1 | 1 | 0 |
|
|
|
|
|
|
| 1 | 1 | 1 |
|
|
|
|
|
|
| 0 | 0 |
| 0 |
|
|
|
|
|
| 1 | 0 |
| 0 |
|
|
|
|
|
|
|
| 0 | 0 |
| 1 |
|
|
|
|
|
| 0 | 1 |
| 1 |
|
|
|
|
|
| 0 | 0 | 0 |
|
|
|
|
|
|
|
| 1 | 1 | 0 |
|
|
|
|
|
|
| 0 | 1 | 1 |
|
|
|
|
|
|
|
|
| 1 | 1 | 1 |
|
|
|
|
|
|
|
| 0 | 0 | 1 |
|
|
|
|
|
|
| 1 | 0 | 0 |
这个问题中，只要选择x1＝0，就进入了可解状态。
显然，多解子句块间有两个变量相互关联段才有可能出现无解的情况，而只有一个变量关联的多解子句块间不会形成无解。
2015-12-15
https://wap.sciencenet.cn/blog-340399-943506.html
上一篇：3SAT剩余子句块多解表示方法
下一篇：详解3SAT归约到子集和问题的方法
