Research On Tree Decomposition In Constraint Satisfaction Problems

Constraint satisfaction problems (CSP-constraint satisfaction problems), alsoknown as constraint network, is an important branch of artificial intelligence. Alongwith the development of economy, academic research hasn’t been stayed in thetheoretical stage, and it is much closer to real life. So there are a growing number ofproblems about economic, industrial and other aspects, which are solved by beingabstracted into constraint network. The core technology Solving constraint network isconsistency technology. Consistency technology is often optimized in the model ofconstraint network. Constraint network problems have a uniform structure, so that nomatter how the structure is obtained, the model built is able to handle with it.Therefore, algorithm of consistency technology can be applicable to all the constraintnetwork, while the difference is the level of efficiency when solving the problem.After decades of development, the methods of solving constraint network have beengreatly improved, and different types of problems also have correspondingalgorithms.Now the more commonly used solving mechanism is backtracking algorithm, Onthe basis of using backtracking algorithms, there are many different algorithms forinitialization filtering of constraint network and solving constraint network.Thesealgorithms vary in efficiency, so they provide with a lot of research direction forresearchers. Even there may exists some improvement in algorithms. When solvingthe constraint network with backtracking algorithm, heuristic algorithm can improveefficiency. The commonly used heuristic methods are variable ordering heuristic andvalue ordering heuristic. When solving constraint network, there is another method called treedecomposition algorithm. It solves constraint network by preprocessing the wholeproblem and converting constraint to an abstract tree. Nodes of tree are variables andconstraints of constraint network, and the nodes are connected via constraints. Eachchild node of the decomposition tree is equivalent to a small constraint network.When solving such a tree, the small constraint network is solved firstly, and then thesmall constraint network spreads. To some extent,this method reduces the size of theproblem when solving the constraint networks, and increases efficiency. Currently,there are a lot of algorithms which are based on tree decomposition, this articlefocuses on the backtrack search with tree decomposition, referred to as BTD, BTDsolves the problem by applying the tree decomposition to backtracking algorithm.It is known that backtracking algorithm is a depth-first algorithm, so thedepth-first algorithm has more advantage than breadth-first algorithm in efficiency.This paper focuses on optimizing BTD algorithm, and applies the BTD algorithm tothe restart technology. The dom/wdeg heuristic is the most common and mostefficient method when solving the problem. Details are as follows:(1)Firstly we introduce some knowledge about tree decomposition algorithm,here also includes the triangulation algorithm which determines the quality of thedecomposition tree. The complete decomposition tree obtained is an NP-hard problem.In order to translate the constraint network into a decomposition tree, min-fillalgorithm is the most common algorithm, Then we introduce the heuristic and the newheuristic which is based on tree decomposition, and a variety of heuristic methods.Also the condition how to use heuristics is pointed out.(2)The proposed BTD algorithm in the article is a new algorithm, which is BTDbased on separator. In this algorithm, the tree wide is no longer the size of the treenode, but the size of the separator, thereby the width of the tree reduces. The mainfunction of the algorithm is adjusting the order of variables in tree nodes, then obtainsthe solution order of variables in sub-problems. The conventional consistencyalgorithms can be used in BTD algorithm, such as AC3, etc. There are a lot of problems which can’t be solved by a decomposition tree, thereby we should replacethe root node by changing the decomposition tree structure, which can be realized bythe restart technology. This technology solves the problem by adding restartalgorithm.