窮舉測試（exhaustive testing）：亦稱完全測試，即程式運行的各個可能分支都應該調試到。窮舉法，可視為最簡單的搜尋。即是在一個可能存在可行狀態的狀態全集中依次遍歷所有的元素，並判斷是否為可行狀態
基本介紹
- 中文名：窮舉測試
- 外文名：exhaustive testing
介紹,狀態全集,可行狀態,狀態跳轉,判斷標準,
介紹
窮舉法 可視為最簡單的搜尋：即是在一個可能存在可行狀態（可行解）的狀態全集中依次遍歷所有的元素，並判斷是否為可行狀態。例如，要設計一個“從一堆蘋果中找出藍色的蘋果”這樣的窮舉算法，則定義：
狀態全集
：一堆蘋果
可行狀態
：藍色的蘋果
噢，好，我們現在已經抽取了兩個基本概念，迫不及待要開始窮舉了，但……怎么做呢？窮舉的關鍵是“依次遍歷”，即做到不重、不漏。呃，我們可以讓聽話的蘋果們排成一行，放在“蘋果數組”中，然後呢，我們就可以按照0號蘋果、1號蘋果、2號蘋果、...、n號蘋果這樣的順序成功遍歷。好，我們解決了遍歷蘋果的問題……慢，我們現在是設計一個算法的抽象模型，如果一切待窮舉的對象都已經活生生地擺在那裡，當然有可能把它們全部收集起來並排隊，但如果開始的時候我們並不知道所有要窮舉的對象，比如我們或許要通過一台安裝在探測飛船內的計算機在全宇宙範圍內窮舉出除地球以外有生命的星球，那么我們的計算機可能是隨著飛船的前行方能不斷地得到新星球的信息，而不是停在地球的時候就獲得全宇宙的星球信息（就算可能，記憶體或許也裝不下如此大的數據量——哪怕宇宙真的是有限“大”的）。所以我們不應當要求窮舉進行之前就能獲得狀態全集中的所有狀態，這樣一來，我們的“蘋果數組”計畫就宣告流產了。現在再看看我們激動人心的星球搜尋計畫：它並沒有把所有星球收羅排隊，那么它成功的關鍵在哪裡？在於飛船能否以適當的路徑“光顧”完所有的星球；我們把這個條件加強一下：飛船每次到達一個星球，都會看到星球上立著一個方向標，標示下一個星球的方位；而假定這樣的標示保證飛船能夠不重不漏地飛臨宇宙中的所有星球。啊喔……你是不是覺得我這是在異想天開？喔，沒關係，大不了我們不搜尋星球了，而除此之外的很多現實窮舉問題都可以滿足這個加強條件。嗯，我承認本文討論的是滿足這個加強條件的稍稍狹義的窮舉：它必須保證在知道一個狀態的前提下能獲得一個新狀態，並且這樣的“狀態鏈”剛好能遍歷整個狀態全集。我們稱從當前狀態獲得並轉到下一個狀態的過程為“狀態跳轉”（我是想用“狀態轉移”的，嗨，可惜它會與動態規划算法的術語相混淆）：
狀態跳轉
：根據當前得到的蘋果，按一定的“遍歷算法”取得下一個蘋果；這個算法保證不重不漏地取遍蘋果堆中的所有蘋果，只要所取的第一個蘋果也是按算法定義給出的
很顯然，對於不同的窮舉任務，都會有不同的遍歷算法，所以這樣一來我們就得將其實現下放給調用我們“窮舉算法庫”的用戶們了。不過考慮到這的確是由於問題的多樣性所決定的，因而這個要求應當是合理的。
嗯啊，現在我們已經有了蘋果源，目標蘋果，乃至遍歷蘋果的方案（用戶提供），接下來還差一個判斷標準，這個倒簡單了：
判斷標準
：當前蘋果是否為藍色的蘋果
下一步，我們就可以考慮“the classof窮舉算法”的具體實現了。我們把這個class的名字定義為WalkThrough.
首先，讓我們注意到，“狀態”是一個很重要的概念：不同的窮舉問題都有彼此不同的狀態，在蘋果問題中，“狀態”是蘋果，它包含了蘋果顏色或者更多的信息；而在星球搜尋計畫中，“狀態”則是星球，它可能包含該星球的體積、平均密度、溫度、是否有大氣、是否探測到水、星表活動狀況等一系列豐富得驚人的信息。因此，不同狀態(state)對應不同的數據類型，要讓WalkThrough能處理它們，有必要使用模板，於是我們的最初定義如下：
template
class WalkThrough
;
萬事開頭難，但現在我們顯然已經開了一個不錯的頭，嗯，繼續。在考慮具體實現之前，先幻想一下我們的WalkThrough能為用戶提供怎樣的服務——當然，它的本職工作是找到並返回可行狀態，因此它似乎應該有一個類似於getFilter()的成員函式。問題是，如果可行狀態不止一個時，getFilter()應當返回一個可行狀態還是所有的可行狀態？不難想像，返回所有可行狀態的作法並不太現實，因為：1.有時候用戶只需要一個，或者少數幾個可行狀態，此時把所有的可行狀態都窮舉出來顯然是低效而不必要的；2.甚至，有些問題的可行狀態數量是無限的，如窮舉素數，此時返回所有狀態當然不可能。同時考慮到用戶要求的仍有可能是不止一個可行解，我們現在知道，應當提供一個getNextFilter()而不是getFilter()的函式：第一次調用它時，將返回從初始狀態開始，依序遍歷到的第一個可行狀態；而此後的調用都將以上次調用為起點繼續向前遍歷，返回下一個可行狀態。需要注意的是，如果已經遍歷完了狀態全集，顯然再調用此函式是沒有意義的，所以它應當返回一個標誌，反饋給用戶是否遍歷已經完成。我們將這個函式定義為bool，如果調用有效，則返回true，反之如果已經完成遍歷，則返回false.顯然，我們相應需要一個私有的State對象變數curState，它用於存儲當前的狀態值。
我們是否應當給getNextFilter加上一個State引用參數，以向用戶返回每次窮舉到的可行狀態？在這裡我們並沒有這樣做。試想，可能用戶會想獲得第5個遍歷到的可行狀態，那么他當然就要調用5次getNextFilter()，但前4次他並不要求得到所搜尋到的可行狀態。所以，我們將“找到下一個可行狀態”與“獲得當前找到的可行狀態”分離開來，新增加一個getState()成員函式，它返回一個State對象，注意到getState()操作並不影響WalkThrough對象的內部狀態，所以它同時應被聲明為const成員函式。
相應地，我們需要一個setState()成員函式，它用於改變當前的狀態值，例如設定初始狀態的時候都有可能用到。它帶一個constState&類型的參數，用以指定所要設定的State值，由於State可能是一個較大的類型，所以使用引用傳遞能保證效率，同時加上const限制則保證該函式不會更改所傳入的引用對象本身的值。
同時用戶可能需要知道，對於一個窮舉對象，是否已經完成窮舉，當然他可以調用getNextFilter()並檢查返回值，但如果遍歷沒有完成，則getNextFilter()除了最後返回true之外還會額外地進行搜尋，並將當前狀態改為下一個可行狀態，這份額外的工作可能並不是用戶所期望需要的。因此我們將增加一個成員函式isOver()，它不帶參數，返回一個bool值：如果已經完成遍歷，返回true，反之返回false.相應地，我們需要一個私有bool變數overFlag，它用於存儲isOver()所需要的狀態值。
至此，WalkThrough的定義如下：
template
class WalkThrough
public:
void setState(const State& s) curState = s;
State getState() const return curState;
bool getNextFilter();
bool isOver() const return overFlag;
private:
State curState;
bool overFlag;
;
我們把構造函式與析構函式置後，先考慮起關鍵作用的getNextFilter()的實現。首先，getNextFileter()由當前的狀態跳轉為下一狀態，然後判斷新狀態是否為可行，若可行，則停止跳轉並返回true，否則繼續跳轉，重複上述步驟。另一方面，如果已經完成了遍歷而還沒有找到可行狀態，則將overFlag設為false並且返回false.
我們將跳轉操作、判斷是否為可行狀態操作下放給用戶實現：用戶相應提供兩個函式，然後向WalkThrough對象傳入函式指針，供getNextFileter()調用。那么這兩個函式應該採用什麼樣的接口形式比較合適呢？先看看跳轉函式，一個很直觀的實現是傳入一個State對象（或其const引用），然後返回“下一個”State對象，不過至少在返回的時候，值傳遞會產生State對象的複製操作（諸如NRV最佳化之類的語言標準外的特定編譯器實現不在討論之列），當State對象比較大的時候，開銷是不值得的。我們應當考慮傳入State對象的引用，然後“全權委託”跳轉函式進行直接修改——把它“變”成下一個狀態。可能會有人質疑這樣做是否違反了封裝原則，但即使摒棄效率方面的權衡，這樣做也是合情合理的。跳轉函式——不妨視為負責“狀態轉化”函式，就像一個煉丹爐——有權利、甚至有義務這樣做，它的職責是“轉化狀態”而非“獲得狀態”。唔……我都覺得自己在語言上過於細究了。嗯，除了轉化狀態，跳轉函式在發現遍歷完成之後也應當及時告知調用它的getNextFilter()，否則下放了大部分權力的getNextFilter()是無從知曉的。於是我們的跳轉函式接口為：接受一個State的引用，返回一個bool值。如果遍歷沒有完成，那么函式執行完畢之後State引用將變為它的後繼狀態，且函式返回true；否則State不變，函式返回false.
判斷是否為可行狀態的函式接口則很好定義了：它接受一個constState型引用作為待判斷的狀態，返回bool值，其中true表示該狀態為可行狀態，false表示該狀態不是可行狀態。
我們將跳轉函式以及判斷函式的函式指針類型分別定義為StateJumper及Matcher，由於用戶可能也會用到這些函式指針類型，我們將定義加到public域中：
public:
typedef bool (*StateJumper)(State&);
typedef bool (*Matcher)(const State&);
// others...
並且，在private域中相應加上StateJumper和Matcher的函式指針變數，存儲用戶提供的相應函式的地址：
private:
// others...
StateJumper Jumper;
Matcher IsMatch;
相應地，內聯定義公有成員函式：
void setJumper(const StateJumper j) Jumper = j;
void setMatcher(const Matcher m) IsMatch = m;
分別用於設定Jumper和IsMatch的函式指針值。
現在所有的成員變數都已經浮出水面，我們可以定義構造函式和析夠函式了，我們不打算對WalkThrough的創建與繼承等方面作限制，因此它們都加在public域中。先看構造函式，有必要定義一個默認構造函式：
WalkThrough(): overFlag(false), Jumper(0), IsMatch(0)
這個構造函式不指定任何初始條件，包括當前狀態。可以在需要的時候使用一系列的set成員函式定義。
接下來定義一個“全功能”的構造函式：
WalkThrough(const State& s, StateJumper j = 0, Matcher m=0)
: overFlag(false), curState(s), Jumper(j), IsMatch(m)
對於拷貝構造函式，由於我們這裡沒有涉及記憶體分配，沒有“深拷貝”的需求，因此不作定義，使用默認的位拷貝可以有不錯的效率。類似地，析構函式也沒有什麼事務需要處理，不過考慮到這個WalkThrough可能用於繼承，且有可能出現delete基類指針來刪除派生對象的情況，便定義一個空的虛析構函式，以免引起錯誤：
virtual ~WalkThrough()
最後，我們來實現唯一的一個非內聯函式：getNextFilter()，在給出實現之前順便給出完整的WalkThrough的定義：
template
class WalkThrough
public:
typedef bool (*StateJumper)(State&);
typedef bool (*Matcher)(const State&);
WalkThrough(): overFlag(false), Jumper(0), IsMatch(0)
WalkThrough(const State& s, StateJumper j = 0, Matcher m=0)
: overFlag(false), curState(s), Jumper(j), IsMatch(m)
virtual ~WalkThrough()
void setJumper(const StateJumper j) Jumper = j;
void setMatcher(const Matcher m) IsMatch = m;
void setState(const State& s) curState = s;
State getState() const return curState;
bool getNextFilter();
bool isOver() const return overFlag;
private:
State curState;
bool overFlag;
StateJumper Jumper;
Matcher IsMatch;
;
template
bool WalkThrough::getNextFilter()
if (overFlag) // 若已完成遍歷，則直接返回
return false;
if (!Jumper!IsMatch) // 若用戶未定義Jumper或IsMatch函式，則返回
overFlag = true; // 這裡將沒有定義Jumper或IsMatch的窮舉視為遍歷完成
return false; // 不過，如果你認為兩者絕不能等同，也可以拋出異常
while (!(overFlag = !Jumper(curState))&&!IsMatch(curState))
; // 獲取下一狀態，直到找到可行狀態或者遍歷完成
if (overFlag) // 根據遍歷完成情況決定返回值
return false;
else
