Solving From A Decomposition
Given the tree of a decomposition, solving can be done by constructing the binary tree-like problem as described above, and solving it. This is a polynomial-time problem, as it can be solved in polynomial time using, for example, an algorithm for enforcing directional arc consistency.
A specialized algorithm for the case of binary acyclic problems that result from a decomposition is described as follows. It works by creating constraints that are passed along the edges of the tree, from the leaves to the root and back. The constraint passed along an edge "summarizes" the effects of all constraints of the part of the graph on one side of the edge to the other one.
In a tree, every edge breaks the graph in two parts. The constraint passed along an edge tells how the part of the originating end of the edge affects the variables of the destination node. In other words, a constraint passed from node to node tells how the nodes "on the side of " constrain the variables of node .
If the variables of these two nodes are and, the nodes on the size of do not affect all variables but only the shared variables . As a result, the influence on of the nodes on the side of can be represented as a constraint on variables . Such a constraint can be seen as a "summary" of how a set of nodes affects another node.
The algorithm proceeds from the leaves of the tree. In each node, the summaries of its children (if any) are collected. These summary and the constraint of the node are used to generate the summary of the node for its parent. When the root is reached, the process is inverted: the summary of each node for each child is generated and sent it. When all leaves are reached, the algorithm stops.
| A decomposition tree with associated constraints. All variables have domain {0,..,10} in this example. | The leftmost node contains the constraint a0 is sent to its parent. | The left child of the root receives the constraint b>0 and combines it with its constraint b |
When the root has received constraints for all its children, it combines them and sends constraints back to them. The process ends when all leaves are reached. At this point, the allowed values of variables are explicit. |
The set of variables shared between two nodes is called their separator. Since the separator is the intersection between two sets associated with nodes, its size cannot be larger than the induced width of the graph.
While the width of the graph affects the time required for solving the subproblems in each node, the size of the separator affects the size of the constraints that are passed between nodes. Indeed, these constraints have the separators as scope. As a result, a constraint over a separator of size may require size to be stored, if all variables have domain of size .
Read more about this topic: Decomposition Method (constraint Satisfaction)
Famous quotes containing the word solving:
“You are right to demand that an artist engage his work consciously, but you confuse two different things: solving the problem and correctly posing the question.”
—Anton Pavlovich Chekhov (1860–1904)