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

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

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

　　(1) 狀態全集：一堆蘋果

　　(2) 可行狀態：藍色的蘋果

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

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

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

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

　　下一步，我們就可以考慮“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)

　　這個構造函數不指定任何初始條件，包括當前狀態?？梢栽谛枰臅r候使用一系列的set成員函數定義。

　　接下來定義一個“全功能”的構造函數：

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

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

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

　　對于拷貝構造函數，由于我們這里沒有涉及內存分配，沒有“深拷貝”的需求，因此不作定義，使用默認的位拷貝可以有不錯的效率。類似地，析構函數也沒有什么事務需要處理，不過考慮到這個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

　　return true;熱門推薦： 如何迅速成為Java高手

本新聞共2頁,當前在第1頁  1  2  

原文轉自：http://www.anti-gravitydesign.com