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

A New Preprocessing Technique Based on Entirety Singleton Consistency

作　　者：朱兴军[1,2] 孙吉贵[1,2] 张永刚[1,2] 李莹[1,2] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012

出　　处：《自动化学报》2009年第1期71-76,共6页Acta Automatica Sinica

基　　金：圉家自然科学基金(60773097);吉林省青年科研基金(20080107)资助~~

摘　　要：研究了求解约束满足问题(Constraint satisfaction problem,CSP)中的预处理技术.首先提出了子论域上的完全独立相容性(Entirety singleton consistency,ESC)概念和相应算法,分析并证明了算法的复杂性和正确性,而后对其两条重要性质进行了详细证明.基于此概念和性质,提出了一种基于完全独立相容性的预处理算法:SAC-ESC算法,并给出了正确性证明.最后,本文采用分治思想,根据不同问题的论域自适应地合理划分其子论域.实验结果表明,对于随机问题、鸽巢问题、N皇后问题和基准用例,算法SAC-ESC的执行效率大约是目前流行算法SAC-SDS和SAC-3的3～20倍.This paper studies the technique of preprocessing in constraint satisfaction problem （CSP）. Firstly, we propose a notion of entirety singleton consistency （ESC） and the algorithm, and then analyze the time and space complexity and correctness. Based on this, we present a new preprocessing algorithm SAC-ESC based on ESC, and prove its correctness. Furthermore, we use the divide-conquer strategy for the algorithm to automatically adapt to domain partition of various problems. In our experiments on random CSPs, pigeon problems, N-queens problems and benchmarks, the efficiency of our algorithm SAC-ESC is 3 - 20 times those of the existing SAC-SDS and SAC-3.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]