一种求解难SAT问题的改进DP算法  

A Modified DP Algorithm for Solving Hard SAT Problems

作　　者：徐云[1,2] 陈国良[1,2] 张国义[1,2] 

机构地区：[1]国家高性能计算中心 [2]中国科学技术大学计算机科学技术系,合肥230027

出　　处：《中国科学技术大学学报》2002年第3期358-362,共5页JUSTC

基　　金：国家"九七三"(G19980 30 40 3)资助项目

摘　　要：DP算法是求解SAT问题的最有效完全算法之一 ,论文分析和讨论了DP算法中的各种分枝文字策略 .并基于对不满足解数估计的方法 ,提出了一个有效的分枝文字策略 .实验结果表明 ,提出的改进DP算法对难SAT实例有较好的平均性能 .DP algorithm is one of the most efficient complete algorithms for solving SAT (satisfiability) problems. The branching literal strategy of DP algorithm is discussed and analyzed in this paper. Based on estimating the number of unsatisfiable solutions, an efficient strategy of branching literals is proposed. Experimental results demonstrate that the average computation time of hard SAT instances has been improved.

关 键 词：难SAT问题 改进DP算法 随机算法 不满足解数 NP完全问题 分支文字策略 可满足性问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]