Chinese Journal of Computers   Full Text
Title	An Approach of Solving Constraint Satisfaction Problem Based on Preprocessing
Authors	SUN Ji-Gui1),2) ZHU Xing-Jun1),2) ZHANG Yong-Gang1),2) LI Ying1),2)
Address	1)(College of Computer Science and Technology, Jilin University, Changchun 130012) 2)(Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012)
Year	2008
Issue	No.6(919—926)
Abstract &   Background	Abstract As an effective technology for solving constraint satisfaction problem, consistency technology plays an important role not only in preprocessing, but also in searching. Firstly, this paper proposes two new consistency algorithms called Pre-AC and Pre-AC* applied during searching, which are based on the performance on an improvement of consistency during preprocessing and information extraction. Secondly this paper presents two new searching algorithms called BT+MPAC and BT+MPAC* by embedding those two consistency algorithms into the BT framework respectively. Thirdly, after proving the correctness of Pre-AC and Pre-AC*, this paper analyzes their time complexity. It is evidently that the complexities of Pre-AC and Pre-AC* are O(nd) and O(ed2) respectively, which are apparently lower than O(ed3), the complexity of arc consistency algorithm. In the experiments on several kinds of instances, efficiency of the proposed algorithms is 2~50 times higher of that of maintaining arc consistency. Keywords constraint satisfaction problem; arc consistency; singleton arc consistency; pre_arc consistency Background CSP is an important researching area in artificial intelligence. However, it is the NP-complete task of determining whether a given CSP instance has a solution. As an effective technology for solving CSP instance, consistency technology plays an important role not only in preprocessing, but also in searching. However these two phases are separated as far as we know. So the efficiency of solving problems is not satisfied. This paper proposes two new consistency algorithms applied during searching based on preprocessing and embedded into BT framework to form two searching algorithms. The authors analyze the time and space complexity and prove correctness of them theoretically. Besides, experiments show that the proposed algorithms have a better performance. All our algorithms mentioned in this paper were implemented in C++ and embedded into the constraint solving platform "Ming Yue 1.0" designed by the authors. The idea of this paper is inspiring since it does not follow the traditional mode. Moreover it exploits the information enough in preprocessing to reduce the search space and speed up solving process by removing the inconsistent values. This paper was supported by the National Natural Science Foundation of China (grant No.60773097).