SA T问题中隐蔽集求解的改进

• 作者: 李淑霞 谷文祥 龚茜茹
• 来源期刊: 微电子学与计算机
• 关键词: SAT问题 隐蔽集 隐藏结构 最小隐蔽集 隐蔽集变量
• 年，卷（期）: 2014,（7）
• 页码范围: 65-68
• 页数: 4页
• 分类号: TP18
• 语种: 中文

摘要

隐蔽集（backdoor sets）作为隐藏结构的一种，能有效地提高难求解问题的求解效率，近年来成为人们研究的热点。隐蔽集中变量的赋值能有效减少SAT问题求解的搜索分支，从而减少问题求解的时间复杂度和空间复杂度。为提高SAT问题的求解效率，提出一种求解SAT问题隐蔽集的改进算法，并给出最小隐蔽集的定义。在该算法中加入启发式，使求解出的隐蔽集变量个数较少，最后给出隐蔽集问题的总结和展望。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谷文祥	东北师范大学计算机学院	71	538	11.0	20.0
2	李淑霞	河南工业职业技术学院计算机工程系	20	95	5.0	9.0
3	龚茜茹	河南工业职业技术学院计算机工程系	25	23	3.0	3.0