Information Technology Reference
In-Depth Information
3.9 Influence-based Backjumping
We improved graph-based backjumping to form a new influence-based
backjumping. First of all, our goal is not only to utilize static connection relation,
but also dynamic relevant information. The key problem is how to limit the cost
of computing resources that caused by introducing dynamic information within
reasonable scope. Through exquisite design of the algorithm and data structure,
we succeeded in solving this problem.
Influence-based backjumping¾IBMD (Influence-based-Backjumping, Most-
constrained-first, Domain-filtering)integrates three strategies: most-constrained-
first, domain filtering and backjumping. Most constrained first refers to selecting
the variable with minimum “degree of freedom”to assign each time. The “degree
of freedom” is mainly measured by the current domain of variable, because it is
the most important and easiest quantity to calculate. The calculation can be also
measured with help of connection degree of variable in constraint network. The
most-constrained-first strategy is a very effective improvement for fixed variable
instantiation ordering.
Domain filtering refers to deleting the value inconsistent with assigned
variable values from variable domain. This is a constraint propagation
technology with small cost. When a new variable is assigned, all those
unassigned variable values which are inconsistent with this assignment will be
deleted. The assignment is tentative, so deleted values must be stored. When
some assignment is revoked, all deleted values caused by this assignment must
be recovered.
Backjumping we designed is different from traditional dependency-directed
backtracking, including graph-based backjumping. The traditional dependency-
directed backtracking records explicitly assumption sets on which reasoning will
rely. Once one-step backtrack is done, assumption set of revoked variable will be
merged into the assumption set of recent assigned variables, which causes a lot of
time cost and space cost. In order to avoid such cost, our backjumping does not
backjump according to recorded assumption set. In fact, we do not need these
records at all. Our backjumping method backjumps according to actual influence
from one assignment to variable in filtering process. One assignment has
influence on the variable vi, if and only if as least a value of current domain has
been deleted in the filtering process caused by that assignment. Obviously the
influence is calculated more accurately than the connection relation of network.
Because connection relation is a possible data relevance, while influence relation
