SAT问题中隐蔽集求解的改进  

The Improvment Backdoor Sets for SAT

作　　者：李淑霞[1] 龚茜茹[1] 谷文祥[2] 

机构地区：[1]河南工业职业技术学院计算机工程系,河南南阳473000 [2]东北师范大学计算机学院,吉林长春130117

出　　处：《微电子学与计算机》2014年第7期65-68,共4页Microelectronics & Computer

基　　金：国家自然科学基金(61070084)

摘　　要：隐蔽集(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 .

关 键 词：SAT问题 隐蔽集 隐藏结构 最小隐蔽集 隐蔽集变量 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]