基于分支回溯的NAE-3SAT问题求解算法

• 作者: 傅琳璐 周俊萍 姜蕴晖 谷文祥
• 来源期刊: 智能系统学报
• 学科: 工学
• 关键词: NAESAT NAE-3SAT 时间复杂性 NAE-3SAT问题上界 变量数目 分支回溯
• 年，卷（期）: 2012,（6）
• 页码范围: 506-511
• 页数: 6页
• 分类号: TP301
• 字数: 5617字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-4785.201206010

摘要

NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效率.最后证明了算法在最坏情况下的时间复杂度上界为O(1.618n),其中n为公式中的变量数目.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周俊萍	东北师范大学计算机科学与信息技术学院	10	82	4.0	9.0
2	谷文祥	东北师范大学计算机科学与信息技术学院	71	538	11.0	20.0
6	傅琳璐	东北师范大学计算机科学与信息技术学院	2	0	0.0	0.0
7	姜蕴晖	东北师范大学计算机科学与信息技术学院	3	2	1.0	1.0