基于寻找可满足2-SAT子问题的SAT算法

• 作者: 傅阳春 周育人
• 来源期刊: 计算机应用研究
• 关键词: SAT问题 2-SAT子问题 2-SAT算法
• 年，卷（期）: 2010,（2）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 462-464
• 页数: 3页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2010.02.015

摘要

可满足问题(SAT)是一个NP-Hard问题.提出了一种求解SAT的新算法(FFSAT).该算法将SAT问题转换为寻找一个可满足的2-SAT子问题.SAT问题虽然是NP完全问题,但是当所有子句长度不大于2时,SAT问题可以在线性时间求解.使用2-SAT算法-BinSat求解2-SAT子问题,当它不满足时,根据赋值选择新的2-SAT子问题.实验结果表明,采用本算法的结果优于UnitWalk.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周育人	华南理工大学计算机科学与工程学院	26	561	9.0	23.0
2	傅阳春	华南理工大学计算机科学与工程学院	1	3	1.0	1.0