软件学报

作者：高健,陈荣,李辉

单位：高健，大连海事大学 信息科学技术学院, 辽宁 大连 11602611,陈荣，大连海事大学 信息科学技术学院, 辽宁 大连 11602602,李辉，大连海事大学 信息科学技术学院, 辽宁 大连 11602603

关键词：量词约束满足问题;易解子类;隐蔽集;回溯算法

基金：国家自然科学基金（61402070，61672122，61602077）

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

来源：2019年第12期

《软件学报》期刊编辑部

查看软件学报杂志2019年第12期