| 利用正交方法解SAT问题 |
| |
| 引用本文： | 荆明娥,陈更生,赵长虹,唐璞山,周电. 利用正交方法解SAT问题[J]. 复旦学报(自然科学版), 2008, 47(6) |
| |
| 作者姓名： | 荆明娥 陈更生 赵长虹 唐璞山 周电 |
| |
| 作者单位： | 复旦大学,专用集成电路国家重点实验室,上海,201203;复旦大学,专用集成电路国家重点实验室,上海,201203;E.E.Department,the University of Texas at Dallas,TX 75083,USA |
| |
| 基金项目： | 国家自然科学基金，中国博士后科学基金，上海市自然科学基金 |
| |
| 摘 要： | 提出了一种解决SAT问题的新算法.该算法首先定义了子句之间的正交关系;然后从消除子句之间的交叠信息出发,利用正交子句的特性,结合有效的简化技术,逐渐将问题简化为一组与原问题完全等价的正交子句组;最后,根据正交子句组对整个赋值空间的覆盖情况来判断SAT是否满足.该算法为SAT问题的解决提供了一个新的思路.
|
| 关 键 词： | 可满足性问题 卡诺图 正交子句 NP完全问题 |
Solving SAT Problems by Orthogonal Method |
| |
| JING Ming-e,CHEN Geng-sheng,ZHAO Chang-hong,TANG Pu-shan,ZHOU Dian. Solving SAT Problems by Orthogonal Method[J]. Journal of Fudan University(Natural Science), 2008, 47(6) |
| |
| Authors: | JING Ming-e CHEN Geng-sheng ZHAO Chang-hong TANG Pu-shan ZHOU Dian |
| |
| Abstract: | A novel algorithm for SAT problem is presented.Firstly,the orthogonal relation between the clauses is defined.Then,the algorithm utilizes the character of orthogonal clauses to eliminate the overlap information between clauses,and adopts effective simplification techniques to transform the SAT problem into an orthogonal clause group.Finally,the satisfiability of a SAT problem is verified by the covering of orthogonal clause group on the whole assignment space.Moreover,the algorithm provides a new idea for SAT problems other than the well-known DPLL and DP algorithms. |
| |
| Keywords: | SAT problem karnaugh orthogonal clause NP-complete problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
