Information Technology Reference
In-Depth Information
Fig. 6.4 The value vector's
frequency
(a) aaaaa
abbbb
acbcc
baabc
bbcac
bcaab
cabac
cbacb
cccba
aaccb
bbbca
(b) The Value
Vectors a b c
Column 1 443
Column 2 443
Column 3 443
Column 4 434
Column 5 344
the vector of columns. The frequency of the sub-combination SC C , denoted by f C
,
is the number of occurrences of the s -tuple V in the columns C .
Definition 6.4 ( Sub-Combination Equalization Heuristic (SCEH) )InaCAof
strength t , for any two sub-combinations SC V 1
C
and SC V 2
C
of size s
(
0
<
s
<
t
)
from the same column set C ,wehave
f V 1
C
f V 2
C
|
|≤
1 for all V 1 =
V 2 .
3 5
Example 6.4 A covering array CA
(
11
,
,
2
)
is given in Table (A) of Fig. 6.4 .
1, then we have s =
Consider s
5 column vectors and each has 3 value vectors.
We can count the frequency of each column vector. The results are listed in Table (B).
The frequencies of different vectors with the same column are almost the same.
=
As a mathematical hypothesis, SCEH has neither been proved nor disproved so
far to our knowledge. Nevertheless, it can serve as an effective strategy to prune the
search space. For almost all CA instances, the search time can be reduced with this
strategy.
While processing a CA, one can specify the strategy level SL, so that the
occurrences of all s -tuples (0
<
s
SL) are restricted. Normally we would choose
SL
1. The strategy is applied to the backtracking search algorithm by checking
the upper-bound UB and lower-bound LB of the frequency of each sub-combination.
If an assignment x
=
t
=
u causes the frequency of a sub-combination to go beyond the
[
,
]
range
LB
UB
, then the value u will be eliminated from the candidate set.
6.3.5 Combination of Strategies
In previous sections, we have introduced four strategies to reduce the search space,
including: init-block, double lexicographic order, LNH and SCEH. Now an important
question naturally arises: Can these strategies be used together during the search? The
 
 
Search WWH ::




Custom Search