Google SoC 系列：使用 Ruby 实现约束规划

  • Werner Schuster
  • 高昂

2007 年 6 月 26 日

话题：Ruby语言 & 开发架构

Gecode/R 是一个得到 Google SoC 资助的 Ruby 项目，目的是使得 Ruby 语言的开发者同样可以使用运筹学中的约束规划（Constraint Programming）方法，项目的发起人 Andreas Launila 对于约束规划这样解释道：

约束规划是一种声明式的规划范式（Declarative Programming Paradigm），开发者描述需要何种解决方案，而不是告诉程序如何进行具体的计算。当使用约束规划时，开发者可以试图为问题建立模型，并将模型集中提交给问题处理程序。问题处理程序通过检索问题域中的所有可行解，并利用模型中的约束条件来去除这些解中的部分，而不需要真正去访问到这部分的可能解。

一个常见的例子就是数独游戏（Soduko），通过约束规划解决数独问题的过程是：为问题处理程序填写约束规则（比方说每一行的数字必须是各不相同的），然后寻找令所有约束条件同时满足的解决方案。

当问及现实世界中是否有使用约束规划解决问题的例子时，Andreas 解释道：

约束规划是用于处理 NP 难解组合问题的常用方法，在这种情况下，一般只存在有限的选择，但需要根据特定条件进行搜索。现实世界中的例子包括时序安排，周期分配以及人员工作时间设置等问题。

Gecode/R 实际上是建立在 C++ 约束规划函数库Gecode基础之上的 Ruby 语言封装，关于为何使用 Ruby 语言来实现 Gecode 的功能，Andreas 这样解释道：

对我来说，约束规划是在我常用工具箱中一个非常有用的工具。当使用约束规划来处理恰当的问题类型时，会为我们节省大量的时间和工作。由于可以进行快速编码实现，当更好的算法存在并且运行效率并非是首要考虑的因素（或者性能上的差别比起在研究和实现算法上需要花的额外时间是可以忽略不计）时，约束规划可以用来很快的解决问题。

一个有趣的话题是关于如何使用 Ruby 语言来定义约束规划：

我的目的是为了创建一个前端，而不仅仅是一个绑定。我称之为类库而不仅是一种 DSL（Domain Specific Language，领域特定语言），尽管两者之间的边界并非有十分严格的界定。因为项目即将开始，至今还没有定义精确的语法规则。下面简单的代码段给出项目的大致指导方向，但这不一定是项目最终使用的语法规则。代码段示例解决了“send+more=money”这个经典的问题。

通过这样的途径，比较方法和算术方法被用于表示线性约束，并且通过对数组进行拓展来表达特殊约束来用于分支选择。变量在创建时需要记录，以便于跟踪他们。其中一个不足之处是符号“!=”没有被定义为一个方法，所以使用不等式时的语法与其他语言并不相同。

下面是程序代码编写的样例：

# 经典的 send+more=money 问题。

class SendMoreMoneyProblem < Gecode::Space

  def initialize

    # 设置变量，在 0..9 之间的 8 个字母.

    s,e,n,d,m,o,r,y = letters = IntVar.array(8, 0..9)

    # 设置约束条件.

    constrain equation_row(s, e, n, d) +

                  equation_row(m, o, r, e) ==

                  equation_row(m, o, n, e, y)

    constrain s.not_equal(0) # 并不是写成"s != 0" 因为我们无法重定义符号 != .

    constrain m.not_equal(0)

    letters.all_distinct

    # 选择搜索解决方案时要使用的启发式分支.

    letters.branch_using(:variable => :min_size, :value => :min)

  end
private


  # 使用线性方程有更好的方法。取出变量中的一个数字，

  # 并且计算线性组合就像变量是基于 10 个字符的阿拉伯数字。

  # 例如：x,y,z 成为 100*x + 10*y + z .

  def equation_row(*variables)

    variables.inject(0){ |result, variable| variable + 10*result }

  end

end

# 打印出问题的第一种解决方案

p SendMoreMoneyProblem.new.solutions(:first)

如果想了解更多细节，可以查看维基百科上面“send+more=money”词条相关的文章。

当使用 Ruby 语言定义业务逻辑或者数据时，常有可能使用内部 DSL来编写更加简练并且可读性更强的代码。Andreas 关于代码可能的样式这样解释道：

另一个使得代码看起来更像 DSL 的方法是在编码中跳过类声明之类的。这个方法在快速处理单一样例的问题时更加出色，但是会妨碍与其它 Ruby 代码协同来使用约束规划。

下面是使用 DSL 方法的代码样例：

find_first_solution_to define_problem do |p|

  # 设置变量，在 0..9 之间的 8 个字母。

  s,e,n,d,m,o,r,y = letters = p.create_int_vars(8, 0..9)

  # 设置约束。

  p.add 1000*s + 100*e + 10*n + d +

           1000*m + 100*o + 10*r + e ==

           10000*m + 1000*o + 100*n + 10*e + y

  p.add s.not_equal(0)

  p.add m.not_equal(0)

  p.add all_distinct(letters)

  # 选择启发式分支。

  p.branch_on letters, :variable => :min_size, :value => :min

end

由于 Gecode/R 是在本地类库基础之上的绑定实现，这样就存在一个潜在的瓶颈问题。Andreas 非常自信的认为这不会是一个影响项目发展的问题：

在 Gecode 中已经实现了通用约束的传播机制，所以这些约束的实际传播过程已在此处完成。如果用户设置自定义的传播机制，则需要在 C 语言和 Ruby 语言之间进行来回切换，目前我还不清楚这样是否存在性能问题。但 Gecod 的设计可以使其能很好地与外界进行交互，并且可以很好的与 Java 语言协同工作，所以如果有人说 Gecode/R 在本地类库上实现绑定将会成为瓶颈，我肯定会对此表示惊讶。

Gecode/R 是建立在 RubyForge 上的开放源代码项目，这同时也是吸引对此感兴趣开发者加入的优秀站点。约束规范相关的 API 接口和语法的可以在链接中的 Wiki 页面深入了解。Andreas 同时也维护着建立在 O'Reilly Ruby 站点上的 Gecode/R 项目相关博客。

查看英文原文：Google SoC Series: Constraint programming with Ruby

Ruby语言 & 开发架构