| 一种求解难SAT问题的改进DP算法 |
| |
| 引用本文： | 徐云,陈国良,张国义. 一种求解难SAT问题的改进DP算法[J]. 中国科学技术大学学报, 2002, 32(3): 358-362 |
| |
| 作者姓名： | 徐云 陈国良 张国义 |
| |
| 作者单位： | 国家高性能计算中心(合肥)中国科学技术大学计算机科学技术系,合肥,230027 |
| |
| 基金项目： | 国家“九七三”(G19980 30 40 3)资助项目 |
| |
| 摘 要： | DP算法是求解SAT问题的最有效完全算法之一，论文分析和讨论了DP算法中的各种分枝文字策略，并基于对不满足解数估计的方法，提出了一个有效的分枝文字策略，实验结果表明，提出的改进DP算法对难SAT实例有较好的平均性能。
|
| 关 键 词： | 难SAT问题 改进DP算法 随机算法 不满足解数 NP完全问题 分支文字策略 可满足性问题 |
| 文章编号： | 0253-2778(2002)03-0358-05 |
A Modified DP Algorithm for Solving Hard SAT Problems |
| |
| XU Yun,CHEN Guo-liang,ZHANG Guo-yi. A Modified DP Algorithm for Solving Hard SAT Problems[J]. Journal of University of Science and Technology of China, 2002, 32(3): 358-362 |
| |
| Authors: | XU Yun CHEN Guo-liang ZHANG Guo-yi |
| |
| Abstract: | 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. |
| |
| Keywords: | satisfiability problem hard SAT instance randomized algorithms number of unsatisfiable solutions |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
