Research On Adaptive Search Strategy For Solving Constraint Satisfaction Problems

Constraint Programming（CP）is an effective method for solving combinatorial search problems,it has been a hot issue in basic research of artificial intelligence and used in many fields.CP models a task as a constraint satisfaction problem（CSP）,and then uses a constraint solver to solve it.Ideally,users only need to focus on the modeling process.It’s very challenging for non-expert users to design or select right search strategies,a good strategy can significantly reduce the search space,so developing black box constraint solver to automatically select effective strategies has important research value.This paper introduces the existing search strategy in detail,and proposes an adaptive search strategy for solving the CSP while improving the existing algorithm.In order to realize the automatic selection of variable ordering heuristic in constraint solver,the algorithm framework that can balance"exploration"and"exploitation"is designed.An adaptive score with multiple features is formulated,it not only follows the principle of fail-first,but also combines the search depth to evaluate the performance of the search strategy more comprehensively.In the"exploration"stage,problem’s search space is explored by cyclic sampling method combined with restart,the information of the search tree is continuously collected,and the efficiency of each heuristic is evaluated by using the adaptive score.In the"exploitation"stage,the heuristic with the largest adaptive score is used to guide the search.The experimental results on Mini Zinc benchmark show that the efficiency of this algorithm is better than the existing adaptive search algorithm and four classical heuristics,ABS,CHS,dom/Wdeg^ca.cd,FRBA.In addition,for different CSPs,the adaptive score proposed in this paper has better effect than others.