Research On Heuristic Algorithm For Constraint Satisfaction Problem Based On Variable Weight

Constraint satisfaction problem is one of the most important research directions in the field of artificial intelligence,which is mainly used to solve practical and academic problems.The main idea of solving constraint satisfaction problem is to abstract the problem into a constraint network model first.Then,the algorithm for solving the constraint satisfaction problems is used to solve the constraint network model.At present,the algorithm for solving constraint satisfaction problems mainly includes backtracking search algorithm,heuristic algorithm and local reasoning algorithm.MAC algorithm,which is based on backtracking search,is the most widely used search algorithm for solving constraint satisfaction problems.The idea of the algorithm is using backtracking search strategy during the search.After the selection and the instantiation of the variable,the constraint network is filtered by the consistency algorithm.The consistency algorithm can delete the values that do not satisfy the consistency in the domain,reduce the search space and simplify the search process.When using MAC algorithm to solve large scale constraint satisfaction problems,unreasonable variables instantiation order often leads to too large search tree,which seriously affects the efficiency of solving.In the process of backtracking search,the state of the constrained network often changes,so it is very difficult to find an optimal order of variable instantiation.Therefore,scholars have proposed the concept of heuristic.Before we instantiate variables,we use heuristics to select variables and values to minimize the size of search tree as much as possible.The role of variable ordering heuristic algorithm is to guide the backtracking algorithm to instantiate variables based on heuristic rules,so as to avoid redundant search and improve efficiency.According to whether the variable instantiation order is changed during the backtracking search,the variable ordering heuristic algorithm is divided into two kinds: static variable ordering heuristic algorithm and dynamic variable ordering heuristic algorithm.Based on the initial structure and properties of the constraint network,the static variable ordering heuristic algorithm determines the instantiation order of the variable before the search begins.The principle of heuristic algorithm for dynamic variable ordering heuristic algorithm is to collect heuristic information that is beneficial to solve in the process of backtracking search.When selecting variables,we first compute a heuristic score for each variable,and then select variables according to heuristic scores.Because of the backtracking search is a dynamic process,fixed variable instantiation order cannot adapt to changing constraint network states during the search.Therefore,the dynamic variable ordering heuristic algorithm is often used in practice.Scholars have put forward many good variable ordering heuristic algorithms including the Dom heuristic based on the domain size,the Ddeg heuristic based on variable degree,the Wdeg heuristic based on constraint weight,the Tdeg heuristic based on tightness,and the Variable_try heuristic based on variable instantiation times.Heuristic algorithms usually have good scalability,and the combination of different heuristics usually can get a more heuristic heuristic.The Dom/Wdeg heuristic,which combines the Dom heuristics and the Wdeg heuristics,is the most efficient dynamic variable sorting heuristic algorithm.In this paper,we studied and analyzed the widely used Wdeg heuristic.Aiming at its shortcomings,the corresponding optimization is carried out,and seveal more efficient heuristic algorithm is proposed.The specific work is as follows:(1)The constraint satisfaction problem of background knowledge and current dynamic variable ordering heuristics are introduced and analyzed,including the basic concept of the constraint satisfaction problem,the consistency algorithms,the MAC algorithm,the Ddeg heuristic,the Wdeg heuristic,the Tdeg heuristic and the Variable_try heuristic.(2)Aiming at the shortcomings of the Wdeg heuristic,this paper puts forward the concept of variable weight and several heuristics based on variable weight.A large number of experiments prove that the new heuristics have strong heuristic ability in solving constraint satisfaction problems.