Information Technology Reference
In-Depth Information
test method. In backtracking, the variables are instantiated as a fixed order. When
a new variable violates former instantiated variable, backtracking is performed to
try other instantiated variable until all values of domain are tried. When all values
are tried in failure, it backtracks the most recently instantiated variable and
assigns it again.
Suppose the solution of CSP is made up of vectors with uncertain length,
i.e.(
x
1
, x
2
,
… ), which satisfies all constraints. X
i
is the value domain of variable xi,
then the feasible solution space of CSP is X
1
× X
2
×… X
n
, where n is the number
of variables.
At the beginning of backtracking, partial solution is a null vector. Then
choose a variable
x
1
from variable set and add it into partial solution. Usually
x
1
takes the minimum element of X
1
. The candidates of
1
chosen under various
constraints will form a subset S
1
of X
1
. The constraints can be used to find out
candidates from partial solution (
x
x
1
, x
2
,
…
,x
k-
1
) to (
x
1
, x
2
,
…
,x
k-1
,x
k
). If (
x
1
,
x
2
,···,x
k-1
,x
k
) does not allow
x
k
to take any value, then S
k
= φ. On this condition,
backtracking is done and assign a new permission value for
x
k
-1
. If
x
k
-1
does not
have new permission value, further backtracking to
x
k
-2
is done and so on.
Suppose T(
x
1
,
x
2
, ··· ,x
k
) does not allow to have new expansion node, then bounding function
BT
k
(
x
1
, x
2
, ··· ,x
k-
1
) denotes all fetching values of
x
k
. If partial solution (
x
1
, x
2
, ···,x
k
) is false, otherwise true. The backtracking algorithm with only
one solution is shown as follows:
Algorithm 3.1
Backtracking Algorithm
Input: A CSP problem
Output: Complete solution or return no solution
procedure BACKTRACK
begin
k =1;
while
k>0
do
If
x
k
has unchecked value to make
x
k
∈
T(x
1
,x
2
,
…
,x
k-1
) and
BT
k
(x
1
,x
2
, ,x
k
)
=true
then if(
) satisfy all constraints
then return(0) ; /* return one solution */
else
x
1
,x
2
,
…
,x
k
k=k+1
;
end if;
else
k=k-1
;
endwhile
