Information Technology Reference
In-Depth Information
However, the algorithm exists multinomial complexity for constraint network
with special structure. The simplest case is that, arc-consistent algorithm can be
used to solve the tree-structured constraint network within linear time
complexity.
3.4 Constraint Propagation in Tree Search
Two different methods for solving CSP are discussed above: backtracking and
constraint propagation. In the first method, different combinations of variable
assignments are tested until a complete solution is found. This approach suffers
from thrashing. In the second method, constraints between different variables are
propagated to derive a simpler problem. Although any CSP can always be solved
by achieving n consistency, the efficiency of this approach is usually lower than
backtracking's. Furthermore, the k-consistency(k<n) algorithm does not ensure
achieving global consistent solution. A integrated method is to embed constraint
propagation inside a backtracking algorithm, as follows:
At first, a root node is created to solve original CSP. When a node is visited, a
constraint propagation algorithm is used to achieve a desired consistency. If at a
node, the domain of each variable contains only one value, and corresponding
CSP is arc consistent, then the node represents a solution. If in the process of
constraint propagation at a node, the domain of any variable becomes null, then
the node is pruned. Otherwise select one variable (whose domain size >1), and
new CSP node is created for each possible assignment of this variable. Each new
CSP node is depicted as a successor node of the node representing current CSP.
All these nodes are visited by a depth-first backtracking algorithm.
The problem now is how constraints propagate to what extent at each node. If
no constraint propagation is done, then the method reverts to backtracking. If m-
consistency algorithm is used to achieve m consistency for m CSP nodes which
are unassigned would completely eliminate backtracking, and result in poor
efficiency. Experience indicates that limited constraint propagation whose
consistency is generally not stronger than arc consistency, can achieve the best
efficiency.
3.5 Intelligent Backtracking and Truth Maintenance
Another method to overcome drawbacks of standard backtracking is intelligent
backtracking in which backtracking is done directly to the variable that caused
