朋友，這篇筆記看起來怎么樣呢？
前言：這是我 3月22日 寫的線性求解器 gecode 的筆記。我喜歡 gecode 的文檔，也很喜歡它簡潔流暢的 C++ 源碼。計(jì)劃趕不上變化快，當(dāng)時(shí)興致勃勃的我，真的想不到，3月22日是我這五個(gè)月來最后一次寫這么工整的筆記;之后我便陷入一場極大的拉鋸戰(zhàn)中——無暇再打開這個(gè)筆記(甚至都給忘了，這幾天整理資料才想起)，但拉鋸戰(zhàn)最終收獲甚少;當(dāng)時(shí)的我更想不到，現(xiàn)在提起「線性優(yōu)化」這個(gè)課題，我的第一反應(yīng)是拒絕。我很喜歡這個(gè)筆記，稍微閱讀我便可以把當(dāng)時(shí)總結(jié)的重點(diǎn)全部回顧起來。這幾個(gè)月來的教訓(xùn)是：不要認(rèn)為自己可以什么都學(xué)、什么都涉獵，趕快定好一個(gè)細(xì)分方向，努力下去吧。接下來的很長一段時(shí)間，我可能都沒空更新這個(gè)筆記了。我當(dāng)時(shí)的期望「gecode 是很優(yōu)秀的線性求解器，但中文互聯(lián)網(wǎng)幾乎沒有其系統(tǒng)性教輔資料，我用研一下學(xué)期來寫一套」近期也不可能實(shí)現(xiàn)了。共勉。我會(huì)回來看你的，老伙計(jì)。
Gecode基礎(chǔ)知識(shí)
- Gecode基礎(chǔ)知識(shí)[1]
- SendMoreMoney[3]
- 必須注意的點(diǎn)[4]
- rel - 關(guān)系約束[5]
- distinct - 兩兩不同約束[6]
- branch - 定義分支規(guī)則[7]
- 關(guān)于 print[8]
- 以SendMoreMoney為例[2]
- 搜索引擎的使用[9]
- 異常處理[10]
- Gist - 可視化求解過程[11]
- 設(shè)定目標(biāo)值[12]
- 筆記地址[13]
以SendMoreMoney為例
SendMoreMoney
我們給這八個(gè)字母賦值(賦一個(gè)數(shù)字)：S E N D M O R Y
使得等式成立：SEND + MORE = MONEY ，其中每個(gè)字母是不同的數(shù)字。
還不明白?告訴你答案，我們最后要把 SEND + MORE = MONEY 替換為 9567 + 1085 = 10652 。這就是求解成功了，其中 S 是 9 、 E 是 5 ...
必須注意的點(diǎn)
代碼在：https://gitee.com/piperliu/math_codes_economics_management/tree/master/gecode_MPG_notes/codes/03sendmoremoney/sendmoremoney.cpp[14]
- // 使用整數(shù)變量和整數(shù)約束
- // 我們需要 include gecode/int.hh 頭文件
- #include <gecode/int.hh>
- // 使用搜索引擎（求解邏輯），我們需要 gecode/search.hh 頭文件
- #include <gecode/search.hh>
- // 所有的 gecode 功能都在命名空間 Gecode 里
- // 所以，避免 Gecode::IntVarArray 這樣的麻煩
- // 我們 using namespace Gecode; 來簡化代碼
- using namespace Gecode;
- // 所有的模型都要繼承 Gecode::Space
- class SendMoreMoney : public Space {
- protected:
- // 這里聲明了一個(gè)整數(shù)變量數(shù)組 l
- IntVarArray l;
- public:
- // 在構(gòu)造函數(shù)里聲明模型
- // l(*this, 8, 0, 9) 表示：
- // - 變量數(shù)組 l 是這個(gè)模型的（this）
- // - 變量數(shù)組 l 包含 8 個(gè)變量
- // - 這些變量的取值范圍是 [0, 9]
- SendMoreMoney(void) : l(*this, 8, 0, 9) {
- // 我們聲明了一些變量
- IntVar s(l[0]), e(l[1]), n(l[2]), d(l[3]),
- m(l[4]), o(l[5]), r(l[6]), y(l[7]);
- // 下面是一些約束的實(shí)現(xiàn)，先不用管具體含義
- // no leading zeros
- rel(*this, s, IRT_NQ, 0);
- rel(*this, m, IRT_NQ, 0);
- // all letters distinct
- distinct(*this, l);
- // linear equation
- // 這里是一些 Args 變量
- // 我把 Var 理解為決策變量，或者自變量
- // 而 Args 是根據(jù) Var 變動(dòng)的，中介變量
- // 本身并不主動(dòng)變化，受 Var 們變動(dòng)影響
- IntArgs c(4+4+5); IntVarArgs x(4+4+5);
- c[0]=1000; c[1]=100; c[2]=10; c[3]=1;
- x[0]=s; x[1]=e; x[2]=n; x[3]=d;
- c[4]=1000; c[5]=100; c[6]=10; c[7]=1;
- x[4]=m; x[5]=o; x[6]=r; x[7]=e;
- c[8]=-10000; c[9]=-1000; c[10]=-100; c[11]=-10; c[12]=-1;
- x[8]=m; x[9]=o; x[10]=n; x[11]=e; x[12]=y;
- linear(*this, c, x, IRT_EQ, 0);
- // 定義了分支定界的規(guī)則
- // post branching
- branch(*this, l, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
- }
- // 必須聲明一個(gè) copy constructor
- // 其中一定一定要有對(duì)于變量的更新
- // search support
- SendMoreMoney(SendMoreMoney& s) : Space(s) {
- l.update(*this, s.l);
- }
- // 以及聲明一個(gè) copy 方法（用于search）
- virtual Space* copy(void) {
- return new SendMoreMoney(*this);
- }
- // print solution
- void print(void) const {
- std::cout << l << std::endl;
- }
- };
- // main function
- int main(int argc, char* argv[]) {
- // create model and search engine
- SendMoreMoney* m = new SendMoreMoney;
- DFS<SendMoreMoney> e(m);
- delete m;
- // search and print all solutions
- while (SendMoreMoney* s = e.next()) {
- s->print(); delete s;
- }
- return 0;
- }
如上，我們實(shí)現(xiàn)了一個(gè)問題，我在中文注釋中做出了解釋。值得注意的有：
- 所有的 gecode 功能都在命名空間 Gecode 里
- 所有的模型都要繼承 Gecode::Space
- 除了基本的構(gòu)造函數(shù)，必須聲明一個(gè) copy constructor 、以及聲明一個(gè) copy 方法(用于search)
- 我們必須在 copy constructor 對(duì)決策變量進(jìn)行更新(比如 l.update(*this, s.l);)，這尤為重要，否則程序不會(huì)報(bào)錯(cuò)，而求解過程是錯(cuò)誤的。原因在于，我們的求解器在求解過程中，會(huì)不斷賦值 Space 實(shí)例，如果不在 copy constructor 中更新決策變量，則無法進(jìn)行回溯、保存等操作
我把 Var 理解為決策變量，或者自變量;而 Args 是根據(jù) Var 變動(dòng)的，中介變量，本身并不主動(dòng)變化，受 Var 們變動(dòng)影響。
注意到無論是變量還是約束，其聲明時(shí)，第一個(gè)參數(shù)都 *this 。你可以如此理解：變量如小孩子，小孩子出生，必須明確 ta 的監(jiān)護(hù)人是誰，否則，接下來小孩子沒有依靠，這個(gè)小孩子也就活不下去。在這里，我們的變量和約束都依靠其存在的問題中，即類 SendMoreMoney 。
rel - 關(guān)系約束
- rel(*this, s, IRT_NQ, 0);
上述語句表示：變量 s 不等于 0，其中：
- IRT_NQ 表示不等于，我們將在后文見到所有的邏輯符號(hào)表達(dá)
- rel 是 relation 的意思
distinct - 兩兩不同約束
- distinct(*this, l);
我們這里不具體闡述 distinct 的用法，只說明其作用：
- l 數(shù)組中變量要兩兩不同(pairwise different)
其他約束不再詳述，以后會(huì)提到。
branch - 定義分支規(guī)則
在求解過程中，不同的搜索方式對(duì)于求解效果有著天差地別的影響。因此定義合適的 branch 分支規(guī)則尤為重要。
- branch(*this, l, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
這里表示，對(duì)于變量數(shù)組 l 中的變量，我們首先選擇對(duì)其中搜索范圍最小的變量進(jìn)行搜索(INT_VAR_SIZE_MIN())，此外如果選擇了一個(gè)變量，我們將現(xiàn)有的最小值賦給它(INT_VAL_MIN())。
其他規(guī)則以及關(guān)于 branch 的用法將在后文討論。
關(guān)于 print
在求解后， gecode 會(huì)自動(dòng)調(diào)用 print 輸出。我們可以自由發(fā)揮，重載 print 函數(shù)，讓解是我想要的形式。
- // print solution
- void print(void) const {
- std::cout << l << std::endl;
- }
求解后的效果：
- {9, 5, 6, 7, 1, 0, 8, 2}
表示 S 是 9 、 E 是 5 ...
搜索引擎的使用
我們?cè)谏厦娑x了我們的問題(包含變量與約束)，我們?cè)诔绦蛑蟹Q之為一個(gè)“模型model”。
這個(gè)模型對(duì)象中存儲(chǔ)了當(dāng)前變量的范圍，我將其理解為搜索中的一些節(jié)點(diǎn)的集合(在一些運(yùn)算后產(chǎn)生的更小的、更精準(zhǔn)的解空間)。
那么如何實(shí)現(xiàn)一顆搜索樹呢?在 main 方法中，我們將其實(shí)現(xiàn)。
- // main function
- int main(int argc, char* argv[]) {
- // create model and search engine
- SendMoreMoney* m = new SendMoreMoney;
- // 第一個(gè) print()
- std::cout << "1" << std::endl;
- m->print();
- m->status();
- // 第二個(gè) print()
- std::cout << "2" << std::endl;
- m->print();
- DFS<SendMoreMoney> e(m);
- // 第三個(gè) print()
- std::cout << "3" << std::endl;
- m->print();
- delete m;
- // search and print all solutions
- while (SendMoreMoney* s = e.next()) {
- // 第四個(gè) print()
- std::cout << "4" << std::endl;
- s->print(); delete s;
- }
- return 0;
- }
你可以看到，我在上面安插了 4 個(gè) print，來看看當(dāng)前我們搜索到的范圍。輸入如下。
- 1
- {[1..9], [0..9], [0..9], [0..9], [1..9], [0..9], [0..9], [0..9]}
- 2
- {9, [4..7], [5..8], [2..8], 1, 0, [2..8], [2..8]}
- 3
- {9, [4..7], [5..8], [2..8], 1, 0, [2..8], [2..8]}
- 4
- {9, 5, 6, 7, 1, 0, 8, 2}
當(dāng)我們聲明這個(gè)問題時(shí)(初始化模型)，我們的模型根據(jù)約束做了一些最基本的運(yùn)算，在這里體現(xiàn)為：
- S的范圍應(yīng)該是[1, 9]
- M的范圍應(yīng)該是[1, 9]
這很好理解，因?yàn)槲覀冇屑s束 rel(*this, s, IRT_NQ, 0);， rel(*this, m, IRT_NQ, 0); 。
只有當(dāng)我們調(diào)用 status() 后，約束傳播constraint propagation才會(huì)起作用。
status函數(shù)的注釋原文為 Query space status Propagates the space until fixpoint or failure; updates the statistics information stat; and:
- if the space is failed, SpaceStatus::SS_FAILED is returned.
- if the space is not failed but the space has no brancher left, SpaceStatus::SS_SOLVED is returned.
- otherwise, SpaceStatus::SS_BRANCH is returned.
我的理解是，對(duì)現(xiàn)有的解空間做一次最基本的探索，直到需要 branch 做決策的點(diǎn)或者探索失敗。
值得注意的是，如果我們?nèi)∠鲜?m->status(); 這句話，那么 3 對(duì)應(yīng)的 print() 依然是 {9, [4..7], [5..8], [2..8], 1, 0, [2..8], [2..8]} 。這說明為我們的模型聲明搜索引擎時(shí)，會(huì)調(diào)用一次 status() 。
如下，在 while 中，我們希望返回每一次探索的解。值得注意的是，解也是一個(gè)模型(問題實(shí)例)。
- while (SendMoreMoney* s = e.next()) {
- // 第四個(gè) print()
- std::cout << "4" << std::endl;
- s->print(); delete s;
- }
在這里，e是基于DFS深度優(yōu)先搜索的搜索引擎，e.next()則是基于DFS規(guī)則做出的下一個(gè)探索方向的探索結(jié)果。如果探索到頭了，那么e.next()會(huì)返回NULL，此時(shí) while 停止，跳出循環(huán)。
異常處理
實(shí)際上，為了捕捉 Gecode 的異常，使用 try {} catch () {} 是一個(gè)很好的選擇。
- int main(int argc, char* argv[]) {
- try {
- // main 中的內(nèi)容
- } catch (Exception e) {
- std::cerr << "Gecode exception: " << e.what() << std::endl;
- return 1;
- }
- return 0;
- }
注意，這里的 Exception 是 Gecode 命名空間中的異常Gecode::Exception。
不管是本筆記還是教程文件MPG，都沒有使用 try catch (為了易讀性)，但是在時(shí)間使用中，還是應(yīng)該具有如此的良好習(xí)慣。
Gist - 可視化求解過程
程序見https://gitee.com/piperliu/math_codes_economics_management/tree/master/gecode_MPG_notes/codes/03sendmoremoney/sendmoremoneyGist_1.cpp[15]
- #include <gecode/gist.hh>
- using namespace Gecode;
- ...
- int main(int argc, char* argv[]) {
- SendMoreMoney* m = new SendMoreMoney;
- Gist::dfs(m);
- delete m;
- return 0;
- }
我們引入 gist.hh 頭文件，在 main 中較為簡單地可視化 dfs 過程。
可以用鼠標(biāo)探索
關(guān)于 gist 功能，還有其他調(diào)用方法。gist功能較為強(qiáng)大，這里不再贅述。
此外，還可用手動(dòng)增加現(xiàn)實(shí)解的功能，代碼見https://gitee.com/piperliu/math_codes_economics_management/tree/master/gecode_MPG_notes/codes/03sendmoremoney/sendmoremoneyGist_2.cpp[16]
添加了 inspect
設(shè)定目標(biāo)值
設(shè)定目標(biāo)值時(shí)，我們需要聲明 cost 函數(shù)以及用變量表示搜索過程中變量的傳遞(用于目標(biāo)函數(shù)的計(jì)算)。這里不詳細(xì)討論。
這并不復(fù)雜，我們將在之后的筆記中專門討論。
