Research On Adaptive Parameterized Consistency

Nowadays, the constraint is a common relationship. There is no complete independentindividuals. When people join the community, people are limited by the various ofconstraints of social activities and social productions. Not only between humans, orbetween society and human, there is constraints between all the affairs.It has becomean important method to solving problems with the constraint thinking. Therefor e, thestudy of constraint is also deepening, and new methods are have been proposed. It isbecoming standardized from testing cases to solving method. The Entire constraintsolving algorithm is based on backtracking, which together with the compatibilityalgorithm constantly searching and judging to determine the final solution.Backtracking algorithm is a classical complete algorithm, with which the solvableproblems are ensured to obtain their solutions, and the unsolvable problems can beproved to be unsolvable. Because the idea of backtracking is going through everypoint to obtain the final solution. It makes expensive cost of time and space, when thenumber of variables of problem is big or the problem is complicated. Due to thestrong eager for efficient solving, researchers are having optimizing the method ofsolving constraint satisfaction problem. By the effort of continuous researching andtesting, the researcher found that,it can be judge before searching that many values arenot in the solution,which can greatly reduced the problem space by removing suchvalue from the initial problem. However, the principle of deleting values directlyaffects the efficiency of problem solving. Therefore, different compatibilityalgorithms for different problems are also having been proposed.In theory the reality problems can be abstracted as constraint satisfaction problem,and finally can be solved with the corresponding algorithm. The constraintsatisfaction problem is a hot research field in artificial intelligence. CP (Principle andPractice of Constraint Programming) conference held regularly every year, is one ofthe important conference on artificial intelligence. The cost of algorithm increasedwith the increasing of consistency. Although various heuristic to solve the problem ofalgorithm are applied to the algorithm research, but the measure of a good algorithmis mainly based on the pruning ability and execution cost of problems. Due to thedifferent characteristics of different problems and same problem shows differentcharacteristics in different stages, the concept of "heuristic" was proposed, it is mainlyfor the various stages of problem to select the most appropriate algorithm. At the sametime of the program to realize the adaptive, it abstract problem differentcharacteristics of the abstract into parameters. Through the parameterized program itcan be improved the efficiency of constraint problem solving.This thesis mainly around the adaptive of constraint satisfaction problem andparameterized. On the basis of the existing solution technology proposed a more reasonable algorithm the max restriced path constraint (maxRPC). Through a lot ofexperiments, the reduction of the variable redundancy check is an importantoptimization method. Theory of adaptive parametric maxRPC extracts valuecharacteristics of variable as parameter, so setting the filter method to choose a valueto consistent judgement can delete the value which is most likely to be deleted strongconsistency checks. The faster deletion of Invalid value, the easier causebacktracking. It is more likely to find the problem as soon as possible. The parametersettings of each value in the existing algorithm are based on initial variable domain.But the invalid value deletion continuously, the characteristics of the current valuemay change. In order to make the characteristics of variable parameters can moreexactly reflect the characteristics of value in the current stage, I according to thecurrent characteristic of the problems to continuously update the characteristic of thevalue. The original constant features make solving problems faster to delete invalidvalues, reach the fastest backtrack and optimal efficiency. The proposed algorithmrespectively based on the fixed parameter values, the variable parameter adaptivethreshold and adaptive variable parameters threshold to implement. The result ofexperiment if not only make up for the disadvantage of the original algorithm but alsoin terms of access time and node shows good performance. On the introduction ofefficient methods for solving the problem of non-binary processing method tableconstraints, the tuple unified storage, record its position in the table. Adopt theeffective tabular constraint methods in solving non-binary problems which store thetuples unified and record the tuples’ positions in the table. Quickly process bymaintaining the data structure in the process of propagation. Use the tabularconstraints as the underlying structure implementation, whist the general supportstructure of the tabular constraints is used in the parameter and adaptive calculation.Store the structure for each constraint value and record the tuples which include thevalues in the structure.We can get the propagation current status and the supports forthe given values when we check out the structure.