写点什么

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

  • 2007-06-26
  • 本文字数:2383 字

    阅读完需:约 8 分钟

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 问题。<br></br>class SendMoreMoneyProblem < Gecode::Space<br></br> def initialize<br></br> # 设置变量,在 0..9 之间的 8 个字母.<br></br> s,e,n,d,m,o,r,y = letters = IntVar.array(8, 0..9)<br></br> # 设置约束条件.<br></br> constrain equation_row(s, e, n, d) +<br></br> equation_row(m, o, r, e) ==<br></br> equation_row(m, o, n, e, y)<br></br> constrain s.not_equal(0) # 并不是写成"s != 0" 因为我们无法重定义符号 != .<br></br> constrain m.not_equal(0)<br></br> letters.all_distinct<br></br> # 选择搜索解决方案时要使用的启发式分支.<br></br> letters.branch_using(:variable => :min_size, :value => :min)<br></br> end<p>private</p><br></br> # 使用线性方程有更好的方法。取出变量中的一个数字,<br></br> # 并且计算线性组合就像变量是基于 10 个字符的阿拉伯数字。<br></br> # 例如:x,y,z 成为 100*x + 10*y + z .<br></br> def equation_row(*variables)<br></br> variables.inject(0){ |result, variable| variable + 10*result }<br></br> end<br></br>end<br></br># 打印出问题的第一种解决方案 <br></br>p SendMoreMoneyProblem.new.solutions(:first)如果想了解更多细节,可以查看维基百科上面“send+more=money”词条相关的文章

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

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

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

find_first_solution_to define_problem do |p|<br></br> # 设置变量,在 0..9 之间的 8 个字母。<br></br> s,e,n,d,m,o,r,y = letters = p.create_int_vars(8, 0..9)<br></br> # 设置约束。<br></br> p.add 1000*s + 100*e + 10*n + d +<br></br> 1000*m + 100*o + 10*r + e ==<br></br> 10000*m + 1000*o + 100*n + 10*e + y<br></br> p.add s.not_equal(0)<br></br> p.add m.not_equal(0)<br></br> p.add all_distinct(letters)<br></br> # 选择启发式分支。<br></br> p.branch_on letters, :variable => :min_size, :value => :min<br></br>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

2007-06-26 19:301400
用户头像

发布了 74 篇内容, 共 14.5 次阅读, 收获喜欢 3 次。

关注

评论

发布
暂无评论
发现更多内容

Modus串行链路系统电气特性:2线-Modus、4线-Modus、RS232-Modus和RS485-Modus的特性

不脱发的程序猿

通信协议 4月日更 Modus 串行链路 RS232、RS485

Modbus协议在串行链路上的实现

不脱发的程序猿

通信协议 物联网常用协议 4月日更 Modbus 串行通信

对混沌工程的五个常见误解

混沌工程实践

混沌工程 故障注入 误区 生产事故 监管合规

CloudQuery v1.3.6发布,更加完善的数据操作支持

BinTools图尔兹

数据库 sql 数据安全 数据管理工具

阿里巴巴云原生 etcd 服务集群管控优化实践

阿里巴巴云原生

容器 运维 云原生 k8s 存储

防晒衣专用水性油墨说明书

C13713145387

防晒衣专用水性油墨 防水尼龙水性油墨

投资的狠人,往往是这样的

陈东泽 EuryChen

比特币 区块链 投资 李笑来 debank

《采访彩食鲜 CTO 乔新亮:如何从一名程序员晋阶为CTO》(采访提纲)

石云升

28天写作 4月日更 调查采访能力考核

最全 MongoDB 基础教程

若尘

数据库 mongodb mongo

全球案例 | NTT:Atlassian 帮助我们重塑危机中的可能性

Atlassian

敏捷 团队协作 数字化转型 Atlassian Jira

应对海量时序数据,华为云GaussDB(for Influx)有妙招

华为云开发者联盟

云原生 数字化转型 时序数据 华为云GaussDB

PHP自动加载原理

Sakura

4月日更

1小时破千万点击量!阿里巴巴首发:Java核心框架指导手册

Java架构追梦

Java 阿里巴巴 架构 面试 核心框架

SpringCloud(Netfix)-技术专题-服务注册与发现

码界西柚

SpringCloud

KubeVela 1.0 :开启可编程式应用平台的未来

阿里巴巴云原生

容器 云原生 k8s 消息中间件 Go 语言

避免人工智能存在“歧视”,要从这8大方法入手

澳鹏Appen

人工智能 机器学习 大数据 人脸识别

基于深度神经网络的噪声标签学习

华为云开发者联盟

神经网络 损失函数 深度神经网络 噪声 噪音数据

「 留言参与 」—— InfoQ 写作平台【 1 周年盛典 】

InfoQ写作社区官方

1 周年盛典 热门活动

BOE(京东方)2020年报发布: 营收1355.53亿元 净利润大幅增长162.46%

智慧城市:大数据运营中心 IOC —— Web GIS 地图应用

一只数据鲸鱼

WebGIS ioc 数据可视化 智慧城市 数据运营

重读《重构2》- 提炼变量

顿晓

重构 4月日更

LeetCode题解:剑指 Offer 49. 丑数,三指针,JavaScript,详细注释

Lee Chen

算法 大前端 LeetCode

SpringCloud(Netflix)-技术专题-自定义配置Ribbon

码界西柚

SpringCloud Ribbon

华为云PB级数据库GaussDB(for Redis)揭秘第七期:高斯Redis与强一致

华为云开发者联盟

redis 华为云 GaussDB(for Redis) 强一致 PB级数据库

多年后,我终于看清了比特币的本质

陈东泽 EuryChen

比特币 区块链

【LeetCode】实现 Trie (前缀树)Java题解

Albert

算法 LeetCode 4月日更

第一篇测试

童童

架构训练营

透气胶浆、无手感透气胶浆

C13713145387

透气胶浆 仿拔印浆 无手感透气浆

Linux grep 命令

一个大红包

4月日更

联邦学习,为何而生?

博文视点Broadview

云原生势不可挡,华为云GaussDB加速企业数字化转型

华为云开发者联盟

华为云 GaussDB

Google SoC系列:使用Ruby实现约束规划_Ruby_Werner Schuster_InfoQ精选文章