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

发布时间：2021-06-10 07:22

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

【文章来源】：软件学报. 2019,30(12)北大核心EICSCD

【文章页数】：15 页

【参考文献】：
期刊论文
[1]优化求解约束满足问题的MDDc和STR3算法[J]. 杨明奇,李占山,李哲.  软件学报. 2017 (12)
[2]负表约束的简单表缩减广泛弧相容算法[J]. 李宏博,梁艳春,李占山.  软件学报. 2016(11)
[3]基于量词约束满足的机械产品质量特性稳健优化设计方法[J]. 林晓华,冯毅雄,谭建荣,冯勇,高一聪.  机械工程学报. 2013(15)
[4]Integrating Standard Dependency Schemes in QCSP Solvers[J]. 金继伟,马菲菲,张健.  Journal of Computer Science & Technology. 2012(01)
[5]一种基于环切割的约束满足问题求解算法[J]. 李占山,李宏博,张永刚,王孜文.  计算机学报. 2011(08)
[6]求解QBF问题的启发式调查传播算法[J]. 殷明浩,周俊萍,孙吉贵,谷文祥.  软件学报. 2011(07)



本文编号：3221947