An Approach of Solving Constraint Satisfaction Problem Based on Preprocessing
Sun Ji · Chinese Journal of Computers · 2008
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.