分段子句消去法求解的要点

姜咏江

3-SAT问题的子句分段消去法实际上是一种局部降阶的方法，其本质是将3-SAT转化为2-SAT或1-SAT求解。用数码表示的2-SAT只有4种子句，这种变量相同的子句组成了子句块。表1左面两列是子句的数值表达方式，右面一列是文字表达方式。

表1  2阶子句块

这4种子句同时出现在2-SAT中，自然找不到逻辑变量x、y的满足这些子句值都是1的解。但如果这4个子句中仅出现3个，那么我们就可以确定这个子句块有惟一的一组变量值使3个子句的值都是1。如果子句块只出现1个或2个子句，那么这个子句块就有两组值使这1个或2个子句的值都是1。

如果是3-SAT的子句块，则出现8个子句一定无块解。确定了一个变量值的3-SAT动态块实际上是一个2-SAT的子句块，因而可以按照2-SAT子句块求解。

对于确定了2个变量的动态块，相当于1-SAT子句块，这时只要这个变量值出现了不同，那么就肯定无解。

对于高阶的k-SAT，我们可以依据这种降阶的方法求解。先从有唯一解的子句块开始设定变量值，通过子句消去法得到降阶的动态块，再依据降阶法求解。

若子句关联段有多解，要将其解全部求出，然后与其它关联段解组合，这样才能够得到3-SAT 的全部满足解。

分段子句消去法：http://blog.sciencenet.cn/blog-340399-928224.html

2015-10-17