博文
3SAT剩余子句块多解表示方法
|||
3-sat剩余子句块多解表示方法
姜咏江
使用子句消去法对3-SAT求解，最后会碰到剩余子句块多解的情况。如果我们只选择0和1表示，就会使那些很容易就得到的多解无法表出，为此需要引进确定了一个变量值后的剩余多解子句块的表示方法，这样一次可以获得更多的3SAT解表示。下面表1和表2中的$表示该变量值已经确定，上面一行是表示符号。
表1 剩余一个子句
表示： |
| v | v |
| t | t |
| k | k |
| q | q |
变量： | Xi | Xj | Xk | Xi | Xj | Xk | Xi | Xj | Xk | Xi | Xj | Xk |
剩值： | $ | 0 | 0 | $ | 1 | 1 | $ | 1 | 0 | $ | 0 | 1 |
vv表示xjxk的值是0*或*0, tt表示xjxk的值是1*或*1, kk表示xjxk的值是1*或*0, qq表示xjxk的值是0*或*1。“*”表示0或1。
表2 剩余2个子句
表示： |
| 2 | 2 |
| 3 | 3 |
| 2 | 2 |
| 3 | 3 |
变量： | Xi | Xj | Xk | Xi | Xj | Xk | Xi | Xj | Xk | Xi | Xj | Xk |
剩值： | $ | 0 | 0 | $ | 1 | 0 | $ | 1 | 1 | $ | 0 | 1 |
1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
22表示xjxk的值是01或10, 33表示xjxk的值是11或00。
这种表示一般只用于剩余的独立子句块，如若是多解的关联段，尚需设定值求解，到最后碰到此种情况方可使用。
需要说明，子句消去法并不能够一次性求出3SAT的全部解，除非3SAT只有唯一解和只有我们这里给出的表示法能够表出的那些解。这种多解表示法只是对剩余多解子句块运用的一种表示法，目的是在3SAT的一次求解中能够尽可能地表示出更多的解。
剩余只有3种子句的子句块一定有唯一解。剩余有4种类型子句的子句块一定无解。
2015-12-15
https://blog.sciencenet.cn/blog-340399-943455.html
上一篇：3SAT的子句消去法求解方法介绍
下一篇：多解的子句块关联段求解
