一种新的基于完全独立相容性的预处理技术

摘要：

研究了求解约束满足问题(Constraint satisfaction problem,CSP)中的预处理技术.首先提出了子论域上的完全独立相容性(Entirety singleton consistency,ESC)概念和相应算法,分析并证明了算法的复杂性和正确性,而后对其两条重要性质进行了详细证明.基于此概念和性质,提出了一种基于完全独立相容性的预处理算法:SAC-ESC算法,并给出了正确性证明.最后,本文采用分治思想,根据不同问题的论域自适应地合理划分其子论域.实验结果表明,对于随机问题、鸽巢问题、N皇后问题和基准用例,算法SAC-ESC的执行效率大约是目前流行算法SAC-SDS和SAC-3的3～20倍.

关键词：约束满足问题、预处理技术、完全独立相容性、分治策略

所属期刊栏目：35

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

资助基金：国家自然科学基金60773097;吉林省青年科研基金20080107

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

页数：共6页

页码：71-76