| 可满足性问题全部解的求解算法 |
| |
| 引用本文： | 毕忠勤,陈光喜,单美静.可满足性问题全部解的求解算法[J].计算机工程与应用,2009,45(3):35-37. |
| |
| 作者姓名： | 毕忠勤 陈光喜 单美静 |
| |
| 作者单位： | 1. 华东师范大学,上海市高可信计算重点实验室,上海,200062
2. 桂林电子科技大学,数学与计算科学学院,广西,桂林,541004 |
| |
| 基金项目： | 国家重大基础研究计划项目，华东师范大学优秀沣博士研究生培养基金 |
| |
| 摘 要： | SAT问题在人工智能、计算机基础理论研究和人工智能等领域有着广泛的应用,近年来,证明该问题的可满足性取得了巨大的成功,但在求出SAT问题的所有解方面还有待进一步研究。利用一个简单的变换,将可满足性(SAT)问题转化为多项式形式,然后根据命题逻辑的性质以及多项式的性质,得到一个求解出SAT问题所有解的算法。实验结果显示该算法是有效和可行的
|
| 关 键 词： | 可满足性问题 局部搜索 多项式扩展 自动求解 |
| 收稿时间： | 2008-9-10 |
| 修稿时间： | 2008-10-16
|
Algorithm for finding all-solutions of satisfiablity problem |
| |
| BI Zhong-qin,CHEN Guang-xi,SHAN Mei-jing.Algorithm for finding all-solutions of satisfiablity problem[J].Computer Engineering and Applications,2009,45(3):35-37. |
| |
| Authors: | BI Zhong-qin CHEN Guang-xi SHAN Mei-jing |
| |
| Affiliation: | BI Zhong-qin1,CHEN Guang-xi2,SHAN Mei-jing11.Shanghai Key Laboratory of Trustworthy Computing,East China Normal University,Shanghai 200062,China 2.School of Mathematics & Computational Science,Guilin University of Electronic Technology,Guilin,Guangxi 541004,China |
| |
| Abstract: | Satisfiability problem has been widely used in many fields such as artificial intelligence,computer theory research and computation theory.Many algorithms about this NP-hard problem have been built,but how to get all of the truth assignments is still difficult.By establishing the correspondence between the primitive operation in polynomial and clause solution in SAT,an ef- ficient algorithm has been built to obtain all solutions which satisfied the problem.Experiment shows that the new algorithm is feasible... |
| |
| Keywords: | Sattifiability（SAT） problem local search polynomial expanding automatic solve |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
