閑談C++算法封裝：窮舉法

?

??? 將 算法獨立抽象出來，在C++中算不上新鮮：STL中就封裝了不少高效、健壯、靈活的泛型組件及對應的基礎算法，工藝之高、適用性之強，非尋常我輩所輕易能 及。這里不打算（也暫沒有能力打算）以STL這樣的工業(yè)級要求來談論算法封裝，只因最近嘗翻大師名著，閱者水平有限，僅嗅觸至皮毛，理智薄弱，感情卻蓬勃 發(fā)展：也欲嘗試“封裝”的味道。選擇了最簡易的窮舉算法，抽其骨架，炮制成class，套上一實際例子，觀之run之，抽象程度頗低，效率損失彌彰；然卻 也自覺有可愛之處，遂作此文以記之。誠惶誠恐，便于名目之前加“閑談”二字，倘果因技術(shù)問題招致痛罵，則試以此二字為護文符，聊且一擋。

?

??? 眾所周知，窮舉法可視為最簡單的搜索：即是在一個可能存在可行狀態(tài)（可行解）的狀態(tài)全集中依次遍歷所有的元素，并判斷是否為可行狀態(tài)。例如，要設計一個“從一堆蘋果中找出藍色的蘋果”這樣的窮舉算法，則定義：

??? (1) 狀態(tài)全集：一堆蘋果

??? (2) 可行狀態(tài)：藍色的蘋果

??? 噢， 好，我們現(xiàn)在已經(jīng)抽取了兩個基本概念，迫不及待要開始窮舉了，但……怎么做呢？窮舉的關(guān)鍵是“依次遍歷”，即做到不重、不漏。呃，我們可以讓聽話的蘋果們 排成一行，放在“蘋果數(shù)組”中，然后呢，我們就可以按照0號蘋果、1號蘋果、2號蘋果、...、n號蘋果這樣的順序成功遍歷。好，我們解決了遍歷蘋果的問 題……慢，我們現(xiàn)在是設計一個算法的抽象模型，如果一切待窮舉的對象都已經(jīng)活生生地擺在那里，當然有可能把它們?nèi)渴占饋聿⑴抨牐绻_始的時候我們 并不知道所有要窮舉的對象，比如我們或許要通過一臺安裝在探測飛船內(nèi)的計算機在全宇宙范圍內(nèi)窮舉出除地球以外有生命的星球，那么我們的計算機可能是隨著飛 船的前行方能不斷地得到新星球的信息，而不是停在地球的時候就獲得全宇宙的星球信息（就算可能，內(nèi)存或許也裝不下如此大的數(shù)據(jù)量——哪怕宇宙真的是有限 “大”的）。所以我們不應當要求窮舉進行之前就能獲得狀態(tài)全集中的所有狀態(tài)，這樣一來，我們的“蘋果數(shù)組”計劃就宣告流產(chǎn)了。現(xiàn)在再看看我們激動人心的星 球搜索計劃：它并沒有把所有星球收羅排隊，那么它成功的關(guān)鍵在哪里？在于飛船能否以適當?shù)穆窂健肮忸櫋蓖晁械男乔颍晃覀儼堰@個條件加強一下：飛船每次到 達一個星球，都會看到星球上立著一個方向標，標示下一個星球的方位；而假定這樣的標示保證飛船能夠不重不漏地飛臨宇宙中的所有星球。啊喔……你是不是覺得 我這是在異想天開？哦，沒關(guān)系，大不了我們不搜索星球了，而除此之外的很多現(xiàn)實窮舉問題都可以滿足這個加強條件。嗯，我承認本文討論的是滿足這個加強條件 的稍稍狹義的窮舉：它必須保證在知道一個狀態(tài)的前提下能獲得一個新狀態(tài)，并且這樣的“狀態(tài)鏈”剛好能遍歷整個狀態(tài)全集。我們稱從當前狀態(tài)獲得并轉(zhuǎn)到下一個 狀態(tài)的過程為“狀態(tài)跳轉(zhuǎn)”（我是想用“狀態(tài)轉(zhuǎn)移”的，嗨，可惜它會與動態(tài)規(guī)劃算法的術(shù)語相混淆）：

??? (3) 狀態(tài)跳轉(zhuǎn)：根據(jù)當前得到的蘋果，按一定的“遍歷算法”取得下一個蘋果；這個算法保證不重不漏地取遍蘋果堆中的所有蘋果，只要所取的第一個蘋果也是按算法定義給出的

??? 很顯然，對于不同的窮舉任務，都會有不同的遍歷算法，所以這樣一來我們就得將其實現(xiàn)下放給調(diào)用我們“窮舉算法庫”的用戶們了。不過考慮到這的確是由于問題的多樣性所決定的，因而這個要求應當是合理的。

??? 嗯啊，現(xiàn)在我們已經(jīng)有了蘋果源，目標蘋果，乃至遍歷蘋果的方案（用戶提供），接下來還差一個判斷標準，這個倒簡單了：

??? (4) 判斷標準：當前蘋果是否為藍色的蘋果

??? 下一步，我們就可以考慮“the class of 窮舉算法”的具體實現(xiàn)了。我們把這個class的名字定義為WalkThrough.

?

??? 首 先，讓我們注意到，“狀態(tài)”是一個很重要的概念：不同的窮舉問題都有彼此不同的狀態(tài)，在蘋果問題中，“狀態(tài)”是蘋果，它包含了蘋果顏色或者更多的信息；而 在星球搜索計劃中，“狀態(tài)”則是星球，它可能包含該星球的體積、平均密度、溫度、是否有大氣、是否探測到水、星表活動狀況等一系列豐富得驚人的信息。因 此，不同狀態(tài)(state)對應不同的數(shù)據(jù)類型，要讓WalkThrough能處理它們，有必要使用模板，于是我們的最初定義如下：

?

template <class State>

class WalkThrough

{

?

};

?

??? 萬 事開頭難，但現(xiàn)在我們顯然已經(jīng)開了一個不錯的頭，嗯，繼續(xù)。在考慮具體實現(xiàn)之前，先幻想一下我們的WalkThrough能為用戶提供怎樣的服務——當 然，它的本職工作是找到并返回可行狀態(tài)，因此它似乎應該有一個類似于getFilter()的成員函數(shù)。問題是，如果可行狀態(tài)不止一個時， getFilter()應當返回一個可行狀態(tài)還是所有的可行狀態(tài)？不難想象，返回所有可行狀態(tài)的作法并不太現(xiàn)實，因為：1.有時候用戶只需要一個，或者少 數(shù)幾個可行狀態(tài)，此時把所有的可行狀態(tài)都窮舉出來顯然是低效而不必要的；2.甚至，有些問題的可行狀態(tài)數(shù)量是無限的，如窮舉素數(shù)，此時返回所有狀態(tài)當然不 可能。同時考慮到用戶要求的仍有可能是不止一個可行解，我們現(xiàn)在知道，應當提供一個getNextFilter()而不是getFilter()的函數(shù)： 第一次調(diào)用它時，將返回從初始狀態(tài)開始，依序遍歷到的第一個可行狀態(tài)；而此后的調(diào)用都將以上次調(diào)用為起點繼續(xù)向前遍歷，返回下一個可行狀態(tài)。需要注意的 是，如果已經(jīng)遍歷完了狀態(tài)全集，顯然再調(diào)用此函數(shù)是沒有意義的，所以它應當返回一個標志，反饋給用戶是否遍歷已經(jīng)完成。我們將這個函數(shù)定義為bool，如 果調(diào)用有效，則返回true，反之如果已經(jīng)完成遍歷，則返回false. 顯然，我們相應需要一個私有的State對象變量curState，它用于存儲當前的狀態(tài)值。

??? 我 們是否應當給getNextFilter加上一個State引用參數(shù)，以向用戶返回每次窮舉到的可行狀態(tài)？在這里我們并沒有這樣做。試想，可能用戶會想獲 得第5個遍歷到的可行狀態(tài)，那么他當然就要調(diào)用5次getNextFilter()，但前4次他并不要求得到所搜索到的可行狀態(tài)。所以，我們將“找到下一 個可行狀態(tài)”與“獲得當前找到的可行狀態(tài)”分離開來，新增加一個getState()成員函數(shù)，它返回一個State對象，注意到getState()操 作并不影響WalkThrough對象的內(nèi)部狀態(tài)，所以它同時應被聲明為const成員函數(shù)。

??? 相 應地，我們需要一個setState()成員函數(shù)，它用于改變當前的狀態(tài)值，例如設置初始狀態(tài)的時候都有可能用到。它帶一個const State&類型的參數(shù)，用以指定所要設定的State值，由于State可能是一個較大的類型，所以使用引用傳遞能保證效率，同時加上 const限制則保證該函數(shù)不會更改所傳入的引用對象本身的值。

??? 同 時用戶可能需要知道，對于一個窮舉對象，是否已經(jīng)完成窮舉，當然他可以調(diào)用getNextFilter()并檢查返回值，但如果遍歷沒有完成，則 getNextFilter()除了最后返回true之外還會額外地進行搜索，并將當前狀態(tài)改為下一個可行狀態(tài)，這份額外的工作可能并不是用戶所期望需要 的。因此我們將增加一個成員函數(shù)isOver()，它不帶參數(shù)，返回一個bool值：如果已經(jīng)完成遍歷，返回true，反之返回false. 相應地，我們需要一個私有bool變量overFlag，它用于存儲isOver()所需要的狀態(tài)值。

??? 至此，WalkThrough的定義如下：

?

template<class State>

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;

};

?

??? 我 們把構(gòu)造函數(shù)與析構(gòu)函數(shù)置后，先考慮起關(guān)鍵作用的getNextFilter()的實現(xiàn)。首先，getNextFileter()由當前的狀態(tài)跳轉(zhuǎn)為下一 狀態(tài)，然后判斷新狀態(tài)是否為可行，若可行，則停止跳轉(zhuǎn)并返回true，否則繼續(xù)跳轉(zhuǎn)，重復上述步驟。另一方面，如果已經(jīng)完成了遍歷而還沒有找到可行狀態(tài)， 則將overFlag設為false并且返回false.

??? 我 們將跳轉(zhuǎn)操作、判斷是否為可行狀態(tài)操作下放給用戶實現(xiàn)：用戶相應提供兩個函數(shù)，然后向WalkThrough對象傳入函數(shù)指針，供 getNextFileter()調(diào)用。那么這兩個函數(shù)應該采用什么樣的接口形式比較合適呢？先看看跳轉(zhuǎn)函數(shù)，一個很直觀的實現(xiàn)是傳入一個State對象 （或其const引用），然后返回“下一個”State對象，不過至少在返回的時候，值傳遞會產(chǎn)生State對象的復制操作（諸如NRV優(yōu)化之類的語言標 準外的特定編譯器實現(xiàn)不在討論之列），當State對象比較大的時候，開銷是不值得的。我們應當考慮傳入State對象的引用，然后“全權(quán)委托”跳轉(zhuǎn)函數(shù) 進行直接修改——把它“變”成下一個狀態(tài)。可能會有人質(zhì)疑這樣做是否違反了封裝原則，但即使摒棄效率方面的權(quán)衡，這樣做也是合情合理的。跳轉(zhuǎn)函數(shù)——不妨 視為負責“狀態(tài)轉(zhuǎn)化”函數(shù)，就像一個煉丹爐——有權(quán)利、甚至有義務這樣做，它的職責是“轉(zhuǎn)化狀態(tài)”而非“獲得狀態(tài)”。唔……我都覺得自己在語言上過于細究 了。嗯，除了轉(zhuǎn)化狀態(tài)，跳轉(zhuǎn)函數(shù)在發(fā)現(xiàn)遍歷完成之后也應當及時告知調(diào)用它的getNextFilter()，否則下放了大部分權(quán)力的 getNextFilter()是無從知曉的。于是我們的跳轉(zhuǎn)函數(shù)接口為：接受一個State的引用，返回一個bool值。如果遍歷沒有完成，那么函數(shù)執(zhí) 行完畢之后State引用將變?yōu)樗暮罄^狀態(tài)，且函數(shù)返回true；否則State不變，函數(shù)返回false.

??? 判斷是否為可行狀態(tài)的函數(shù)接口則很好定義了：它接受一個const State型引用作為待判斷的狀態(tài)，返回bool值，其中true表示該狀態(tài)為可行狀態(tài)，false表示該狀態(tài)不是可行狀態(tài)。

??? 我們將跳轉(zhuǎn)函數(shù)以及判斷函數(shù)的函數(shù)指針類型分別定義為StateJumper及Matcher，由于用戶可能也會用到這些函數(shù)指針類型，我們將定義加到public域中：

?

public:

??? typedef bool (*StateJumper)(State&);

??? typedef bool (*Matcher)(const State&);

?

// others...

?

??? 并且，在private域中相應加上StateJumper和Matcher的函數(shù)指針變量，存儲用戶提供的相應函數(shù)的地址：

?

private:

??? // others...

??? StateJumper Jumper;

??? Matcher IsMatch;

?

??? 相應地，內(nèi)聯(lián)定義公有成員函數(shù)：

?

??? void setJumper(const StateJumper j) { Jumper = j; }

??? void setMatcher(const Matcher m) { IsMatch = m; }

?

??? 分別用于設置Jumper和IsMatch的函數(shù)指針值。

??? 現(xiàn)在所有的成員變量都已經(jīng)浮出水面，我們可以定義構(gòu)造函數(shù)和析夠函數(shù)了，我們不打算對WalkThrough的創(chuàng)建與繼承等方面作限制，因此它們都加在public域中。先看構(gòu)造函數(shù)，有必要定義一個默認構(gòu)造函數(shù)：

?

??? WalkThrough(): overFlag(false), Jumper(0), IsMatch(0) { }

?

??? 這個構(gòu)造函數(shù)不指定任何初始條件，包括當前狀態(tài)。可以在需要的時候使用一系列的set成員函數(shù)定義。

??? 接下來定義一個“全功能”的構(gòu)造函數(shù)：

?

??? WalkThrough(const State& s, StateJumper j = 0, Matcher m = 0)

??? : overFlag(false), curState(s), Jumper(j), IsMatch(m) { }

?

??? 除了overFlag外，所有的屬性都可以在這個構(gòu)造函數(shù)中設定（當然，它允許缺省值）。由于沒有進行任何窮舉操作，將overFlag強制為false是合理的。

??? 對 于拷貝構(gòu)造函數(shù)，由于我們這里沒有涉及內(nèi)存分配，沒有“深拷貝”的需求，因此不作定義，使用默認的位拷貝可以有不錯的效率。類似地，析構(gòu)函數(shù)也沒有什么事 務需要處理，不過考慮到這個WalkThrough可能用于繼承，且有可能出現(xiàn)delete基類指針來刪除派生對象的情況，便定義一個空的虛析構(gòu)函數(shù)，以 免引起錯誤：

?

??? virtual ~WalkThrough() { }

?

??? 最后，我們來實現(xiàn)唯一的一個非內(nèi)聯(lián)函數(shù)：getNextFilter()，在給出實現(xiàn)之前順便給出完整的WalkThrough的定義：

?

template <class State>

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 <class State>

bool WalkThrough<State>::getNextFilter()

{

??? if (overFlag)? // 若已完成遍歷，則直接返回

??? return false;

??? if (!Jumper || !IsMatch)? // 若用戶未定義Jumper或IsMatch函數(shù)，則返回

??? {

??? ??? overFlag = true;? // 這里將沒有定義Jumper或IsMatch的窮舉視為遍歷完成

??? ??? return false;???? // 不過，如果你認為兩者絕不能等同，也可以拋出異常

??? }

??? while (!(overFlag = !Jumper(curState)) && !IsMatch(curState))

??? ;? // 獲取下一狀態(tài)，直到找到可行狀態(tài)或者遍歷完成

??? if (overFlag)?? // 根據(jù)遍歷完成情況決定返回值

??? ??? return false;

?? ?else

??? ??? return true;

}

?

??? 呼……小功告成，總算可以小松一口氣。不過如果到此就關(guān)閉計算機，就像直播球賽進行到高潮時突然停電一樣，太令人不爽。——弄了這么久，總該給個example試一試，來點成就感吧？

??? 沒 問題。蘋果問題太簡單，于是我們選擇的是一個傳說中的“和是50”超級難題，什么是“和是50”超級難題？請聽好了：所謂“和是50”超級難題，就是在0 到99的整數(shù)組成的一個加法算式中，找出和是50的算式，考慮加數(shù)順序，像0+50啊，1+49啊，……，49+1啊，50+0啊……（喂，我知道你可能 想殺人，但請不要讓與之匹配的眼光朝著我……）對于這樣一個超級難題，我們經(jīng)過研究，決定采用……窮舉法來實現(xiàn)（哪來的這么多西紅柿？）。

??? 首先我們研究這個問題的狀態(tài)是什么——兩個加數(shù)，不是么，它們是有順序的，并且可以取0到99的整數(shù)。于是乎，我們定義狀態(tài)類如下（注：STL中有類似的東西，但作為完整的示例，我們親自手工打造）：

?

class Pair

{

public:

??? Pair(int mx = 0, int my = 0): x(mx), y(my) { }

??? int x, y;

};

?

??? Pair雖然屬于世界上最深奧的class之一，然而憑各位的智慧，我就不用多解釋了。接著我們來看一下跳轉(zhuǎn)函數(shù)的實現(xiàn)——當然，它應當符合WalkThrough中定義的StateJumper類型：

?

bool counter(Pair& pair)

{

??? if (pair.y < 99)

??? ++pair.y;

??? else

??? {

??? if (pair.x < 99)

??? {

??? ??? ++pair.x;

??? ??? pair.y = 0;

??? }

??? else

??? ??? return false;

??? }

??? return true;

}

?

??? counter 的作用是試圖將pair.y增1，但如果pair.y已經(jīng)到達上限99，則將pair.x加1，同時pair.y置0繼續(xù)下一輪；但如果pair.x也到 了99，那么，噢，說明遍歷結(jié)束了。——嗯，這樣的確是一種有效的遍歷方式，對吧。它實際上類似于下面的二重循環(huán)：

?

??? for (; pair.x <= 99; ++pair.x)

??????? for (pair.y = 0; pair.y <= 99; ++pair.y)

???????????? ...

?

??? 只不過循環(huán)要求在循環(huán)體內(nèi)解決一切問題，而我們“解決一切問題”的重任擔在了另一個函數(shù)里，counter不能越權(quán)，因而不能這樣直接使用循環(huán)。

??? 接下來是判斷是否為有效狀態(tài)的函數(shù)，它最簡單了：

?

bool match(const Pair& pair)

{

??? return (pair.x + pair.y) == 50;

}

?

??? 萬事俱備，可以寫main:

?

int main()

{

??? WalkThrough<Pair> sf50(Pair(0, -1), &counter, &match);

??? while (sf50.getNextFilter())

??? cout << sf50.getState().x << " + "

??? ???? << sf50.getState().y << " = 50" << endl;

??? return 0;

}

?

??? 請 一定要注意，getNextFilter()中有一個"Next"，也就是說，如果把狀態(tài)全集中的第一個狀態(tài)作為構(gòu)造的參數(shù)，——本題中就是Pair (0, 0)——是可行狀態(tài)的話，getNextFilter()將不會判斷到，它直接判斷“下一個”狀態(tài)，就是Pair(0, 1)去了。為了讓它能夠完整地判斷，我們不能讓Pair(0, 0)作為第一個狀態(tài)，而是作為首次運行g(shù)etNextFilter()后到達的狀態(tài)。于是，在構(gòu)造初始狀態(tài)時我們就要用“前”一個狀態(tài)Pair(0, -1)作為構(gòu)造參數(shù)（雖然它根本不在本題的狀態(tài)全集中），以使得getNextFilter()從Pair(0, 0)開始判斷。

??? 嗯， 好，在運行之前不要忘了#include <iostream>，不要忘了打開std名字空間（using namespace std;），不要忘了粘上/包含上前面的WalkThrough的完整定義……編譯，運行，好，這個超級難題被我們解決了。我的編譯平臺是Redhat Linux 9， GNU C++ 3.2.2.

??? 最 后我們分析小結(jié)一下經(jīng)過封裝之后的窮舉算法。首先看效率——是啦，我知道這個“和是50”超級難題所用的算法很糟糕——我是指在相同算法的前提下，使用我 們封裝好的窮舉類進行實現(xiàn)時的效率損失：初始化以及一系列set/get函數(shù)基本不影響效率，主開銷源自于getNextFilter()本身的調(diào)用及 getNextFilter對兩個用戶提供函數(shù)的調(diào)用所產(chǎn)生的額外開銷。試想如果用相同的算法，但僅用兩層for來做窮舉，則少了上萬次的函數(shù)入棧、清棧 操作。窮舉法本身就不是一個高效的搜索思想，所以對內(nèi)層代碼的效率變化是最敏感的，這一點是我們所封裝的窮舉類的最大缺點。

??? 不 過總算還是有一點好處，比如，封裝之后，就將設計窮舉算法分解成了相對獨立的設計狀態(tài)類、狀態(tài)跳轉(zhuǎn)函數(shù)、狀態(tài)判斷函數(shù)三個部分，三者的耦合度相對降低。此 外，這個設計的過程多少讓我們又多了解了一點點基于對象編程的抽象能力，嗯，等等。噢……或許這是一個學術(shù)價值大于實用價值的設計吧，呵呵。