基于序列的子问题相容性技术
约束满足问题(CSP-Constraint Satisfaction Problem)是人工智能研究领域的一个重要问题。在求解过程中，相容性技术(consistency technique)所起的作用是十分巨大的，该技术通过移走不相容的值和尽可能早地发现将来会产生冲突的值，来降低搜索空问、加速求解过程。研究约束求解中的相容性技术,针对目前已有相容性的传播级别,提出一种新的相容性概念——基于序列的子问题相容性(SSAC),并给出相应实现算法,而后分析其时空、空间复杂性及正确性,证明SSAC化简不改变原约束满足问题的解集,同时证明SSAC的约束传播能力介于SAC和AC之间通过对随机问题和.composed问题的测试表明:新提出算法的效率是已有算法SAC-SDS和SAC-3的2-3倍.
人工智能 约束满足问题 相容性 约束传播能力
陈德泉 张永刚 辛颖 刘文壮
吉林大学 计算机科学与技术学院,吉林 长春 130012;吉林大学 符号计算与知识工程教育部重点实验室 吉林 长春 130012
国内会议
济南
中文
1-9
2014-10-16（万方平台首次上网日期，不代表论文的发表时间）