CAJ | 학술논문

结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策.该算法引导完全算法优先搜索近似解所在的子空间,加速解决器找到可满足解的过程,为SAT问题的求解提供了一种新的有效途径.实验结果表明,该算法有效地提高了决策的精度和SAT解决器的效率,对很多实例非常有效.
결합DPLL완전산법능구증명가만족성(SAT)문제적불가만족성화국부수색산법쾌속적우점,제출이용근사해가속구해SAT문제적계발식완전산법.수선이용국부수색산법쾌속지득도일개근사해,병장해근사해작위완전산법적초시수입,용우기중분지변량적상위결책.해산법인도완전산법우선수색근사해소재적자공간,가속해결기조도가만족해적과정,위SAT문제적구해제공료일충신적유효도경.실험결과표명,해산법유효지제고료결책적정도화SAT해결기적효솔,대흔다실례비상유효.