Research On Constraint Propagation Strategy And Heuristics In CSP

Constraint Satisfaction Problem(CSP)is an important branch of artificial intelligence,and it is also a hot issue in the field of artificial intelligence in the world.CSP can simulate a variety of complex combinations,covering a wide range of technologies such as artificial intelligence,operations research,programming languages databases etc.CSP has been successfully applied to such areas as resource allocation,production scheduling,product configuration,logistics planning,routing,bioinformatics etc.To solve a Constraint Satisfaction Problem(CSP),constraint modeling is first performed.The modeling process is done by specifying variables,domains and constraints.Then use the constraint solver to solve.General constraint solver interleaves heuristically guided backtracking search and inference methods until meets a solution by assigning values to a given set of variables that satisfy all constraints.Backtracking search algorithm is the main search algorithm to solve the CSP.During the backtracking search,a series of decisions must be made,it deternmines which variable need to instantiate to which value.These decision processes are called variable and value ordering.Existing studies have shown that for many problems,the choice of variable and value rankings can greatly affect the efficiency of solving CSP instances.This paper makes a detailed study of the current heuristic methods for ranking variables and values.Applying constraint propagation in backtracking search is one of the most important techniques for solving the constraint satisfaction problem.Arc consisntency is the core of the constraint propagation technology.Many constraint propagation algorithms are developed around arc consisntency.Arc consisntency is the most basic and well-known constraint propagation algorithm.It requires that each value of the constraint network can find support in the constraints.Many AC algorithms have now been proposed.Among many AC algorithms,AC-3 algorithm,a coarse-grained algorithm,has become the most propular one because of its generality and simplicity.To establish AC,the AC-3 algorithm keeps a list of elements that need to be revised.The AC-3 algorithm can use several different propagation mechanisms in the AC process.It has three classic variants,corresponding to arc-oriented,variable-oriented,and constraint-oriented.For the three classic variants of AC-3,there are different revision heuristics.These revision heuristics are also based on the “fail-first principle”.When AC is applied during the search,the revision list is used,thus a proper ranking mechanism can significantly improve the performance of the AC-3 algorithm.This paper analyzes and studies the three classical variants of AC-3 and the revision heuristics applied to them,and proposes a new variable-oriented propagation strategy based on AC-3.The dissemination strategy also maintains a list of variables that need to be corrected when AC is established.It breaks down the propagation process into two separate phases.This article will show how it reduces the number of revision and list operations.In the experiment,revision heuristic was applied to this new variable-oriented propagation strategy and compared with the most effective available propagation strategies.Results from various structural and stochastic problems indicate that the newly proposed propagation strategy reduces the number of revisions and speeds up the search process.It speeds up the implementation of AC and outperforms existing propagation strategies.