姜咏江

SAT问题中最基本的是3-SAT。子句消去法可以在多项式时间完成对3-SAT求出满足解，但如何对具体的3-SAT求解达到最快？

依据子句消去法确定变量唯一解的基本规则，只要在k阶子句块中一个变量有2^k-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

这样就会立即得到表2，显然设定x16=1，那么所有的子句都会被消去。

表2

最后求出的满足解是：x20=0，x5=0，x4=0，x2=1，x9=0，x15=0，x16=1,其它变量值可以是0或1.

在SAT用子句消去法求解的过程中，只有找不到k阶子句块变量有2^k-1个相同的表现值时，才用子句消去法求有唯一可选解的变量，并将唯一可选解变量也用子句消去法消去。当所有剩下的变量都有2个可选解时，才从任何一个变量值设置开始，使用子句消去法消去那些剩余子句块变量值唯一子句，最后就能够一次性获得3-SAT的满足解。

2016/11/6