基于序列的子问题相容性技术

摘要：

研究约束求解中的相容性技术,针对目前已有相容性的传播级别,提出一种新的相容性概念——基于序列的子问题相容性(SSAC),并给出相应的实现算法.然后分析其时空、空间复杂性及正确性,证明SSAC化简不改变原约束满足问题的解集,同时证明SSAC的约束传播能力介于SAC和AC之间.通过对随机问题和composed问题的测试表明,所提算法的效率是已有算法SAC-SDS和SAC-3的2～3倍.

关键词：约束满足、相容性技术、SSAC

所属期刊栏目：42

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金面上项目:基于自适应约束传播的约束求解方法研究61170314;国家自然科学基金面上项目:结合自主搜索机制的约束求解方法研究61373052

在线出版日期：2016-05-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：28-31,37