第3期 谷文祥，等：最坏情况下Min-2SAT问题的上界 ·243· 定理112】设分支树T的根结点标记为公式 b)如果&=false,B=tue,则返回Simplipy F,则分支树T中叶子的个数不超过(rm),其中 （Fx1=7x2]). (F)是公式F中子句的数目或变量的数目. c)如果a=true,B=false,则返回Simplipy 由分支树的定义可以看出，分支树的构造过程相 (F[x1=2]). 当于基于DPLL(Dais-Putnam-Logemann-Loveland)算 d)如果a&=true,B=true,则返回Simplipy 法的执行过程.算法逐一对公式F中的变量进行赋值， (F[x1]). 直到确定任意一个赋值满足或不满足公式F为止.假 对于给定的范式，重复使用化简算法 设基于DPL的算法在分支树T中任意一个结点执行 Simplify(F)对其进行化简，直到范式不能再应用算 的操作都是多项式的，那么从子句数目的角度考虑，算 法中任何一条化简规则为止.这样在求解Min-2SAT 法的执行时间t为 问题时可以减少算法需要考虑的情况，以减弱算法 t≤#{To}x ploy(F:)≤ 的复杂性。 (2×(#{1Tees})-1)×ploy(F:)≤ 根据化简规则，可以得到下面的引理。 (rmm)m×ploy(F:). 引理1令F是一个2-CNF范式，F'= 若从变量数目的角度考虑，算法的执行时间t为 Simplify(F),则F'中不包含度至多为2的变量. t≤#{Tde}x ploy(F:)≤ 证明若变量的度为1，则可通过化简算法 (2×(#{Tme})-1)×ploy(F:)≤ Simplify(F)中化简规则2)对其化简；若变量的度为 (rmm)"×ploy(F:) 2,则可通过化简规则4)进行化简.因此公式化简后 用F表示2-CNF公式，用N,(F)表示在公式F 只包含度至少为3的变量. 的2子句中出现次的变量的个数.很容易得到 引理2令F是化简后的公式，a、x是邻居，a K(P)=∑xX(P 的度为3，则在F[x]和F[x]中，至少有一个化简 2 规则会对a赋值. 式中：K2(F)表示F中2-子句的数目.根据文献 证明考虑变量a所有可能出现的情况. [13]可以对其稍作修改，得到新的复杂性测度为 1)当(aVx)∧(aVx1)∧(aVx2)时，若x= =(D+Lw(回+四xX9 0,则由化简规则3)可知a=1. 2 2)当(aVx)∧(aV1)∧(aVx2)时，若 2化简规则 x=1,则由化简规则2)可知a=0. 3)当(aVx)(aVx)A(aVx2)Aa时，若 在给出求解Min-2SAT问题的算法之前，首先 x=0,则由化简规则1)可知消除了a和一a,再由化 给出一个化简算法如下， 简规则2)可知a=1. 化简算法Simplify(F) 4)当(aVx)A(aVx1)∧(aVx2)AaAa 输入：一个2-CNF范式F. 时，若x=1,则由化简规则3)可知a=0. 输出：一个化简后的2-CNF范式F. 5)当(aVx)A(aVx1)∧(aVx2)Aa时， 1)如果F=FU{C,D},并且对于一个文字L 若x=1,则由化简规则3)可知a=0. 有C\{l}=D\{l},则返回Simplipy(FoU{C\{l, 6)当(aVx)∧(aVx1)∧(aVx2)∧a时， T}) 若x=0,则由化简规则3)可知a=1. 2)如果F中存在一个文字1满足#(F,)= 由于公式F已化简，所以不存在其他情况，引 0,则返回Simplipy(F[l]). 理得证 3)如果F中存在一个文字1满足#(F,)≥ #(F,I),则返回Simplipy(F[l]). 3算法MinSATAlg 4)如果F中存在2个变量x1和x2,并且1至 本文给出一个求解Min-2SAT问题的算法Min- 多出现在一个不含x2的2-字句中，令α和B分别为 SATAlg,它是一个典型的分支算法.具体算法描述 F[x2]和F[2]中通过化简规则对1所赋的布尔 如下. 值(tue或者false),则根据&和B的值将公式F化 输人：一个2-CNF范式F. 简的方法为： 输出：PesVal(F). a)如果a=false,B=false,则返回Simplipy 1)F=Simplify(F). (F[x]) 2)如果F只包含T字句，则返回L(F)