Information Technology Reference
In-Depth Information
is actual data dependence. Therefore, perhaps some two variables are connected
in constraint graph, but do not influence each other under current context. The
space cost of Influence-based backjumping has less space cost than graph-based
backjumping. Furthermore, influence-based backjumping produces less time cost
as well.
In IBMD, each instantiated variable stores a set of influenced variables. Given
a IBMD's context(all assignments of instantiated variables), a variable
v
i
is
influenced by
v
j
if and only if the instantiations of
v
j
reduces current domain of
v
i
to some extent.
IBMD includes forward instantiation and backward backtracking. In forward
instantiation, select the variable whose current domain is minimal to assign at
first. After the variable
v
i
assigned, domain filtering will be carried on. For all
unassigned variable
v
j
, delete those values in its domain
D
j
, which are
contradicting with assignment of
v
i
. If
D
j
becomes null, means that the
assignment of
contradicts with previous variable assignment, therefore
backtracking begins. Backtracking firstly recover values which have been deleted
because of variable
v
i
v
i
instantiation. If all values of
v
i
have been tried, then
backtracking continues going to previous variable
v
h
. If
v
h
has no influence on
v
j
or other variables whose all values have been tried, or
v
h
has been already tried
all values, then make
v
h
as previous instantiation variable and repeat backtracking.
Suppose that the procedure stops at variable
v
g
and the latest variable that
influences
v
g
is
v
f
, then delete the instantiation value of
v
g
from
D
g
and record
v
g
and its instantiation value into influence set of
v
g
with new
value again, thus back to forward instantiation backtracking. The algorithm
written in C is as follows.
v
f
. And then assign
Algorithm 3.7
Influence-based Backjumpiing Algorithm(Liao, 1994)
IBMD()
{
int var, failvar;
while (uninstantiated ! =nil ) {
var =mostConstrained() ;
/*Choose a variable to instantiate */
a[var] =domain[var][ 0]; /* Assign a value. */
while ((failvar =propagate(var) )! =SUCCESS) {
/*While inconsistent */
if ((var =backjump(failvar) ==nil) return(0) ;
/*If back up to top, exit */
