The Study Of Constraint Consistency Technology

In the real world, most problems all can model as constraint problems. Then they can use the uniform constraint solving technology to solve, such as scheduling, hardware design and certification, routing, timetabling, and real-time system. These make the Constraint Satisfaction Problem have better commercial value. A solution of a CSP is an assignment to each variable a value from its domain satisfying all the constraints. The aim of the CSP is to find a solution or the all solutions. However, to check whether the CSP have a solution is NP-hard. Though the Backtracking has completeness, its efficiency is very low. In order to improve the efficiency of the solving, induct the consistency technology. Arc consistency is a very efficient consistency technology. It can remove the values that cannot appear in any solution to reduce the search space before or during searching. So that it can greatly reduce the searching space of the solving.This article mainly studies the consistency algorithm and proposes heuristic algorithm; research the solving technology of constraint problem, remedy the old algorithm and propose the more efficient algorithm. The explicit contributions list as follows:(1) Through the study the AC-4. take full advantage of the data structures, then present ordering heuristic forming the new solving algorithm based on the data structure used in the AC-4 algorithm. These algorithms take full advantage of the state information of the data structure or the information kept recorded in data structure after the process of arc consistency. According to the heuristic information, we sort the values of the variables' domain. So that, we can force the solving algorithm to give priority to extend the values of variables, which have more heuristic information. In this way, the efficiency of the solving algorithm can be improved a lot. The result of our experiments shows that the algorithm, which has been interleaved with ordering heuristic, has much more advantage over the other solving algorithms.(2) Study the SAC-MP algorithm and present the idea of using the graph partitioning technology in the SAC-MP algorithm. The proposed algorithm take full advantage of the value of k which is decided by the graph partition technology in the process of executing.so that it can avoid the redundant operations and blindness that are brought by the uncertainty of the value of k. So that, the algorithm has a better efficiency in solving the constraint satisfaction problem. The result of our experiments shows that our method can improve the efficiency of the algorithm and prove that our method is very effective.(3) MAC(Maintaining arc consistency) algorithm is the main search technology for the constraint satisfaction problems. We have studied the MAC algorithm carefully. In order to make full use of the information, which is collected during the initializing phrase of the MAC. and the characteristics of maintaining full arc consistency of MAC. we propose a new algorithm. Reivsed_MAC. which constructs a new data structure to record the information, which is useful while searching for solutions. By the information, the algorithm can quickly discover whether the value assigned to the current variable is viable or not. According to that, we can reduce the times of propagating so as to reach the aim of improving the efficiency of searching for solutions. The results of our experiments show that the efficiency of our algorithm, Revised_MAC,is better than MAC algorithm.