Information Technology Reference
In-Depth Information
2
10
(
,
,
)
is given in [
3
].
A third way of using constraint solving technology is to design special algorithms.
In the following, we shall elaborate on backtracking search algorithms for finding
covering arrays and orthogonal arrays.
An optimal covering array CA
24
4
6.3 Backtracking Search for Generating Covering Arrays
The Covering Array (CA) generation problem can be naturally modeled as a CSP.
Without loss of generality, assume we are trying to find a CA
(
N
,
d
1
·
d
2
···
d
k
,
t
)
where
d
1
≥
k
matrix,
where each entry in the matrix is called a
cell
.Weusece
r
,
c
to denote the cell at row
r
and column
c
.Theset
d
2
≥ ··· ≥
d
k
. A CA can be displayed as a 2-dimensional
N
×
{
ce
r
,
c
|
1
≤
r
≤
N
,
1
≤
c
≤
k
}
is the set of problem variables
in the CSP, and each variable ce
r
,
c
has domain
{
0
,...,
d
c
−
1
}
. The restrictions on
value combinations serve as problem constraints.
6.3.1 Preprocessing
In the first
t
columns of the matrix, there are
b
d
t
possible combinations
of values. We can make the first
b
rows contain each value combination once by
swapping the rows of thematrixwithout changing the test suite. Thus we can initialize
this
b
=
d
1
d
2
...
t
sub-array (which is called an
init-block
) in advance. For example, in Fig.
6.2
,
the init-block of an instance of CA
×
2
5
(
6
,
,
2
)
is the framed sub-array of size 4
×
2.
6.3.2 The Search Procedure
The framework of the backtracking algorithm is described as a recursive procedure
in Algorithm 4. For a given covering array number
N
, we try to assign each cell
of the
N
k
matrix until all requirements of covering arrays are satisfied. The
parameter
pSol
and
Fmla
represent the current partial solution (assignments to cells)
and the constraints respectively. Each time a variable is assigned, the constraint
propagation function
BPropagate
inspects the constraints to check if any constraint
×
Fig. 6.2
Init-block of
00000
01000
10011
11
101
00111
11110
2
5
CA
(
6
,
,
2
)
Search WWH ::
Custom Search