Research On Consistency Techniques In Constraint Satisfaction Problems

Constraint is a ubiquitous concept, so it attached to the experience of daily life:they represent the conditions which restrict the freedom of people to make decisions. A variety of combinatorial optimization problems in daily life have a very close relationship with it, especially those with academic value and commercial value, such as graph coloring problems, product configuration problems, scheduling problems and so on. In the past, traditional algorithms in operations research were used to solve these problems, but sometimes the unreasonable solution was got, and it took very long time.The search space of this kind of problems is exponential, in order to improve efficiency, the conditions in a actual problem are expressed as constraints, and then the problem is modeled as a Constraint Satisfaction Problem (CSP). We take the current techniques for CSP to solve.A constraint satisfaction problem (CSP) has three components:a finite set of variables, a finite set of domains the values in which can be instantiated to the associated variable, the finite set of constraints (constraint is the restrictive relationship between the variables.) Each constraint will limit the set of values of variables associated constraint. If the set of values do not violate the constraint, we say that the constraint is satisfied by the current assignment. A solution of CSP is that each variable is assigned a value in its domain, and all constraints are satisfied simultaneously.In order to improve the efficiency of solving CSP problems, researchers divide process into two parts:off-line preprocessing (filtering) and on-line solving. Currently the efficient technique which can be used in the two processes is consistency. In recent years, researchers at home and abroad have proposed series of algorithms such as AC, PC, SAC, etc. In this article, I list more popular consistency and solving techniques, and make some research on SAC algorithm in filtering process, which can remove more redundant values, as follows:(1) We mainly research the consistency algorithm SAC3 algorithm in the preprocessing, which mainly adopts the idea of depth-first and a greedy search strategy, and has low complexity and relatively better time complexity. Based on SAC3 algorithm framework, I propose SAC3-FFP algorithm, with the heuristic of failure-first principle, a static heuristic strategy. In the process of constraint propagation it can find that the domain of some variable is empty in advance and backtrack, so that it improves the efficiency. Then I give the complexity and correctness analysis. Experimentations prove that the new propagation algorithm is improved.(2) Combined with the above work, I give SAC3-MINIsup algorithm based on the dynamic heuristic strategy. It dynamically sorts the variable-value pairs which are waiting to propagating in the process of constraint propagation according to the support numbers recorded in the implementation process. The new algorithm's complexity and correctness are been proved. Experimental data prove that it is improved.(3) In the process of constraint propagation, SAC3 algorithm lack validity estimation and pertinence when dealing with the variable-value pairs. I give the SAC3-Revised Algorithm which adds corresponding strategies according to the flaws in SAC3. It propagate only on the suspectable pairs, rather than all of the pairs, so that it can reduce the number of propagation and improve the efficiency. This article also gives the complexity, correctness analysis and experimental results.