Research On Adaptive Consistency Algorithm In Constraint Satisfaction Problems

Constraint Satisfaction Problem is an important part of the artificial intelligence.There are more and more applications in artificial intelligence that use constraintnetworks to solve combinatorial problems.A constraint network is composed of a finite sequence of integer variables X, adomain for X and a set of constraints C. Finding a solution in a constraint satisfactionproblem involves looking for a set of value assignments, one for each variable, so thatall the constraints are simultaneously satisfied. Filtering techniques are essential toreduce the size of the search space and so to improve the efficiency of search algorithms.They can be used during a preprocessing step to remove once and for all some localinconsistencies that otherwise would have been repeatedly found during search.Therefore, the search algorithm combine with the consistency technology, it raises theefficiency of search algorithm significantly.Due to combine the heuristics and consistency algorithm before the search, it willnot be changed in the search process, makes the solving algorithm has limitations, andsolve some problems low efficiency. Therefore, we proposed an adaptive solvealgorithm. During the search process, adaptive solve algorithm based on the currentcharacteristics of the problem dynamic selects a suitable heuristic and consistencyalgorithm for the current state of the problem.This paper mainly contains: firstly, an introduction of the background of theconstraint satisfaction problem such as consistency techniques, the search algorithm ofmaintain arc consistency and heuristics can improve the efficiency of solving algorithm;secondly, consistency techniques are essential to improve the efficiency of searchalgorithms, so we propose an adaptive consistency algorithm LCadp, the specific workas follows:The LCadpallow us to dynamically switch between enforcing a weak, and cheap localconsistency, and a strong but more expensive one, it will be improve the solutionefficiency to ensure a trade-off in deletion ability of the local consistency algorithm andthe cost of the algorithm.Based on the constraint activity characteristics of high concentration, we considerthe constraint network also has this characteristic--if the entire network in a certain statedelete value active, then in the subsequent state will continue delete value actively. Thevolume of a constraint network is used to describe the state of the entire network, LCadpalgorithm according the different status of constraint network dynamically switchingdifferent consistency algorithms, switching is based on the volume change of the network after constraint checks. Constraint network in the original constraintpropagation phase with strong consistency algorithm, if the volume of constraintnetwork change too much, the number of the deletion values is large, the subsequentconstraint propagation continues to use strong consistency algorithm; otherwise, itmeans the number of the deletion values is small, there is no need to use a strongconsistency algorithm, it will switch to a weak one. In addition, the constraint checkarrived at a certain stage, the constraint checking deletes less values than before, andkeep low deletion, so the subsequent constraint checking algorithm keeps using weakconsistency algorithm, no longer switch into a strong one.As a case study we experiment with binary problems using AC3rmas a weakconsistency and LmaxRPC3rmas a strong one.CPU time(CPU(ms)), constraintchecking number(#CCKS), instance nodes(#nodes) as experimental parameterscomparing. The experimental results show that in most problems, the CPU running timeof LCadpoutperforms the other two algorithms, and in some problems, LCadpoutperforms at least one algorithm at the constraint checking and instance nodes.Overall, the efficient application of a LCadpthroughout search outperforms AC3rmandLmaxRPC3rmalgorithm.