2维约束覆盖数组最小规模下限的提升

针对现有方法评价2维约束覆盖时没有考虑约束,而给出的最小规模过大的问题.为获得更准确的2维约束覆盖数组的最小规模,评价现有算法生成的2维约束覆盖数组,本文提出一种可以提升2维约束覆盖数组最小规模下限的禁忌边分解方法.采用禁忌边分解方法将描述被测系统输入配置的图分解成两个子图,通过计算覆盖两个子图中全部顶点的子覆盖数组的规模和剩余需要覆盖的取值组合数,与单纯计算需要覆盖的取值组合数相比,提升了2维约束覆盖数组的最小规模,所提出的方法能够得到更逼近真实值的最小规模的下限,一旦2维约束覆盖数组的规模小于最小规模的下限,则其不可能存在.本文的实验方法是,将禁忌边分解方法应用到现有的被测系统中,得到其2维约束覆盖数组最小规模的下限,将最小规模的下限与生成算法给出的2维约束覆盖数组的规模进行对比.实验结果表明:禁忌边分解方法给出的最小规模下限可以用于评价现有算法生成的2维约束覆盖数组,有助于判断其是否真实存在.

Promotion of lower bounds of minimum sizes of 2-way constrained covering arrays

When evaluating 2-way constrained covering arrays, the minimum sizes given by the existing methods are too large because the constraints are ignored. In order to obtain more accurate minimum sizes of 2-way constrained covering arrays and evaluate the 2-way constrained covering arrays generated by existing algorithms, a forbidden edge decomposing method was proposed to promote lower bounds of the minimum sizes of 2-way constrained covering arrays in this study. The graphs that describe the input configurations of the systems under test were decomposed into two subgraphs. Through calculating the sizes of the sub constrained covering arrays which cover all the vertices in the two subgraphs and the number of the remaining value combinations to be covered, the minimum sizes of the 2-way constrained covering arrays were promoted compared with the number of the value combinations to be covered. The lower bounds of the minimum sizes obtained from the proposed method were closer to the real values. If the sizes of the 2-way constrained covering arrays are less than the lower bounds of the minimum sizes, then it is impossible for them to exist. The proposed experimental method applied the forbidden edge decomposing method to the existing systems under test, then obtained the lower bounds of the minimum sizes of 2-way constrained covering arrays, and compared the lower bounds of the minimum sizes with the sizes of the 2-way constrained covering arrays given by the generation algorithms. The experimental results show that the lower bounds of the minimum sizes given by the forbidden edge decomposing method can be used to evaluate the 2-way constrained covering arrays generated by the existing algorithms, and are helpful to determine their existence.