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

• 作者: 李辉 陈荣 高健
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 量词约束满足问题 易解子类 隐蔽集 回溯算法
• 年，卷（期）: 2019,（12）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 3590-3604
• 页数: 15页
• 分类号: TP181
• 字数: 16519字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005598

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈荣	大连海事大学信息科学技术学院	17	115	6.0	10.0
2	高健	大连海事大学信息科学技术学院	9	33	4.0	5.0
3	李辉	大连海事大学信息科学技术学院	5	19	3.0	4.0