The Research Of Forward Checking Algorithm Based Decomposition

Constraint programming is an emergent software technology for declarative description and effective solving combination optimization problems. It represents the most exciting developments in programming languages of the last decade. It has been identified by the ACM (Association of Computer Machinery) as one of the strategic directions in computer research. It is not only based on a strong theoretical foundation but also it is attracting widespread commercial interest particular in satisfaction problems. Constraint programming has been applied in numerous areas, for example: computer graphics, natural language processing, database systems and molecular biology.A constraint is simply a logical relation among several unknown variables; every variable only has a value in a given domain. Constraints are common in our life for example the three angles of a triangle sum to 180 degrees.Constraint Network and Constraint satisfaction problems have been studied as a research field in Artificial Intelligence starting from the seventies. Constraint satisfaction problems origins from problems like scene labeling problem. A constraint satisfaction problem contains a finite set of variables, a finite set of domains and a finite set of constraints. Each domain restricts the scope of values that a variable can take, and constraint restricts the combination of values that a set of variables may take. A solution of a CSP is an assignment that each variable in the set of variables takes a value from its domain that satisfies all the constraints. A partial solution of CSP is an assignment of a subset of the variable set of CSP which satisfies all constraints which contain these variables. The task of CSP is to find one solution, one partial solution or all solutions. There are three techniques in Constraint Solving which are generate-and-test (GT), Consistency techniques and Searches based on backtracking (BT). BT is a classic technique in constraint solving, but its ability is limited. Consistency techniques effectively detect and prune many inconsistent assignments at a very early stage, so to reduce the search space. In order to find efficient techniques, Researchers focus on combinations of Consistency techniques and search based on backtracking.There are two phases of improvements of backtracking algorithm: look-head schemes and look-back schemes. Forward-checking (FC) is one of the classic look-head schemes. FC employ domain pruning in a fairly restricted way. Pruning is done in lock step with search. That means these algorithms perform constraint propagation, detect some set of inconsistent values and prune those values to the current level once a new assignment is made. All of these values need to be restored until the domains of the uninstantiated variables are in the same state as we entered it when backtracking happens. As a result they would improve the efficiency of FC as we find failed pruning as early as we can and reduce the invalid assignment as most as we can.Constraint Decomposition is a very import research field in Constraint programming. There are many methods which are used in Constraint programming. And there many methods in many subjects such as decompositions in graph, decompositions methods in graph database, heuristic methods.This paper is mainly based on the study of FC, according the disadvantage of FC, using decomposition method, proposes a method called Separated Backtracking-Forward Checking method(SBT-FC) and a extending method called Extending of SBT-FC(ESBT-FC).The main contributions are listed as follows:(1)Propose Assignment and Separation theory and prove using Assignment and Separation problems are equal original problems, and propose a method called SBT-FC which choose a key variable from current constraint graph ,assigning value from domain to it, then using decomposition, not consider the key variable, decompose current constraint graph into several connected constraint graph and consider each sub constraint graph independency in this way we can reduce a lot of redundancy backtracking and find the variable which domain is empty as soon as possible so improve the efficiency of constraint solving. Meanwhile, we design a platform for testing constraint solving which is based on Linux and compare classic method and recently methods. Our result show that SBT-FC better than FC and BDH-FC algorithm in most case.According to these two algorithms, there are four reasons that SBT-FC is better than BT-FC. The first reason is SBT-FC jump back to next sub-problem'key variable, but BT-FC jump back to the last variable. The second reason is SBT-FC does check forward and restore in variables incurrent sub-problem, but BT-FC do these in the future variables. The number of variables in current sub-problem is often smaller than the number of the future variables in most case. The third reason is that there is not any relationship between these sub-problems which are in the same level, so the constraint checking number of SBT-FC is a processing of adding but the constraint checking number of BT-FC is a processing of product. The fourth reason is that SBT-FC do jump back as early as possible because when it find one sub-problem is no solution, BT-FC do jump back in order to reduce invalid checking-forward operation. (2) SBT-FC do decompose when it visits a variable, but the decomposition just has a relationship with the structure of constraint graph and has not relationship with the value of the variable, so SBT-FC decomposition have some invalid operation. According this reason, decomposition is done before search may be better than the way that SBT-FC does. And the structure of decomposition is stored in a special data structure which algorithm can get the information of decomposition when searches-FC is proposed which is based on this method.Because decomposition has nothing to do with variable assignment, we propose a method call ESBT-FC which can first decomposes the problem and store information of decomposition in a special data structure, using decompose-density as a heuristic to guide the decomposition, then it visits the data structure and get the information of decomposition in order to avoid the invalid decomposition in SBT-FC algorithm and get a better decomposition during searching. The experimental results show that ESBT-FC is better than SBT-FC.