Information Technology Reference
In-Depth Information
constraint(binary constraint). The edge between two vertexes denotes that there
exists binary constraint between these two variables denoted by vertexes. In
graph-based backjumping, whenever a failure come out at some variable
X
, the
algorithm always goes back to recent assigned variable connected to
X
in graph.
The graph-based backjumping is described as follows.
Algorithm 3.5
Forward Propagation Algorithm
Forward(
x
1
, … ,
x
i
,
P
)
begin
if
i=n
then Exit and Return current assignment;
C
i+1
ŕ
computeCandidates(
x
1
, … ,
x
i
,
x
i+1
) ;
if C
i+1
not null, then
x
i+1
ŕ
The first element in C
i+1
;
Delete
x
i+1
from C
i+1
Forward (
x
1
, … ,
x
i
,
x
i+1
,
P
);
else
Jumpback(
x
1
, … ,
x
i
,
P
);
endif
end
Where, P is a set of variables which will be backtracked.
Algorithm 3.6
Jumpback Algorithm
Jumpback(
x
1
,··· , x
i
,
x
i+1
, P
)
begin
if
i=0
,then Exit without solution;
PARENTS
ŕ
Parents(
x
i+1
);
P
ŕ
P
∪PARENTS
;
P
ŕ
P
-
x
j
; j is the biggest serial number of variables in
P
,
If
C
j
≠φ,then
x
j
=first in
C
j
;
Delete
x
j
from
C
j
;
Forward (
x
1
,… ,
x
j
,
P
);
else
Jumpback (
x
1
,…
,x
j-1
,
x
j
,
P
);
endif;
end
