Information Technology Reference
In-Depth Information
the failure. To see how intelligent backtracking works, consider the following
example.
Suppose that variables
v
1
,
v
2
, and
v
3
have been assigned values
a
1
,
b
3
, and
c
2
,
respectively. Suppose that none of the values of
v
3
were found compatible with
the values
b
1
and
b
2
of
v
2
. Now suppose that all possible values of
v
4
conflict with
the choice of
v
1
=
a
1
. The conflict is caused by the inappropriate choice of
v
1
, so
the intelligent backtracking method will perform backtracking to
v
1
and also undo
the assignments of
v
3
.
Although this kind of method can find correct backtracking node according to
the failed source, it has not totally avoided the redundant path. Dependency-
directed backtracking is a method to eliminate the drawback and widely used in
truth maintenance system(TMS) developed by Doyle.
A TMS-based problem solver consists of two components: an inference
engine and a TMS. The inference engine is used to derive new facts form old
ones, while TMS is records the justifications of the derivations. New joining of
fact might make some existing assumptions not true. Therefore the maintenance
of justifications can abolish those assumptions not true any more. The method
used for CSP is described as follows.
When a variable is assigned some value, a justification for this value is
created. Then similarly, a default value is assigned to some other variable and is
justified. At this time, the system checks whether the current assignments violate
any constraint. If they do, then a new node is created that denotes that the pair of
values for the two variables are contradictory. This node is also used to justify
other value assignment. This process continues until a consistent assignment is
found for all the variables. Such a system never performs redundant backtracking
and never repeats any computation.
Although the amount of search performed by such a system is minimal, the
cost of determining the source of constraint violation is high. Because reasoning
steps are exponential increasing, the time and space complexity for storing and
search are exponential. Hence, overall the method can take more time than even
simple backtracking for a variety of problems.
Assumption-based truth maintenance system(ATMS) is another relevant work
developed by de Kleer. The ATMS evolves from the TMS. TMS can be regarded
as constraint propagation and ATMS is the expansion of TMS. TMS only
maintains single context, while ATMS attempts to search for multiple contexts at
the same time. Therefore, each fact derived is corresponding to assumptions that
make the fact true. A conclusion may be true in multiple contexts. The
v
2
and
