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

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