Research On Consistency Algorithm Based On MDD In Constraint Satisfaction Problems

Constraint Satisfaction Problem(CSP) is an important part of the artificial intelligence, and its core is the constraint solving. To explore the most efficient algorithm is one of the major problems of current research which is aim to improve the solving efficiency.Consistency technology plays an important role in the solving process of CSP. It can be used to remove the variable values that must not be extended to solutions during a preprocessing step and the whole search. Thus it can reduce the unnecessary search and the search space. Backtracking search is a general solving technology. It makes the constraint satisfaction problem solving fast and efficiently when the variable selection and value selection be joined appropriate heuristic strategy, and combined with consistency technology in the process of backtracking.On nowadays, there are a lot of practical problems involving multiple variables but the major solving technology is according to binary CSPs. Therefore, the direct solution techniques for non-binary CSPs attract more attention. There are at least two options when it comes to dealing with non-binary CSPs: apply one of the standard translations to convert it to a binary CSP and then solve it using efficient binary CSP techniques, or apply one of the direct solution techniques for non-binary CSPs. In this paper, we mainly study the latter.Non-binary constraint representation has a lot of kinds but the most common used is the solution of tuples in a table. There are several approaches to the reduction representation of table constraint such as tries, muti-valued decision diagrams(MDD),compressed tables or deterministic finite automata. The key success factor is basically the compression ratio achieved when tables are represented by sophisticated data structures, because it determines the space requirement. The MDD-based representation has the advantage that it can achievespace reduction. This article is under the MDD structure, according to the analysis of the existing algorithms and optimization, the concrete work is as follows:(1) We give a brief introduction of present solution techniques for non-binary CSPs. Then we propose an mddc+ algorithm which is improved from the original GAC algorithm based on MDD. The algorithm introduces an early-cutoff optimization to record the values which has found supports in current domain when traverse the MDD and the sub-MDDs. If all values in a variable and below its MDDs to be able to find a support in its domain, then the current node of MDD is no need to traverse, but just need to find a path from the current node to a terminal node. Thus reducing the unnecessary process of looking for supports, and its efficiency is verified by experiment.(2) During search, we inject a heuristic in node selection for each layer. We choose the more general dom/wdeg heuristic from present heuristics to reduce the total time of constraint solving. To a certain extent, it improved the solution efficiency.In this paper, the two improved pseudo code are represented. Then, we compared with the original mddc algorithm and STR algorithm by testing the solving CPU time and the number of expansion nodes. Upon that, the improvement of this paper can increase the efficiency on many issues.