|||
姜咏江
SAT问题中最基本的是3-SAT。子句消去法可以在多项式时间完成对3-SAT求出满足解,但如何对具体的3-SAT求解达到最快?
依据子句消去法确定变量唯一解的基本规则,只要在k阶子句块中一个变量有2k-1个相同的表现值,那么这个表现值就是这个变量的解。3-SAT的子句块最高是3阶,在消去子句的过程中会剩下2阶或1阶子句。因而任何时候,3阶子句块变量有4个相同的表现值,2阶子句块中变量有2个相同的表现值,或者一个变量只有唯一的表现值,那么这时都可以用表现值作为变量的解。
例如, SAT=(x1+x20’)(x1’+x20’)(x1+x4’+x6’) (x1’+x4’+x6) (x1+x4’+x6) (x1’+x4’+x6’) (x2+x4’) (x2+x4)x5’) (x9+x15’)(x9’+x15’) (x9’+x15) (x11’+x13+x16) (x11+x13’+x16) (x11+x13+x16)
用0和1表示这个SAT就如表1所示。
下面的表1,SAT出现了1,2,3阶子句块,这时可从子句块中找到x20=0,x5=0,x4=0,x2=1,x9=0,x15=0。
表1
| 1 | 0 | 0 |
| 0 |
|
| 0 |
| 0 |
x1 | x2 | x4 | x5 | x6 | x9 | x11 | x13 | x15 | x16 | x20 |
1 |
| 0 | ||||||||
0 |
|
|
| 0 | ||||||
1 | 0 |
| 0 | |||||||
0 |
| 0 | 1 | |||||||
1 | 0 | 1 | ||||||||
0 | 0 | 0 | ||||||||
| 1 | 0 | ||||||||
| 1 | 1 | ||||||||
|
|
| 0 |
|
|
|
|
|
|
|
| 1 | 0 | ||||||||
| 0 | 0 | ||||||||
|
| 0 | 1 | |||||||
|
|
|
|
| 0 | 1 | 1 | |||
|
|
|
|
| 1 | 0 | 1 | |||
|
|
|
|
| 1 | 1 | 1 |
这样就会立即得到表2,显然设定x16=1,那么所有的子句都会被消去。
表2
| 1 | 0 | 0 |
| 0 |
|
| 0 |
| 0 |
x1 | x2 | x4 | x5 | x6 | x9 | x11 | x13 | x15 | x16 | x20 |
|
|
|
|
| 0 | 1 | 1 | |||
|
|
|
|
| 1 | 0 | 1 | |||
|
|
|
|
| 1 | 1 | 1 |
最后求出的满足解是:x20=0,x5=0,x4=0,x2=1,x9=0,x15=0,x16=1,其它变量值可以是0或1.
在SAT用子句消去法求解的过程中,只有找不到k阶子句块变量有2k-1个相同的表现值时,才用子句消去法求有唯一可选解的变量,并将唯一可选解变量也用子句消去法消去。当所有剩下的变量都有2个可选解时,才从任何一个变量值设置开始,使用子句消去法消去那些剩余子句块变量值唯一子句,最后就能够一次性获得3-SAT的满足解。
2016/11/6
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-26 00:23
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社