A New Preprocessing Technique Based on Entirety Singleton Consistency
Zhu Xing, Sun Ji, Yong Zhang, Ying Li · Acta Automatica Sinica · 2009
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.