Research On Implementation And Optimization Of The Variable Elimination In Binary Constraint Satisfaction Via Forbidden Patterns

Constraint satisfaction problems as a main research direction of problem solving method has been widely used in the field of artificial intelligence,and the attention of many experts and scholars at domestic and abroad.Constraint satisfaction problems modeling can be applied to many areas such as configuration, scheduling, planning,and bioinformatics.In the CSP model we have a number of variables, each of which can take values from its particular finite domain. Certain sets of the variables are constrained in that their simultaneous assignments of values is limited.The certain sets of variables are known as the constraint scopes.If the size of the set of variables are at most two,the constraint network is known as binary constraint satisfaction problem.We are required to assign values to all variables so that every constraint is satisfied.Search algorithms for constraint problems usually proceed by transforming the instance into a set of subproblems, for example, by selecting a variable and assigning to it successively each value from its domain.Search algorithms for constraint problems usually proceed by transforming the instance into a set of subproblems, for example, by selecting a variable and assigning to it successively each value from its domain. Even though the backtracking algorithm can take exponential time it is often effective in practice thanks to intelligent pruning techniques.There are many ways to improve naive backtracking by pruning the search space in ways that cannot remove solutions. This is done by avoiding searching exhaustively in all generated subproblems when the solution can not exists. Such techniques include Back-marking, Back-jumping, Conflict-Directed Back-jumping.The most common techniques is to maintain the local consistency property called generalised arc-consistency(GAC). This technique identifies certain values for variables that cannot possibly form part of a solution.In the same way, savings can also be made if we are able to eliminate variables from a sub-problem. Since backtracking is of exponential time complexity, the elimination of variables to reduce instance size can in the best case reduce search time by an exponential factor.A variable elimination rule in constraint satisfaction problems allows the polynomialtime identification of certain variables whose elimination does not affect the satisfiability of an instance. Variable elimination in the constraint satisfaction problem(CSP) can be used in preprocessing or during search to reduce search space size. Martin C. Cooper et al proposed a tool called the forbiden patterns. We show that there are essentially just four variable elimination rules defined by forbidding generic sub-instances, known as irreducible patterns, in arc-consistent CSP instances. One of these rules is the Broken Triangle Property.We realize the variables elimination that use forbidden patterns to find the variables can be deleted. Select MAC3 rm as a basic algorithm. We show the result that solving the problem only with MAC3 rm compare with solving the problem mix in variables elimination. To observe the effects of variables elimination on solving efficiency.We will realize the variables elimination both in static and dynamic way.The static realization means that implementation the variables elimination once during the initialization. After that doing the backtrack algorithm on the result,find the solution.The dynamic realization means that implementation the variables elimination every time after doing constraint propagation during the search process. in this paper,we analyze the realized results both in the static and dynamic way. Although the dynamic realization can save the time during search,but the variable elimination process itself takes a lot of times. Therefore, int this paper we have use the some method,such as the adaptive parameters,to optimize the a dynamic realization.