你们也应该记得我们把
这个巡逻排班的问题建了一个模型出来
然后到了我们要跑这个模型的时候,发觉这个效率不太好
要超过十分钟才可以求一个解出来。
到底在哪个地方出了问题呢? 我们再去看看这个排班问题部分的约束
我们看见就是要求当夜班的士兵的数量 要是等于
o,然后也需要 在傍晚值班的士兵的数量是在 l 跟 u 中间
我们可以看见这几条约束呢都会要计算一下 当夜班的士兵的数量,还有这个当
傍晚班士兵的数量,更重要的是
我们发觉有相同的表达式都是用来算
这个士兵值傍晚班的数量的,然后我们才要求他们是需要是 大于等于 l 跟小于等于 u。
我们叫这一类的 情况就是叫共同的子表达式。
有什么问题呢? 首先,我们浪费了计算,我们重复了计算的
值傍晚班士兵的数量在两个不同的地方 而且呢,同一个值我们出现在两个不同的地方呢
对这个求解器来讲,就有一些混乱了 要解决这个问题非常 简单。
我们可以利用所谓是中间变量
中间变量就是用来把一个我们要重复使用的表达式的值 把它存起来。
所以在我们的问题 当中呢,我们可以定义一个叫 onEve 的数组 变量。
每一个元素呢就是代表每一天 值傍晚班的士兵的数量。
然后我们把这个数组的值算出来
然后要求这个每一个元素的值都是每一天都是大于等于 l
然后是小于等于 u 的。
但是我们要要求是它的 上限跟下限是 l 跟 u。
其实是一个比较 直接的方法呢,我们就是在定义这个
onEve 这个数组的每一个元素的类型的时候,就直接说它的 类型的范围就是 l 到 u 就可以了。
然后我们下面这一个 条件,这个约束就不需要了
如果你们有留意的话 相同的表达式其实在我们的目标函数里面 也出现。
就是这个要算每一天 值傍晚班的士兵的数量
好了,我们看一看我们新的模型
前面呢跟我们之前的版本是一模一样的
就是在后面关于我们要 要算这个傍晚班士兵的数量的地方我们要改动一下
你们也可以看看,我们现在的目标函数比之前的版本简单了很多了
[空白_录音]
我们现在去把这个已经把共同子表达式的 新的模型去再跑。
我们在 4.5 秒之内就已经可以 找到这个答案了。
所以我们这个新的模型是比原来的版本的效率高很多很多
很多时候当我们要做一个划分集合问题的
时候,我们要需要就是对每一个划分的类型的大小都有一个、 一些限制
譬如说,在我们的问题里面我们要求上夜班的是有 o
个 士兵,傍晚班的就是在 l 跟 u
中间 其实呢在 MiniZinc 里面我们有一个很好的 全局约束是帮助我们做这件事情的。
这个约束呢就叫 global_cardinality
它有三个参数 x、 v 跟
c x 呢就是一个变量的数组 然后 v 跟
c 呢是另外两个数组,它们的大小是一样的
我们要求是什么呢?就是要求在这个 x
这个 变量数组里面,它可以拿到 vi
这个值的 数量是跟 ci 是一样的
我看最好就看一看一个、 一个 例子就可以了。
我们这里说 global_cardinality
(x,[1,2],[2,1]) 它的意思就是什么呢?要求在
x 这个 变量数组里面出现 1
的数量 是 2。
出现 2 的次数是 1 所以我们看看、 可以看一看。
如果我们的变量是 1、 1、 2、 3 呢 我们发觉 1
出现了两次 2 出现了 1 次,所以呢就满足了这个约束了
3 出现的次数不重要
如果我们 x 是等于 1、 2、 3、 4 这个数组的话
1 出现的次数只有 1 趟,而不是 2
所以呢它就不满足我们这个 global_cardinality constraint
了 所以呢
我们可以把所有关于要算 要值夜班、
傍晚班的约束 就可以用下面一条
基于这个 global_cardinality
的约束就可以表达出来了 我们首先需要是每一天
每一天不同的士兵他值的班 这个就是我们的数组。
我们要求呢出现 夜班的数量是
o 然后,出现这个傍晚班这个数量呢 是应该跟我们的
onEve,刚才定义这个数组 因为我们定义它的类型的范围是 l
跟 u 中间,所以就是基本上就要求它们是 这个数量是在 l 跟 u 中间的。
一条的 全局约束就可以代替了我们上面三条的不同的约束
其实这个 global_cardinality
这个全局约束有很多个不同的版本 譬如说这个叫 global_cardinality_closed
相同,它们都有相同的三个参数,其实它的
意义是差不多的,除了有这个相同的
global_cardinality 的要求之外,我们也要求在
x 这个 变量数组里面出现的值一定 是需要从这个
v 这个数组里面 里面有的数值。
所以如果我们看一看之前 我们的例子。
如果 我们这个约束是 global_cardinality_closed
的话 这个解也不满足这个 条件的,因为我们这里有一个
3 的值,这个 3 的值呢 不在这个 v 这个数组里面出现
还有另外两条的 变种呢就是
global_cardinality_low_up 这个
global_cardinality_low_up 呢,还有这个 x
这个变量数组,也有这个 v 这个数据数组
但是另外不同的就是,我们不是要求 v 的元素在 x
里面出现的 固定的次数,我们要求
vi 在 x 这个变量数组里面出现的次数是在
low i 跟 high i 中间,这个就是我们的要求
然后我们还有 global_cardinality_low_up_closed。
所谓是 closed 的意思就是我们要求 x 这个变量数组里面取的
每个元素取的值都需要在 v 这个数组里面出现的
跟我们之前这个 global_cardinality_closed 是差不多
有了这个 global_cardinality
的全局约束之后,我们看看我们的 模型又可以更简单了。
前面也是跟之前一模一样 但是后边呢,我们可以利用一条的约束就代替了
两组不同的约束了。
那 如果我们把这个全新的、 基于全局约束的版本一跑 在 1.5
秒之内就可以求解完毕了 在这个问题里面我可以看见不同的模型,它的求解的效率
都可以有很大的差别,在接下来的课程 里面我们会慢慢再深入地解释
建模是如何会影响到求解的效率的 我们来一个小结。
很多的 离散优化问题呢都是
要求我们去确定一个函数的 一个函数从一个
f,从一个定义域到一个值域 但是呢,确定一个函数也可以把它看成为一个划分
这个定义域的问题 当我们把这个问题当为一个划分问题的时候,好像我们是在
确定另外一个函数叫大 F 这个大 F
呢就是所谓这个小 f 的 伪逆函数了
在势约束下进行这个划分的时候 我们有一个很重要的子结构。
这个子结构呢就可以 很容易就利用我们这个 global_cardinality
这个 全局约束来表达出来
另外呢,我们知道共同的 子表达式是不好的东西。
如果我们遇到它的时候呢,我们应该利用中间变量把这个问题解决
我们也看见过逻辑的联结词呢是非常有用的
是可以帮助我们把这个约束好好地表达出来
[空白_录音]