Information Technology Reference
In-Depth Information
assumptions differ form the justifications in the fact that they are believed unless
there is evidence to the contradiction and can thus prove false. The advantage of
ATMS lies in some temporary assumptions are shared and not need to create
separately. The number of temporary assumptions is usually exponential
increasing, therefore the procedure of assumption creation has exponential
complexity. The ATMS has the following shortcomings:
• It is designed for complete solutions, for one solution unnecessary search is
always done;
• It costs a lot of time and space for maintaining all contexts;
• It is difficult to correct mistake.
It is very difficult for this method to estimate storage requirement, and all
deriving and assumptions should be recorded, which makes the method difficult
to apply to large-scale system. Thus de Kleer and Williams proposed to use
backtracking in order to control ATMS again, which is also similar to an
intelligent backtracking method.
3.6 Variable Instantiation Ordering and Assignment Ordering
Another improvement for standard backtracking is variables instantiation
ordering. Experiments show that this ordering can have substantial impact on the
efficiency of backtrack search. Several heuristics have been developed for
selecting variable ordering. One method is selecting the variable with the fewest
value of domain for instantiation. Thus the order of variable instantiation is, in
general, determined dynamically, which is different in different branches of
search tree. Purdom and Brown extensively studied the heuristic, as well as its
variants(Purdom, 1983), and the results show that they are substantial
improvements over the standard backtracking method.
Another heuristic is to instantiate those variables first that participate in the
highest number of constraints. This approach tries to ensure that the unsuccessful
branches of search tree are pruned early.
Recall that the tree-structured constraint network can be solved without
backtracking. Any given constraint network can be made a tree after deleting
certain vertices. This set of vertices is called the
. If a small cycle
cutset can be found, then a good heuristic is to first instantiate all the variables in
the cycle cutset and then solve the resulting tree-structured CSPs.
cycle cutset
