摘要
隐蔽集(backdoor sets)作为隐藏结构的一种,能有效地提高难求解问题的求解效率,近年来成为人们研究的热点.隐蔽集中变量的赋值能有效减少SAT问题求解的搜索分支,从而减少问题求解的时间复杂度和空间复杂度.为提高SAT问题的求解效率,提出一种求解SAT问题隐蔽集的改进算法,并给出最小隐蔽集的定义.在该算法中加入启发式,使求解出的隐蔽集变量个数较少,最后给出隐蔽集问题的总结和展望.
Backdoor is one of these structures ,which can effectively improve the efficiency of the SAT problem solving ,and which become a focus of study in recent years .The variable assignment for backdoors can reduce the search branch of SAT problem solving process effectively , thereby reducing the time complexity and space complexity of sat problem solver .In order to improve the efficiency of the SAT problem ,this paper presents the improved algorithm of backdoor sets for sloving SAT problem ,and provides the definition of the smallest backdoor sets .The heuristic is joined in this algorithm ,so the smaller backdoor sets can be solved in this way ,Finally ,this paper proposed summary and outlook .
出处
《微电子学与计算机》
CSCD
北大核心
2014年第7期65-68,共4页
Microelectronics & Computer
基金
国家自然科学基金(61070084)
关键词
SAT问题
隐蔽集
隐藏结构
最小隐蔽集
隐蔽集变量
Propositional Satisfiability problem
backdoor sets
hidden structure
the smallest backdoor sets
Variables of backdoors
