测试用例设计中的NP难题

　如何划分测试空间才能以尽量少的子集来覆盖整个测试空间属于测试用例设计的优化问题。从数学上来讲，这实际上是一个NP完全性问题。下面就来讲解为什么最少测试用例数问题是一个NP完全性问题。

　　要说明这个问题，首先需要建立求解最小测试用例数的数学模型。

　　假设在测试空间里有n个可测数据组成的集合记为D = {d1，…dn}，假设测试空间里有m个可能的缺陷，把m个缺陷个缺陷集合记为B = {b1，…bm}。对于每个可测数据，都可能揭示出缺陷集合B中的若干个可能的错误，也就是说对每个可测数据能揭示的缺陷集合是B的一个子集，分别记这些子集为e1，…en ，(ei ∈B, 1≤ i ≤ n)。

　　由于测试空间里的任一缺陷都是由可测数据来引起的，因此对于任一缺陷bk∈B（1≤ k ≤ n），必然存在一个可测数据di∈D（1≤ i ≤ n）可以揭示出这个缺陷，也就是说存在集合ei ( 1≤ i ≤ n)，使得bk ∈ei。

　　最少的测试用例数问题是找出最少个数的测试用例，使用这些测试用例能将缺陷集合中的缺陷全部揭示出来。实际上就是要找出若干个子集ei（1≤ i ≤ n），使得这些子集的成员可以覆盖集合B的所有成员。

　　这样就建立起了最少测试用例数的数学模型，它属于数学中的集合覆盖问题，是一个典型的NP完全性问题。目前还找不到精确的多项式算法来解决这个问题，只能设计一些近似算法来对这个问题进行求解，后面讲的测试用例设计方法其实都是对这个问题的一种近似求解算法。

　　如果要了解集合覆盖问题的近似求解数学算法，可以参考Thomas H. Cormen等著的《算法导论》一书的35.3节，里面有详细的讲解。

　　《算法导论》一书里也举了一个集合覆盖问题的另外一个实际例子：假设X表示解决某一问题所需要的各种技巧的集合，另外有一个给定的可用来解决该问题的人的集合，也就是说对于技巧集合种的每种技巧，至少有一人掌握该种技巧。现在的问题是如何选取最少数量的人组成一个委员会，使得技巧集合中的任一技巧，委员会里至少有一位委员掌握该种技巧。将这个例子对比最少测试用例数问题的数学模型，会发现这是同一个问题。

　　虽然最少测试用例数是一个NP完全性问题，但在实际情况中，大多数情况下测试用例数并不是太多，得到精确解的可能性还是很大的，只有那些比较复杂的有组合关系的情况下，用例数可能会存在一定的冗余。

原文转自：http://www.ltesting.net