Research In Hypertree Decomposition Algorithms Of Constraint Satisfaction Porblems

As a generic way of solving, constraint satisfaction problem has always been a hot topic in the field of artificial intelligence and the research in the problem about constraint satisfaction has never been interrupted. In fact, Constraint satisfaction problems are widely used, many problems can be transformed into a constraint satisfaction problem, such as product configuration, model-based diagnosis, scheduling, timetabling and so on. Generally, a constraint satisfaction problem is consists of a finite set of variables, a finite set of domains. and a finite set of constraints where the set of domains are the domains of each variable, each constraint restricts the values that variables can take simultaneously. To transform the problem into the corresponding constraint satisfaction problem, we usually view the parameter of the problem and the parameter's domain as a variable and its corresponding domain respectively and abstract the related constraints from the conditions that the problem need to satisfy.After simplify the real problem into a system of constraints, the efficiency of solving the related constraint satisfaction problem is become important. Solving a CSP is well-known to be NP-hard and its efficiency has become a goal for many researchers. Meanwhile much effort has been spent by both the AI and the database communities to study the structure of the CSPs. They find a tractable class of CSPs due to restricted structure, these CSPs are identified solely on the base of the structure of the constraint scopes, and independently of the actual constraint relations.Whether a CSP is easy to handle is closely related to its topology, usually we use the constraint primal graph or constraint hypergraph to represent the structure of the corresponding constraint satisfaction problem. In fact, we can solve a CSP which has tree-like structure (i.e. acyclic CSP) in polynomial time. But in real word, the CSPs we encountered are cyclic and they need a huge amount of memory and time. It is important to find some methods, which can transform cyclic CSPs into acyclic CSPs, and this lead to produce many decomposition methods of CSP.Decomposition technique can control the complexity of constraint satisfaction problem, although it is not improved the worst-case complexity. Especially for the large-scale CSPs. All the decomposition technique have a basic principle:is decomposed a constraint satisfaction problem P into an equivalent tree-like constraint problem P'.The efficiency of solving a tree-like CSP is high.In particular each decomposition method D defines some concept of width which can be interpreted as a measure of acyclicity of the constraint graph, called D-width. Such that for each fixed width k, all CSPs of D-width bounded by k are solvable in linear time. As we know constraint decomposition is based on graph-theoretic properties, therefor the research on the constraint decomposition is focused on the tree decomposition, viewed the graph of a problem as a tree:reassembled a graph into a join-tree by split the cycle in the graph. So the constraint graph of the problem become a tree-like structure. The concept of tree width is very important for the tree decomposition, as it is a measure for the associated constraint graph, the smaller the tree width, the better of the acyclicity of the graph and the faster the computation problem can be solved. When the tree width is 1, the graph is become a tree and for the constraint graph, if its width is 1, its corresponding CSP is an acyclic CSP. During the research in the structure of the CSP and the decomposition technique, people have found that describe a problem into a hypergraph can have a more generic use, and proposed the hypertree decomposition technique. Hypetree decompositions are a generalization of tree decompositions and the corresponding hypertree-width is a more appropriate measure for the acyclicity and therefore an indicator for the tractability of the associated computation problem. The hypertree decomposition can most likely obtain the minimal hypertree decomposition (i.e. the width of the decomposition is equal to the hypertree-width) of the graph.Many algorithm has been proposed. People always want to find a hypertree decomposition algorithm which can compute the optimal hypertree decomposition (if such a decomposition exists). One of the most representative algorithms is det-k-decomp, a deterministic algorithm which can construct the k-bounded hypertree decompositions in polynomial time. The det-k-decomp is obtained from k-decomp algorithm, it improve the efficiency by the following ways:reduce the search space for a separator and use heuristics during selecting an appropriate separator; apply a backtracking-based search procedure and store already visited separators which can avoid construct the same subtree multiple times. Generally det-k-decomp significantly outperforms opt-k-decomp, it improve the shortcomings of opt-k-decomp. i.e. the high cost of computation, and in this algorithm the search space and the width of the resulting hypertree decomposition can be bounded by k, that is to say, we can obtain the minimal hypertree decomposition by set k small enough. In principle, such an approach allows us to control the tradeoff between the width of resulting hypertree decomposition and the computation time. Besides, researchers also studied the special hypertree decompositions and proposed some tractable hypertree decompositions, such as connected hypertree decomposition which presented by Sathiamoorthy. The connected hypertree decompositions have a more restrict structure than the hypertree decompositions, and they are subsets of hypertree decompositions. Sathiamoorthy showed that due to the property of subset, the connected hypertree decomposition is also tractable and its decomposition width is not less than hypertree-width. He also proposed the concept of the isomorphic and introduced it into the corresponding algorithm, which can improve the efficiency of the decomposition.In this paper, we proposed a new class of hypertree decomposition:separated hypertree decomposition and presented a new hypertree decomposition algorithm. The main contidutions are listed as follows:(1)Propose a new class of hypertree decompositions:separated hypertree decomposition and give the corresponding algorithm shtd-k-decomp. The separated hypertree decompositions have a more restrict concept and are the subsets of hypertree decompositions, therefore they are tractable and htw(H)≤shtw(H). Experiments show that for most instancs htw(H)=shtw(H) and the decomposition efficient is higher than the connected hypertree decompositons.(2)Based the det-k-decomp and the property of the separated hypertree decomposition, we proposed a new hypertree decomposition algorithm separated-based hypertree decomposition---sht-k-decomp. It outperforms det-k-decomp:the search space of the separator in sht-k-decomp is different:when we select the next separator, we first compute the Separator in the OldSep and the current hypergraph, then determine the value of the separator by the resulting Separator. These can reduce the search space and avoid compute some separators that lead to failed decompositions. We also record the information of the decomposed subgraph which can avoid construct the same subtree multiple times. In order to identify more subgraphs that have processed. Sathiamoorthy proposed the definition of isomorphism and presented that the components which are isomorphic have the same decomposition. Based the det-k-decomp. we introduced the isomorphism such that we can identify more subgraphs have the same decomposition, hence the efficiency is improved.