隐蔽集的研究及发展

SAT问题的隐藏结构与问题难度有很大的关系,近年来成为人工智能的一个研究热点。隐蔽集(Backdoor)作为典型的隐藏结构之一,能使剩下的问题在多项式时间内求解。在深入研究隐蔽集的基础上,首先对隐蔽集的发展、相关概念、参数复杂性及隐蔽集与骨架(Backbone)之间的关系作了全面的论述;接着分别从CSP问题、SAT问题和QBF问题3个方面具体介绍了目前比较流行的隐蔽集求解方法;最后给出了3个未解决的问题,并对隐蔽集的发展趋势进行了展望。

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

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

一种量词约束满足问题的混合易解子类

量词约束满足问题是人工智能和自动推理领域的一个重要问题.寻找多项式时间易解子类,是研究此类问题计算复杂性的关键.通过分析二元量词约束满足问题中的约束关系特征,以及量词前缀中的全称量词排列的顺序,提出了针对全称量词变量子结构的易解性质的分析方法.通过该方法,扩展了已知的基于Broken-Triangle Property的多项式时间易解子类,提出了一个更一般化的量词约束满足问题的混合易解子类.讨论了易解子类在问题结构分析中的一个应用,即通过易解子类确定量词约束满足问题的隐蔽变量集合,并通过实验分析不同易解子类所确定的集合大小.实验改造了基于回溯算法的求解器,在回溯过程中加入了易解子类的识别算法,并采用随机约束满足问题的生成模型作为测试基准.通过对比实验,验证了提出的多项式时间易解子类可以识别出更小的隐蔽变量集合,因此,新提出的易解子类在确定隐蔽变量集合方面更具优势.最后阐述了其他已有的混合易解子类也可以通过类似方法进行扩展,从而得到更多的一般化的理论结果.

WP可解公式上警示传播算法收敛的有效条件

通过对警示传播(warning propagation,WP)算法的数学原理分析,高概率确定的部分变元与公式的骨干集和后门集有密切关系。针对WP算法收敛性的研究,基于骨干集和后门集定义WP-可解公式,利用在G(n,3,m)模型和植入指派模型下证明WP算法的收敛性,给出算法收敛的充要条件。最后,通过在植入指派的公式产生模型上进行数值实验验证,结果表明:如果一个可满足性公式WP-可解公式,当且仅当WP算法高概率收敛。