測試用例設計中的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表示解決某一問題所需要的各種技巧的集合，另外有一個給定的可用來解決該問題的人的集合，也就是說對于技巧集合種的每種技巧，至少有一人掌握該種技巧�，F在的問題是如何選取最少數量的人組成一個委員會，使得技巧集合中的任一技巧，委員會里至少有一位委員掌握該種技巧。將這個例子對比最少測試用例數問題的數學模型，會發現這是同一個問題。

　　雖然最少測試用例數是一個NP完全性問題，但在實際情況中，大多數情況下測試用例數并不是太多，得到精確解的可能性還是很大的，只有那些比較復雜的有組合關系的情況下，用例數可能會存在一定的冗余。

文章來源于領測軟件測試網 http://www.kjueaiud.com/