| 基于分支回溯的NAE-3SAT问题求解算法 |
| |
| 引用本文： | 谷文祥,傅琳璐,周俊萍,姜蕴晖. 基于分支回溯的NAE-3SAT问题求解算法[J]. 智能系统学报, 2012, 0(6): 506-511 |
| |
| 作者姓名： | 谷文祥 傅琳璐 周俊萍 姜蕴晖 |
| |
| 作者单位： | 东北师范大学计算机科学与信息技术学院;长春建筑学院基础教学部 |
| |
| 基金项目： | 国家自然科学基金资助项目(61070084,60803102);中央高校基本科研业务费专项资金资助项目(11QNJJ006);浙江师范大学计算机软件与理论省级重中之重学科开放基金资助项目(ZSDZZZZXK37) |
| |
| 摘 要： | NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效率.最后证明了算法在最坏情况下的时间复杂度上界为O(1.618n),其中n为公式中的变量数目.
|
| 关 键 词： | NAESAT NAE-3SAT 时间复杂性 NAE-3SAT问题上界 变量数目 分支回溯 |
Solution algorithm for the NAE-3SAT problem based on DPLL |
| |
| GU Wenxiang,FU Linlu,ZHOU Junping,JIANG Yunhui. Solution algorithm for the NAE-3SAT problem based on DPLL[J]. CAAL Transactions on Intelligent Systems, 2012, 0(6): 506-511 |
| |
| Authors: | GU Wenxiang FU Linlu ZHOU Junping JIANG Yunhui |
| |
| Affiliation: | 1(1.School of Computer Science and Information Technology,Northeast Normal University,Changchun 130117,China;2.Department of Basic Subjects Teaching,Changchun Architecture & Civil Engineering College,Changchun 130607,China) |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
|
