The Research Of Arc Consistency Algorithm Techniques In Constraint Satisfaction Problems

In social life, many problems can be effectively simulated to solve constraintsatisfaction problems (CSPs) and Constraint satisfaction techniques to solve. Thereare many instances to solve the problem is modeled as a CSP, such as spatial analysis,symbolic reasoning, diagnosis, decision support, scheduling, hardware design andcertification, job scheduling, resource allocation, the graphical display of lights androbot design. This makes the constraint satisfaction problem to become a veryimportant one problem in artificial intelligence research。Determine whether a CSP is solvable is a complete NP-hard, in order toeffectively carry out problem solving, researchers on the scale of the problem bypreprocessing technology for effective simplification, to reduce the search space forsolving and the number of backtracking. In1975,Waltz first to use arc consistencytechnique in computer vision problems, it can effectively remove the variable ofredundant values, reduce the scale of the problem, thus greatly reducing the searchspace, and improve problem solving efficiency. Reduce the extent of the compatibilityproblem is different due to the different compatibility，with the reduced degree ofincrease, the consumption of time and space also increases. Arc consistency algorithmmay be rational reduced to a certain amount of time and space. And thus is consideredto be the most effective way to deal with large-scale problems. Arc consistencyalgorithm is based on the compatibility algorithm, compatibility testing to determinewhether the variable value to meet the arc consistency. If all the variable values aremet consistent compatibility, then it was the arc consistency. The process of testing todetermine is to use the compatibility algorithm, therefore arc consistency algorithmdevelopment, efficiency advance and time and space complexity is based on closelyrelated with compatibility algorithm. Arc consistency algorithm, most of thedevelopment of optimization, is based on the idea of the breadth-first search, anideology based on depth-first search based on two considerations. Arc consistency algorithm based on depth-first search is the first instantiation of a variable assignmentand then call the compatibility of the algorithm consistency of judgment, and thenagain to select a different variable instantiation and then in the sub-questioncompatibility check. Stop the search until all the variables are instantiated or there is adeadlock point.This article is mainly based on the direction of the depth-first ideology abovestudy optimization to determine, the depth-first is the gradual increment of callcompatibility algorithm. Therefore, how to turn select the variable to instantiate thefirst variable value, handing of the overall impact on the deletion of the redundantvalues are all related to the performance of the algorithm. Generally speaking, how toincrease branch search depth, to reduce unnecessary constraints the number of checksand eliminate unnecessary impact in after redundancy value deleted must face. Basedon the above considerations, plus the original SAC-3+algorithms study, and proposeda new singleton arc consistency algorithm for the SAC-3+*. The new algorithm is aconstrained problem into a colletion of sub-problem,which is equivalent to theoriginal problem. This sub-problem will be able to take full advantage of thedepth-first ideology, select the variable values on the compatibility check is a highersuccess rate, thereby enhancing the compatibility of the depth of the search. Thisarticle is still selected variable instantiation process using inference, a one-timeselection of the k-value of the associated constraint propagation to do so would ensurethe success rate of the SAC also saves k-1sub-arc compatibility check. When arcconsistency remove the variable x the value a, the paper records values (x, a) therelationship with the value of (y, b), wait for the end of the one-way arc consistencythe value of the record for the SAC. This will not only save storage space, but alsoreduce a lot of useless constraint checks.