6.1.3　测试用例集约简的数学建模

6.1.3　测试用例集约简的数学建模

测试用例集约简问题的输入为T、R、S和C,其目标为经过约简,得到一个T的子集RS,其中RS的测试用例可以满足所有的测试需求,并且测试开销尽可能小。

令测试需求集为R={r 1,r 2,…,rm},测试用例集为T={t 1,t 2,…,t n},∃T 1⊂T,其中,T 1满足R,有∀T x⊂T,使得T x的测试开销大于等于T 1的测试开销。因此,这是一个最小集合覆盖问题,属于典型的NP-Complete问题,无法用传统的方法得到最优解。

下面给出一个测试用例集约简的实例。如表6-1所示,测试用例集T内包含5个测试用例{t 1,t 2,t 3,t 4,t 5},测试需求集包含6个需求{r 1,r 2,r 3,r 4,r 5,r 6},其中的代表的是测试关系,每个测试用例分别都对应一个测试开销。实际上,这组测试用例是有冗余的,不考虑开销的情况下,只需要{t 1,t 2}便可以覆盖全部测试点,因此另外3个便是需要约简的冗余测试用例。

表6-1　测试用例集实例

(https://www.daowen.com)

将上述问题转化为数学问题,可以等价于以下形式:测试用例集和测试需求分别代表矩阵的行和列,测试用例i满足测试需求j的测试关系表示为S ij=1,测试开销表示为一个向量,则可以将表6-1转换为下述矩阵:

即问题可以表示为一个m行n列的0-1矩阵,目的是在开销最小的情况下,选择一部分矩阵的行,使其覆盖矩阵所有的列。设向量x表示约简结果,x i=1表示行i被选中,可以覆盖Sij=1各行对应的测试功能点,问题求解目标表示为式(6-1)和式(6-2):

式(6-1)为约简目标,式(6-2)为约束,表示每个测试点都需要被覆盖。