陈阳梅，丁晓明

(1.西南大学 计算机与信息科学学院，重庆400715;2.重庆市智能软件与软件工程重点实验室，重庆400715)

软件测试是保证软件质量和可靠性的重要手段。在进行软件测试时，测试人员首先确定软件测试需求，并根据该测试需求集设计出一套完整的测试用例，该测试用例集满足所有的测试需求。由此，该测试用例集的数量和质量决定软件测试的成本和有效性。在软件开发过程中，由于各模块的不断修改完善，各模块的不断添加和融合以及最后对整个系统的可靠性和有效性验证，需要频繁地进行回归测试，在此过程中测试用例集的数量将会越来越大，其中的冗余测试用例也会越来越多。为了提高软件测试效率，降低测试成本，这就很有必要地进行测试用例集约简。

1 测试用例集约简相关概念

1993年，M.J.Harrold等人首次提出了测试用例集约简的概念［1］。令测试用例集T与测试需求集R的二元关系S(T，R)={(t，r)∈T×R:测试用例t满足测试需求r}，即S(T，R)表示测试用例t∈T与测试需求r∈R的满足关系［8］。

如表1所示，测试需求集R={r1，r2，…，r6}，测试用例集 T={t1，t2，…，t7}以及集合 R与集合 T的关系S(T，R)。

由表1可知，T1={t1，t3，t7}即可满足所有的测试需求并且T1是T的子集。在测试用例集T中存在着两种测试用例，一种是对于测试来说必不可少的测试用例，另一种是冗余的测试用例，这些测试用例对测试本身来说并没有执行的价值，相反，执行它们反而会增加测试成本。测试用例集约简问题:令测试需求集R={r1，r2，…，rm}，并有测试用例集T={t1，t2，…，tn}满足所有的测……