朋友，这篇笔记看起来怎么样呢？

前言：这是我 3月22日 写的线性求解器 gecode 的笔记。我喜欢 gecode 的文档，也很喜欢它简洁流畅的 C++ 源码。计划赶不上变化快，当时兴致勃勃的我，真的想不到，3月22日是我这五个月来最后一次写这么工整的笔记;之后我便陷入一场极大的拉锯战中——无暇再打开这个笔记(甚至都给忘了，这几天整理资料才想起)，但拉锯战最终收获甚少;当时的我更想不到，现在提起「线性优化」这个课题，我的第一反应是拒绝。我很喜欢这个笔记，稍微阅读我便可以把当时总结的重点全部回顾起来。这几个月来的教训是：不要认为自己可以什么都学、什么都涉猎，赶快定好一个细分方向，努力下去吧。接下来的很长一段时间，我可能都没空更新这个笔记了。我当时的期望「gecode 是很优秀的线性求解器，但中文互联网几乎没有其系统性教辅资料，我用研一下学期来写一套」近期也不可能实现了。共勉。我会回来看你的，老伙计。

网站制作、成都网站建设的开发，更需要了解用户，从用户角度来建设网站，获得较好的用户体验。创新互联公司多年互联网经验，见的多，沟通容易、能帮助客户提出的运营建议。作为成都一家网络公司，打造的就是网站建设产品直销的概念。选择创新互联公司，不只是建站，我们把建站作为产品，不断的更新、完善，让每位来访用户感受到浩方产品的价值服务。

Gecode基础知识

  • Gecode基础知识[1]
    • SendMoreMoney[3]
    • 必须注意的点[4]
    • rel - 关系约束[5]
    • distinct - 两两不同约束[6]
    • branch - 定义分支规则[7]
    • 关于 print[8]
    • 以SendMoreMoney为例[2]
    • 搜索引擎的使用[9]
    • 异常处理[10]
    • Gist - 可视化求解过程[11]
    • 设定目标值[12]
  • 笔记地址[13]

以SendMoreMoney为例

SendMoreMoney

我们给这八个字母赋值(赋一个数字)：S E N D M O R Y

使得等式成立：SEND + MORE = MONEY ，其中每个字母是不同的数字。

还不明白?告诉你答案，我们最后要把 SEND + MORE = MONEY 替换为 9567 + 1085 = 10652 。这就是求解成功了，其中 S 是 9 、 E 是 5 ...

必须注意的点

代码在：https://gitee.com/piperliu/math_codes_economics_management/tree/master/gecode_MPG_notes/codes/03sendmoremoney/sendmoremoney.cpp[14]

 
 
 
 
    
  
  
  
  
  1. // 使用整数变量和整数约束 
    2. 
  
  
  
  
  2. // 我们需要 include gecode/int.hh 头文件 
    3. 
  
  
  
  
  3. #include  
    4. 
  
  
  
  
  4. // 使用搜索引擎（求解逻辑），我们需要 gecode/search.hh 头文件  
    5. 
  
  
  
  
  5. #include  
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. // 所有的 gecode 功能都在命名空间 Gecode 里 
    8. 
  
  
  
  
  8. // 所以，避免 Gecode::IntVarArray 这样的麻烦 
    9. 
  
  
  
  
  9. // 我们 using namespace Gecode; 来简化代码 
    10. 
  
  
  
  
  10. using namespace Gecode; 
    11. 
  
  
  
  
  11.  
    12. 
  
  
  
  
  12. // 所有的模型都要继承 Gecode::Space 
    13. 
  
  
  
  
  13. class SendMoreMoney : public Space { 
    14. 
  
  
  
  
  14. protected: 
    15. 
  
  
  
  
  15.   // 这里声明了一个整数变量数组 l 
    16. 
  
  
  
  
  16.   IntVarArray l; 
    17. 
  
  
  
  
  17. public: 
    18. 
  
  
  
  
  18.   // 在构造函数里声明模型 
    19. 
  
  
  
  
  19.   // l(*this, 8, 0, 9) 表示： 
    20. 
  
  
  
  
  20.   //   - 变量数组 l 是这个模型的（this） 
    21. 
  
  
  
  
  21.   //   - 变量数组 l 包含 8 个变量 
    22. 
  
  
  
  
  22.   //   - 这些变量的取值范围是 [0, 9] 
    23. 
  
  
  
  
  23.   SendMoreMoney(void) : l(*this, 8, 0, 9) { 
    24. 
  
  
  
  
  24.     // 我们声明了一些变量 
    25. 
  
  
  
  
  25.     IntVar s(l[0]), e(l[1]), n(l[2]), d(l[3]), 
    26. 
  
  
  
  
  26.            m(l[4]), o(l[5]), r(l[6]), y(l[7]); 
    27. 
  
  
  
  
  27.     // 下面是一些约束的实现，先不用管具体含义 
    28. 
  
  
  
  
  28.     // no leading zeros 
    29. 
  
  
  
  
  29.     rel(*this, s, IRT_NQ, 0); 
    30. 
  
  
  
  
  30.     rel(*this, m, IRT_NQ, 0); 
    31. 
  
  
  
  
  31.     // all letters distinct 
    32. 
  
  
  
  
  32.     distinct(*this, l); 
    33. 
  
  
  
  
  33.     // linear equation 
    34. 
  
  
  
  
  34.     // 这里是一些 Args 变量 
    35. 
  
  
  
  
  35.     // 我把 Var 理解为决策变量，或者自变量 
    36. 
  
  
  
  
  36.     // 而 Args 是根据 Var 变动的，中介变量 
    37. 
  
  
  
  
  37.     // 本身并不主动变化，受 Var 们变动影响 
    38. 
  
  
  
  
  38.     IntArgs c(4+4+5); IntVarArgs x(4+4+5); 
    39. 
  
  
  
  
  39.     c[0]=1000; c[1]=100; c[2]=10; c[3]=1; 
    40. 
  
  
  
  
  40.     x[0]=s;    x[1]=e;   x[2]=n;  x[3]=d; 
    41. 
  
  
  
  
  41.     c[4]=1000; c[5]=100; c[6]=10; c[7]=1; 
    42. 
  
  
  
  
  42.     x[4]=m;    x[5]=o;   x[6]=r;  x[7]=e; 
    43. 
  
  
  
  
  43.     c[8]=-10000; c[9]=-1000; c[10]=-100; c[11]=-10; c[12]=-1; 
    44. 
  
  
  
  
  44.     x[8]=m;      x[9]=o;     x[10]=n;    x[11]=e;   x[12]=y; 
    45. 
  
  
  
  
  45.     linear(*this, c, x, IRT_EQ, 0); 
    46. 
  
  
  
  
  46.     // 定义了分支定界的规则 
    47. 
  
  
  
  
  47.     // post branching 
    48. 
  
  
  
  
  48.     branch(*this, l, INT_VAR_SIZE_MIN(), INT_VAL_MIN()); 
    49. 
  
  
  
  
  49.   } 
    50. 
  
  
  
  
  50.   // 必须声明一个 copy constructor 
    51. 
  
  
  
  
  51.   // 其中一定一定要有对于变量的更新 
    52. 
  
  
  
  
  52.   // search support 
    53. 
  
  
  
  
  53.   SendMoreMoney(SendMoreMoney& s) : Space(s) { 
    54. 
  
  
  
  
  54.     l.update(*this, s.l); 
    55. 
  
  
  
  
  55.   } 
    56. 
  
  
  
  
  56.   // 以及声明一个 copy 方法（用于search） 
    57. 
  
  
  
  
  57.   virtual Space* copy(void) { 
    58. 
  
  
  
  
  58.     return new SendMoreMoney(*this); 
    59. 
  
  
  
  
  59.   } 
    60. 
  
  
  
  
  60.   // print solution 
    61. 
  
  
  
  
  61.   void print(void) const { 
    62. 
  
  
  
  
  62.     std::cout << l << std::endl; 
    63. 
  
  
  
  
  63.   } 
    64. 
  
  
  
  
  64. }; 
    65. 
  
  
  
  
  65.  
    66. 
  
  
  
  
  66. // main function 
    67. 
  
  
  
  
  67. int main(int argc, char* argv[]) { 
    68. 
  
  
  
  
  68.   // create model and search engine 
    69. 
  
  
  
  
  69.   SendMoreMoney* m = new SendMoreMoney; 
    70. 
  
  
  
  
  70.   DFS e(m); 
    71. 
  
  
  
  
  71.   delete m; 
    72. 
  
  
  
  
  72.   // search and print all solutions 
    73. 
  
  
  
  
  73.   while (SendMoreMoney* s = e.next()) { 
    74. 
  
  
  
  
  74.     s->print(); delete s; 
    75. 
  
  
  
  
  75.   } 
    76. 
  
  
  
  
  76.   return 0; 
    77. 
  
  
  
  
  77. } 
    78.

如上，我们实现了一个问题，我在中文注释中做出了解释。值得注意的有：

  • 所有的 gecode 功能都在命名空间 Gecode 里
  • 所有的模型都要继承 Gecode::Space
  • 除了基本的构造函数，必须声明一个 copy constructor 、以及声明一个 copy 方法(用于search)
  • 我们必须在 copy constructor 对决策变量进行更新(比如 l.update(*this, s.l);)，这尤为重要，否则程序不会报错，而求解过程是错误的。原因在于，我们的求解器在求解过程中，会不断赋值 Space 实例，如果不在 copy constructor 中更新决策变量，则无法进行回溯、保存等操作

我把 Var 理解为决策变量，或者自变量;而 Args 是根据 Var 变动的，中介变量，本身并不主动变化，受 Var 们变动影响。

注意到无论是变量还是约束，其声明时，第一个参数都 *this 。你可以如此理解：变量如小孩子，小孩子出生，必须明确 ta 的监护人是谁，否则，接下来小孩子没有依靠，这个小孩子也就活不下去。在这里，我们的变量和约束都依靠其存在的问题中，即类 SendMoreMoney 。

rel - 关系约束

 
 
 
 
    
  
  
  
  
  1. rel(*this, s, IRT_NQ, 0); 
    2.

上述语句表示：变量 s 不等于 0，其中：

  • IRT_NQ 表示不等于，我们将在后文见到所有的逻辑符号表达
  • rel 是 relation 的意思

distinct - 两两不同约束

 
 
 
 
    
  
  
  
  
  1. distinct(*this, l); 
    2.

我们这里不具体阐述 distinct 的用法，只说明其作用：

  • l 数组中变量要两两不同(pairwise different)

其他约束不再详述，以后会提到。

branch - 定义分支规则

在求解过程中，不同的搜索方式对于求解效果有着天差地别的影响。因此定义合适的 branch 分支规则尤为重要。

 
 
 
 
    
  
  
  
  
  1. branch(*this, l, INT_VAR_SIZE_MIN(), INT_VAL_MIN()); 
    2.

这里表示，对于变量数组 l 中的变量，我们首先选择对其中搜索范围最小的变量进行搜索(INT_VAR_SIZE_MIN())，此外如果选择了一个变量，我们将现有的最小值赋给它(INT_VAL_MIN())。

其他规则以及关于 branch 的用法将在后文讨论。

关于 print

在求解后， gecode 会自动调用 print 输出。我们可以自由发挥，重载 print 函数，让解是我想要的形式。

 
 
 
 
    
  
  
  
  
  1. // print solution 
    2. 
  
  
  
  
  2. void print(void) const { 
    3. 
  
  
  
  
  3. std::cout << l << std::endl; 
    4. 
  
  
  
  
  4. } 
    5.

求解后的效果：

 
 
 
 
    
  
  
  
  
  1. {9, 5, 6, 7, 1, 0, 8, 2} 
    2.

表示 S 是 9 、 E 是 5 ...

搜索引擎的使用

我们在上面定义了我们的问题(包含变量与约束)，我们在程序中称之为一个“模型model”。

这个模型对象中存储了当前变量的范围，我将其理解为搜索中的一些节点的集合(在一些运算后产生的更小的、更精准的解空间)。

那么如何实现一颗搜索树呢?在 main 方法中，我们将其实现。

 
 
 
 
    
  
  
  
  
  1. // main function 
    2. 
  
  
  
  
  2. int main(int argc, char* argv[]) { 
    3. 
  
  
  
  
  3.   // create model and search engine 
    4. 
  
  
  
  
  4.   SendMoreMoney* m = new SendMoreMoney; 
    5. 
  
  
  
  
  5.   // 第一个 print() 
    6. 
  
  
  
  
  6.   std::cout << "1" << std::endl; 
    7. 
  
  
  
  
  7.   m->print(); 
    8. 
  
  
  
  
  8.   m->status(); 
    9. 
  
  
  
  
  9.   // 第二个 print() 
    10. 
  
  
  
  
  10.   std::cout << "2" << std::endl; 
    11. 
  
  
  
  
  11.   m->print(); 
    12. 
  
  
  
  
  12.   DFS e(m); 
    13. 
  
  
  
  
  13.   // 第三个 print() 
    14. 
  
  
  
  
  14.   std::cout << "3" << std::endl; 
    15. 
  
  
  
  
  15.   m->print(); 
    16. 
  
  
  
  
  16.   delete m; 
    17. 
  
  
  
  
  17.   // search and print all solutions 
    18. 
  
  
  
  
  18.   while (SendMoreMoney* s = e.next()) { 
    19. 
  
  
  
  
  19.     // 第四个 print() 
    20. 
  
  
  
  
  20.     std::cout << "4" << std::endl; 
    21. 
  
  
  
  
  21.     s->print(); delete s; 
    22. 
  
  
  
  
  22.   } 
    23. 
  
  
  
  
  23.   return 0; 
    24. 
  
  
  
  
  24. } 
    25.

你可以看到，我在上面安插了 4 个 print，来看看当前我们搜索到的范围。输入如下。

 
 
 
 
    
  
  
  
  
  1. 1 
    2. 
  
  
  
  
  2. {[1..9], [0..9], [0..9], [0..9], [1..9], [0..9], [0..9], [0..9]} 
    3. 
  
  
  
  
  3. 2 
    4. 
  
  
  
  
  4. {9, [4..7], [5..8], [2..8], 1, 0, [2..8], [2..8]} 
    5. 
  
  
  
  
  5. 3 
    6. 
  
  
  
  
  6. {9, [4..7], [5..8], [2..8], 1, 0, [2..8], [2..8]} 
    7. 
  
  
  
  
  7. 4 
    8. 
  
  
  
  
  8. {9, 5, 6, 7, 1, 0, 8, 2} 
    9.

当我们声明这个问题时(初始化模型)，我们的模型根据约束做了一些最基本的运算，在这里体现为：

  • S的范围应该是[1, 9]
  • M的范围应该是[1, 9]

这很好理解，因为我们有约束 rel(*this, s, IRT_NQ, 0);， rel(*this, m, IRT_NQ, 0); 。

只有当我们调用 status() 后，约束传播constraint propagation才会起作用。

status函数的注释原文为 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.

我的理解是，对现有的解空间做一次最基本的探索，直到需要 branch 做决策的点或者探索失败。

值得注意的是，如果我们取消上述 m->status(); 这句话，那么 3 对应的 print() 依然是 {9, [4..7], [5..8], [2..8], 1, 0, [2..8], [2..8]} 。这说明为我们的模型声明搜索引擎时，会调用一次 status() 。

如下，在 while 中，我们希望返回每一次探索的解。值得注意的是，解也是一个模型(问题实例)。

 
 
 
 
    
  
  
  
  
  1. while (SendMoreMoney* s = e.next()) { 
    2. 
  
  
  
  
  2.     // 第四个 print() 
    3. 
  
  
  
  
  3.     std::cout << "4" << std::endl; 
    4. 
  
  
  
  
  4.     s->print(); delete s; 
    5. 
  
  
  
  
  5.   } 
    6.

在这里，e是基于DFS深度优先搜索的搜索引擎，e.next()则是基于DFS规则做出的下一个探索方向的探索结果。如果探索到头了，那么e.next()会返回NULL，此时 while 停止，跳出循环。

异常处理

实际上，为了捕捉 Gecode 的异常，使用 try {} catch () {} 是一个很好的选择。

 
 
 
 
    
  
  
  
  
  1. int main(int argc, char* argv[]) { 
    2. 
  
  
  
  
  2.   try { 
    3. 
  
  
  
  
  3.     // main 中的内容 
    4. 
  
  
  
  
  4.   } catch (Exception e) { 
    5. 
  
  
  
  
  5.     std::cerr << "Gecode exception: " << e.what() << std::endl; 
    6. 
  
  
  
  
  6.     return 1; 
    7. 
  
  
  
  
  7.   } 
    8. 
  
  
  
  
  8.   return 0; 
    9. 
  
  
  
  
  9. } 
    10.

注意，这里的 Exception 是 Gecode 命名空间中的异常Gecode::Exception。

不管是本笔记还是教程文件MPG，都没有使用 try catch (为了易读性)，但是在时间使用中，还是应该具有如此的良好习惯。

Gist - 可视化求解过程

程序见https://gitee.com/piperliu/math_codes_economics_management/tree/master/gecode_MPG_notes/codes/03sendmoremoney/sendmoremoneyGist_1.cpp[15]

 
 
 
 
    
  
  
  
  
  1. #include  
    2. 
  
  
  
  
  2. using namespace Gecode; 
    3. 
  
  
  
  
  3. ... 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. int main(int argc, char* argv[]) { 
    6. 
  
  
  
  
  6.   SendMoreMoney* m = new SendMoreMoney; 
    7. 
  
  
  
  
  7.   Gist::dfs(m); 
    8. 
  
  
  
  
  8.   delete m; 
    9. 
  
  
  
  
  9.   return 0; 
    10. 
  
  
  
  
  10. } 
    11.

我们引入 gist.hh 头文件，在 main 中较为简单地可视化 dfs 过程。

可以用鼠标探索

关于 gist 功能，还有其他调用方法。gist功能较为强大，这里不再赘述。

此外，还可用手动增加现实解的功能，代码见https://gitee.com/piperliu/math_codes_economics_management/tree/master/gecode_MPG_notes/codes/03sendmoremoney/sendmoremoneyGist_2.cpp[16]

添加了 inspect

设定目标值

设定目标值时，我们需要声明 cost 函数以及用变量表示搜索过程中变量的传递(用于目标函数的计算)。这里不详细讨论。 

这并不复杂，我们将在之后的笔记中专门讨论。

本文名称：朋友，这篇笔记看起来怎么样呢？
本文来源：http://www.36103.cn/qtweb/news23/18373.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

云服务器知识

各行业网站

贵州义龙电信机房　　 　眉山网站建设　　 　产品包装设计　　 　IOS开发　　 　合江网站建设　　 　成都保温材料　　 　成都小程序商城　　 　云虚拟主机　　 　品牌网站定制　　 　乐山托管服务器　　 　美美搬家　　 　成都网站建设　　 　商城网站建设　　 　网站建设公司　　 　宜宾网站营销推广　　 　成都微商城　　 　鸿艺文化　　 　背发光字　　 　广安网站建设　　 　网站建设开发