一种量词约束满足问题的混合易解子类
作者:
作者单位:

作者简介:

高健(1983-),男,辽宁沈阳人,博士,副教授,CCF专业会员,主要研究领域为约束程序设计,自动推理;陈荣(1969-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为软件诊断,群体智能,优化调度;李辉(1983-),男,博士,副教授,主要研究领域为众包软件,复杂网络.

通讯作者:

陈荣,E-mail:rchen@dlmu.edu.cn

中图分类号:

TP181

基金项目:

国家自然科学基金(61402070,61672122,61602077)


Hybrid Tractable Class for Quantified Constraint Satisfaction Problems
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61402070, 61672122, 61602077)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Quantified constraint satisfaction problem (QCSP) is a central problem in artificial intelligence and automated reasoning. The tractable class is an important method to analyze its computation complexity. This study proposed a new method to determine tractability of quantified variables by analyzing constraint structures and the ordering of universally quantified variables in the prefix on a binary QCSP. Based on this method, the existing tractable class was extended with the broken-triangle property, and then a more generalized hybrid tractable class was proposed. Furthermore, an application was presented that was identifying backdoor sets through the new tractable class, and the experimental results were analyzed to show the size of backdoor sets identified by those hybrid tractable classes. To perform the experiment, a state-of-the-art QCSP solver was modified based on a backtracking algorithm by integrating a backdoor set detection module, and the advantage of the new generalized tractable class is shown where the size of backdoor set identified by it is smaller than the existing one on randomly generated instances. Finally, it is indicated that the method proposed in this study can be employed to extend other hybrid tractable classes.

    参考文献
    相似文献
    引证文献
引用本文

高健,陈荣,李辉.一种量词约束满足问题的混合易解子类.软件学报,2019,30(12):3590-3604

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-12-28
  • 最后修改日期:2018-03-17
  • 录用日期:
  • 在线发布日期: 2019-12-05
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号