| 基于序列的子问题相容性技术 |
| |
| 引用本文： | 陈德泉 张永刚 辛 颖 刘文壮. 基于序列的子问题相容性技术[J]. 计算机科学, 2015, 42(7): 28-31, 37 |
| |
| 作者姓名： | 陈德泉 张永刚 辛 颖 刘文壮 |
| |
| 作者单位： | 吉林大学计算机科学与技术学院 长春130012吉林大学符号计算与知识工程教育部重点实验室 长春130012 |
| |
| 基金项目： | 本文受国家自然科学基金面上项目:基于自适应约束传播的约束求解方法研究(61170314),国家自然科学基金面上项目:结合自主搜索机制的约束求解方法研究(61373052)资助 |
| |
| 摘 要： | 研究约束求解中的相容性技术,针对目前已有相容性的传播级别,提出一种新的相容性概念——基于序列的子问题相容性(SSAC),并给出相应的实现算法。然后分析其时空、空间复杂性及正确性,证明SSAC化简不改变原约束满足问题的解集,同时证明SSAC的约束传播能力介于SAC和AC之间。通过对随机问题和composed问题的测试表明,所提算法的效率是已有算法SAC-SDS和SAC-3的2～3倍。
|
| 关 键 词： | 约束满足 相容性技术 SSAC |
Singleton Sub-problem Arc Consistency Based on Order |
| |
| CHEN De-quan ZHANG Yong-gang XIN Ying LIU Wen-zhuang. Singleton Sub-problem Arc Consistency Based on Order[J]. Computer Science, 2015, 42(7): 28-31, 37 |
| |
| Authors: | CHEN De-quan ZHANG Yong-gang XIN Ying LIU Wen-zhuang |
| |
| Affiliation: | College of Computer Science and Technology,Jilin University,Changchun 130012,ChinaKey Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education,Jilin University,Changchun 130012,China |
| |
| Abstract: | |
| |
| Keywords: | Constraint satisfaction Arc consistency technique SSAC |
|
|
点击此处可从《计算机科学》下载全文 |
|
