优化是决策的一般形式，在我们的社会中很常见。它的应用包括从求解数独谜题到婚礼上的座次安排。同样的技术可以调度航班和机组成员，协调钢铁生产，组织铁矿从矿井到港口的运输。人力资源和材料管理上好的决策可以令企业提升上百万的盈利。同样的问题很多也在我们日常生活出现，成为决定每天送货路线，决定学校时间表，传输电力到家里等种种问题的一部分。除了它们的重要性，这些问题如果用传统的本科计算机科学方法难以求解。 这门课程为已经完成离散优化高阶篇的同学设计。 请看这门课程的宣传视频：http://www.cpr.cuhk.edu.hk/cutv/detail/988
3.1.5 搜索
Loading...
From the course by The Chinese University of Hong Kong
离散优化算法篇 Solving Algorithms for Discrete Optimization
ratings
From the lesson
基础约束编程
这个模块开始时用例子说明约束编程求解器的基础技术，也就是约束传播和搜索。值域代表了变量可能的取值，而约束可用于在值域上进行推理。约束本身可以以值域传播器和边界传播器的形式表示。你将会学习到一个传播引擎如何处理一组传播器，并通过变量值域协调沟通约束传播得到的信息。你也将会学到基础搜索，变量，数值选择等概念，还有传播和搜索是如何紧密而高效地连接起来的。最后，这个模块介绍了如何在Minizinc中进行编程化搜索。
Meet the Instructors
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
神农氏深知 世人面对疾病无能为力，希望到天神花园采药，
研制能治百病的药方，造福世人。
女娲以及上天编订录制一个药柜， 药柜共有十行、
十列，柜中抽屉均有五种种子，分属五行。
倾侧抽屉，可使种子触地萌生，
长出药草，神农可将所有抽屉逐一倾侧，使其长成
百草森林，并于当中逐一尝验，拼凑出符合神奇 药效条件的药方。
第一，每行上前后相邻抽屉所选药草属性 必须相生或相克。
第二，第一个抽屉的药草不可为金属性。
最后，每列上所选必须有至少一种，至多两种金属性药草。
而对 土属性亦然。
为百草药园过于巨大，神农氏恐难完全探寻，
诸葛亮遂召唤时空飞龙，令神龙尽快找出满意的百草药方。
>> 神农为了要治病，所以他要研发一个 有百草的一个药方。
女娲呢就提供了这个 药柜，这个药柜呢有十行也有十个列的抽屉。
在每一个抽屉里面呢，都有五种草药的 种子，它们呢都分别有不同的属性的，
分别就是金、 木、 水、 火、 土。
神农要做的事情就是把这个每一个抽屉顺序地拿出来，
然后呢，把里面的种子呢就撒到这个地上，然后这个神奇的种子呢
不但会把这个草药生出来，而且呢也会
这个做五条不同的道路出来，然后呢在这个路的远端呢
就把这个每一种的草药生出来。
神农呢然后 又要需要在每一条路的远端呢再撒这个种子，
然后呢就可以建立一个草药园出来了。
然后神农要做的就是，到这个草药园这个迷宫里面到处走走，
做一些搜索，然后也尝一尝这个百草，然后呢就希望可以研发出这个神奇的药方出来。
但是呢，这个药方呢当然有一些 条件要满足的。
第一个条件呢就是 在这个药方里面，如果这个草药是从同一行的
抽屉里面拿出来的话，如果呢这两个抽屉它们呢就是在同一行的旁边的
第一个跟第二个，那这两个草药的 属性就要满足一个我们所谓是这个
草药之间的属性的一个相生相克的一个关系，这个关系呢我们
就列到放在这个表格里面。
譬如说，如果我们第一个抽屉 有的是水这个属性，然后第二个抽屉的草药呢
是火的属性呢，根据这个表呢这个是满足的。
但是如果第一个抽屉里面的草药是水，但是第二个抽屉里面的
属性呢是金的话，你看看在这个表格里面呢是没有的， 就是不满足这个条件的。
而且呢，我们就要求在同一个行上面的抽屉 如果它们在旁边的，就要满足这个相生
相克的这个条件了，所以第二个跟第三个抽屉， 第三跟第四个，第四跟第五个，到了最后，第九
个跟第十个都要满足这个我们所谓是行的条件。
第二个条件呢就是关于第一个抽屉的，第一个抽屉呢，无论你
选任何的草药，我们就是这个草药的属性不可以是金的，这个就是这个药方
的一个非常特别的一个要求。
我们还有一个条件，如果我们选取的草药
都是从同一个列出来呢，那我们有另外一个要求，这个要求就是什么呢？
在这十种的草药上面，我们最少有一种 最多两种的草药呢它的属性一定是金来的。
对于这个土的属性的草药呢，我们也有相同的要求，
就是最少一种最多两种的草药呢是为这个土这个属性的。
所以如果我们看这个的排列呢，这个是满足的， 因为在里面呢，我们看见有一个金的属性的草药，
然后呢也有两个土的属性的草药，所以这个是满足的。
但是在这里呢，我们有两个土的属性的草药，但是呢没有金的草药在里面，
所以这一个排列呢是不满足我们这个列的条件的。
好了，我们现在就可以看清楚我们这个草药迷阵的问题。
我们这个问题里面有一个百草的药柜，每一个抽屉里面都有五种不同属性的草药的 种子。
神农要做的就是顺序把这个抽屉拿出来， 帮助我们长出不同的草药跟这个草药的迷阵。
长出了草药之后，当然神农就要寻找一个神奇的药方了，但是这个
药方呢需要是满足下面这三条的条件。
第一个条件是 跟这个草药从一行的抽屉里面拿出来的草药
如果它们是相邻的话，我们就要求呢它们是会 它们的属性是会符合这个相生相克的关系的。
然后我们刚才也讲过，第一个抽屉里面呢我们选取的这个草药呢
不可以是金的属性的，然后最后呢就是如果这个草药呢
是从一个列里面拿出来的话，
我们就要求呢最少一种最多两种的草药呢，它们的属性应该是金。
也有相同的要求，对于这个土这个属性的草药。
好了，怎么去解决这个问题呢？ 当然呢，我们其实有一个非常简单的方法，
这个方法呢其实也非常地笨的，其实就是按部就班地尝试每一个一百种的
草药的不同的组合得出来的药方，
然后对每一个药方呢完成之后呢，你就又检查了，神农需要检查 是否所有我们刚才提到的三种的约束
都给满足了，如果是的话，那我们非常幸运，我们已经发现了一个神奇的药方。
如果不对的话，我们就去尝试下一个
一百种草药的组合，直到我们可以找到我们的这个神奇的药方。
但是大家有可能都已经想到，就是 利用我们这个非常笨的一个方法呢，最差劲的情况之下
我们是需要尝试 5 到 100
平方这样子 多个组合的药方，这个方法呢其实我们也叫它是生成和
测试，其实是一个十分之不切实际的一个方法来的。
所以呢，我们神农呢也不应该用这个方法来做，不然呢他要
花到这个天荒地老也没有办法去找到他的这个神奇的药方的。
好了，我们现在就提供一个比较好的一个方法，我们这个方法呢我们叫它时序的
回溯搜索，那这个方法呢其实挺简单，我们首先
选择一个决策，在我们这个问题里面所谓一个决策呢就是
一个抽屉里面五种不同的草药，到底我们应该选择哪一种的草药呢，或者说
选择哪一种草药的属性呢？然后呢 我们每拿到一个抽屉，我们选择了
其中一个可能性之后呢，我们要保证我们刚选择
这个可能性呢要跟我们之前已经做了的决策呢是要兼容的。
如果发现当前的这个选择跟之前某一些决策，或者是
约束有一些冲突的话，我们就需要考虑另外一个可行的选择了。
如果我们利用这个方法呢，可以把所有的决策都都都
都做了一个选择，而且所有的选择都都都是互相兼容的话，那我们就已经找到我们要 要求的一个解了。
但是，如果我们发现在任何一个步骤里面发现有
一个我们现在做的决策呢是不可以满足，肯定呢就是我们之前做的一些决定
或者是上一个，或者是上上一个肯定是有问题，那么我们就要回到
好，之前做过的决策，把这个决策呢，要改变它的选择了。
这个就是我们所谓是时序的回溯的搜索的方法。
我们下面就可以看看我们怎么利用这个时序
回溯的搜索的方法来解决我们草药
这个迷宫的一个问题。
首先呢，我们就看 我们第一个，首先就是我们要先解决一个 比较小型的一个问题。
在这个小型的问题里面呢，我们只有 3 行跟 2 列的抽屉。
好了，我们 看看我们第一个抽屉。
每一个抽屉都有 5 种不同的 种子，它们的属性都是金木水火土。
所以呢，我们就先看看第一个选择。
第一个选择呢就是我们试试，第一个抽屉我们选择这个 金这个属性，好不好呢？然后我们就发现
这个选择是不行的，因为它就违反了我们 第 2 个约束。
我们第 2 个约束就是说，第 1 个抽屉呢，我们绝对不可以选择这个金 这个属性的这样子的草药的。
所以呢，我们就需要去尝试第 2 个选择。
就是木，也因为木呢，我们也没有之前的选择，也没有其他的
约束，所以我们就可以看看另外一个抽屉，就是我们第 1 行的 第 2 个抽屉。
这个抽屉里面当然还是相同的 5 种的选择。
我们就先选这个金吧！然后呢，我们发觉呢，
根据这个，因为这两个抽屉呢，它们是在同一行，然后在旁边，
我们就要看看它有没有满足这个相生相克的关系。
我们发现如果第 1 个抽屉是 木的话，它的旁边这个抽屉呢，只可以是火，或者是土。
所以呢，我们知道，它是，如果第 2 个抽屉选择的是金呢，
这个是不可以满足这个条件的，所以我们要选择另外一个——木。
刚才已经讲过了， 木木也是不满足这个条件的，木跟水也是不满足的，所以呢，最后我们就要选择
这个木跟火了，这个就满足了我们，起码满足了我们这个 相生相克这个条件。
然后呢，我们为了两个抽屉选择了它的可能性。
那我们就去到第 2 行第 1 个抽屉看看。
第 2 行第 1 个抽屉呢，里面也有 5
种的 草药，我们当然呢，一开始就选择金，可不可以呢？
我们发现呢，没问题，没有违反任何的条件。
然后我们就看看 第 2 行第 2 个抽屉呢。
第 2 行第 2 个抽屉呢，我们先 选择呢，也是第 1 个可能性，就是金这个属性。
我们发现呢，金这个属性 只可以是金跟水、 金跟木，所以金跟金是不行的。
所以呢，我们就要试另外一个。
我们发现呢，金跟木是可以的。
所以呢，我们 就可以到这个第 3 行第 1 个抽屉里面去做选择了。
然后呢，我们当然第 1 个选择就是
金，看看可不可以呢？如果大家还记得的话， 我们还有另外一个条件的。
就是在同一个列 的草药上面呢，它们要最少有一个是金， 最多是两个是可以是金的属性。
这个好像是没问题哦。
但是呢，我们还有同一个要求呢，是给属土，土这个属性的 草药的。
我们发现呢，在这个第 1 个列里面呢，就是没有土这个属性的 草药的。
所以呢，我们就是违反了这个条件。
所以呢，我们就要试试看木可不可以。
我们发现呢，改了木之后，我们还是没有土。
所以呢，还是不行。
我们发现呢，水跟火还是不行。
所以最后呢，我们就要为了这个抽屉 选的是土，所以呢，有一个金，一个土，我们就满足了这个第三个条件。
好了，有了这个之后，我们当然就可以放这个，
为了这个最后一个抽屉呢，去选择一个草药了。
我们还是有 5 个可能性，但是呢，因为我们现在在同一个列， 我们要保证这个抽屉跟这个抽屉选择的
草药的属性要满足我们之前提过的这个相生相克的 这个条件。
我们发现呢，如果是土的话， 就只可以跟金是
可以兼容，这个是没问题。
所以我们满足了这个，但是呢，现在我们在 右面这一个列呢，已经都放上这个草药了。
我们还有一个 条件是要满足的，就是在同一个列上面呢，我们起码有一个金，起码有一个
土，最多有两个金，最多也有两个土。
我们发现呢，现在这样子的情况之下呢， 是没有土的。
所以这个地方提示我们是不可以放金的。
所以呢，我们就要放木了。
放了木之后呢，我们发现这个土、 木 其实是不满足这个相生相克这个条件。
所以我们就要试另外一个，土跟水，
是行的，但是我们放了水之后，这个列呢就没有金也没有土，所以就违反了
这个条件，所以我们要试火。
火呢，其实也是不满足的，所以最后呢，
我们发现还是要放这个土，放了这个土之后呢，但是还是不满足
这个相生相克这个条件。
因为土、 土是不在这个 关系里面的。
所以呢，土这个呢，也不可以选。
就是说呢， 我们刚才做的，在上一个做，为了这个第
3 行第 1 个 抽屉做的一个决策是有问题的。
所以呢，就是说 我们也不可以选这个土。
所以我们要回溯了。
发现呢，原来就是我在上面，就是第 2 行第 2 个抽屉呢，
我们其实不可以选这个木的，所以呢，我们应该选呢，就是水。
我们选，放了水之后呢，我们发现，金、 水是可以的。
所以我们 就可以继续，看看在第 3 行第 1 个抽屉要放，选择什么的草药了。
第 3 行第 1 个抽屉呢，我们发现有 5 个可能性。
我们可不可以放金呢，放了金之后，我们发现会违反 最后这个条件。
就是因为在现在这个列里面呢，没有土这个属性的草药。
所以呢，我们就要试试另外的可能性。
木可不可以呢？ 我们发现也没有土，不行。
水也不行，火也不行，所以最后呢，我们应该就放土这个 选择土这个属性的草药了。
好了，到了 这个之后呢，我们当然就可以尝试去放，选择为了最后一个抽屉 选择一个草药了。
我们最后当然也是有 5 个可能性。
我们先看这个金，放了金之后呢，我们发现
是没问题的，但是呢，就是对这个相生相克是没问题的。
但是呢，对最后的一个条件，就是在这个列里面呢，我们发现我们没有土这个属性的 草药。
所以呢，这个是不行。
我们可以试试看这个木。
木，我们发现呢， 这个土跟木不是兼容的。
所以这个也不可以，然后我们发现呢，其他的可能性呢，
都会违反，有可能是违反我们的相生相克
这个条件，也有可能是违反我们最后的一个列里面起码有一个金，
一个土，或者是最多是两个金，两个土这个条件的。
所以我们到了这里呢，还是没有找到我们的 需要求的一个解的。
其实呢，刚才 看见了就是我们，显示我们怎么利用这个时序
回溯这个搜索的方法去做搜索。
我们刚才 其实呢，就是搜索到这个地步。
如果你们有耐心的话，你们可以继续的这样子，去 搜索，就是为了每一个决策做一个
决定，然后看看跟之前做的决策有没有兼容。
然后如果这样子继续去搜索的话，我们发现呢，
到了，搜索到这个右面，最后
我们可以在这个地方，可以为我们这个问题求到一个 解的。
好了，我们现在 其实就可以呢，为我们刚才看见这个故事
与我们从前学过的东西做一个对比。
大家一看，也应该知道呢，其实我们这个
寻找这个药方的一个问题呢，是一个
这个约束求解的一个问题来的，所以呢我们其实可以看看它的 MiniZinc 的模型是怎么样。
我们在这个模型里面有两个参数，分别就是 r 跟 c
这个 r 跟 c 呢就是代表我们这个药柜呢有多少行跟多少列。
我们刚才看过 的就是一个比较小型的一个问题的版本。
然后我们也定义了一个 枚举类型来把我们每一个药柜
里面抽屉的不同的草药，它的属性金、 木、 水、 火、 土都列出来。
然后在这个模型里面最重要就是这个二维的
一个变量的数组，这个数组呢就是为了每一行每一个列
这个抽屉我们到底要选择哪一种属性的这个草药呢？
然后当然我们也知道这个我们选取的草药呢，是要满足一些 条件的。
第一个条件呢，其实我们就可以利用一个很简单的 table
的全局约束，就是说在同一行，如果这两个抽屉呢它们是在旁边的 在旁边的，
j 到这个 j + 1 ，这个抽屉我们要求呢它就是满足
我们这个 table 的全局约束，这个 table 的全局约束呢就是把我们刚才提到过的
这个相生相克这个条件呢列出来的。
我们当然还有其它的条件。
这个第二个条件呢就是说第一个抽屉呢，我们选择的
草药呢，它的属性不可以是金来的。
然后呢最后就是如果在同一个列，同一个列上面的 抽屉选择出来的草药呢，我们要求呢就是
里面呢起码有一个最多是两个的属金 的草药，也有起码一个最多是两个是属
土的这个属性的草药，然后下面就是只是一个 solve
satisfy 的项，然后我们就是把这个结果呢输出。
好了，另外呢，我们刚才也一步一步呢去
建立一个我们所谓是搜索树，这个搜索树呢 其实呢跟我们这个神农去建这个
草药园这个迷宫呢是一摸一样的，这个也是
所以刚才这个神农要去做搜索的时候也是在
这个草药园呢，就是根据这个搜索树呢来希望可以找到 它这个神奇的药方。
看完刚才的显示之后，我们在下面就希望
可以比较详细地介绍一下我们刚才做解决问题方法的一个算法。
首先就是有一个集合我们需要介绍的，这个集合呢我们叫 fixed(D)。
这个 D 呢就是我们这个问题里面每一个变量它的值域，这个 fixed(D)
这个 集合呢里面包含呢就是一批的变量，这一批变量呢我们都是已经给它赋值的
我们就说这个变量是已经给固定的，然后我们就说这个给固定的这个
变量呢它是属于 fixed(D) 这个集合。
然后呢 我们就要介绍一个，另外一个有，非常有用的一个
函数，这个函数呢叫 satisfied(c)，这个 satisfied
这个函数呢就拿 一个参数，这个参数呢就是一个约束 c 来的。
我们 调用这个 satisfied 时候我们就假设呢，这个约束 c
呢里面所有 的变量都已经是给固定的，然后所以我们就很非常容易呢就可以决定
到底这个约束 c 呢是否已经给满足或者是被这个违反了。
有了这个 fixed(D) 跟这个 satisfied(c) 这两个东西之后呢，我们就可以介绍一个非常重要的一个
函数，我们叫 check(C, D)。
check 这个函数呢就有两个参数，就是 大 C
就是一个约束的集合，这个 D
呢就是这个约束里面所有的 变量它们的值域。
这个 check 这个函数非常简单，它就是 利用一个
foreach 这样子的循环呢去检查我们这个大 C
集合里面的所有的每一条的约束小 c，
然后如果我们发现这个小 c 呢里面所有的变量都已经是给固定的话，
那我们就可以调用我们刚才介绍过这个 satisfied 这个
函数呢来看看到底这个约束呢是否已经被 满足或者是被违反。
如果我们发现这个大 C 里面的其中一个
约束呢是被违反的话，那我们就这个 check 这个函数呢
就会这个返回一个空的值域，不然的话，我们就把我们原来的 这个值域呢返回就可以了。
有了这个 check 这个函数之后我们就可以
介绍一下我们这个最基本的回溯 搜索这个算法了，我们这个算法呢我们叫这个函数叫
back_search，它也是有两个参数的，也是 跟之前一样，大 C
这个参数呢就是一个 约束的集合，而 D 呢就是这个约束里面的变量它们的值域。
如果我们发现我们所有的约束里面的
变量呢都已经是给固定的，那么就非常简单了，我们就调用我们刚才 提过的这个
check 这个函数呢，就看看是否这个问题里面每一条的约束都是 已经给满足了。
不然的话，我们就利用调用另外一个 函数，我们叫
choose，这个 choose
函数就是从我们问题 里面还没被固定的变量里面选取其中一个，
我们就返回把它放在 X 这个变量里面。
然后呢就非常简单了，我们 还是用利用一个非常简单的
foreach 的循环，这个 foreach 的循环呢就会把这个 X
这个变量里面的 值域里面的每一个数值，每一个数值 D
都检查一下，怎么检查呢？ 这个检查就是利用我们
check 这个函数去看看它是否跟我们之前已经
做过的决策是不是兼容，这个就是所谓这是检查。
如果我们发现它跟我们 之前做过的决策是有这个冲突的话，如果它，大家还记得这个 check
就会返回一个空的 值域了，不然的话，它返回的值域呢就是没有改变的，就是说刚才这个 D 这个数值呢
是跟之前的决策是没有违 都是兼容的，那我们就可以利用这个递归的方法，继续
去为我们这个问题呢做这个搜索， 直到呢我们可以把所有的变量都可以
把它固定，它的值固定，而且呢固定的值互相之间是兼容的。
又或者呢，我们发现无论我们怎么看这个值域里面的
哪一个的数值都发现没有办法是跟之前的兼容的，我们就要返回一个空的 值域。
好了，刚才呢其实在这个算法 里面呢有两个地方是非常重要的。
第一个地方呢，就是在这个 choose，这个 函数里面。
这个 choose 这个函数呢是帮助我们选择下一个变量 去检查的。
其实呢，这个 choose 这个函数呢
对我们的搜索的效率呢的影响呢是可以非常的 大的。
不同的选择呢可以影响到，直接地影响到 我们这个搜索树的大小。
一般来讲呢这个 choose 这个函数呢都
可以允许我们采用不同的方法来选择我们在搜索的时候 下一个变量是什么来的。
最简单的方法呢就是很简单就是利用呢 我们原来的变量它们输入的顺序，来选择下一个
变量去检查，但是呢其实我们还有其它的可能性的。
譬如说，我们可以基于呢剩下来的
变量它们的值域的大小来选择，通常呢我们是希望选择一个
值域的最小的一个变量来检查的。
但是我们也可以 根据这个变量里面，值域里面的最小的值或者是最大的数值呢
来选择也可以的。
我们在下面后面呢就会有一些例子可以介绍给大家的。
我们刚才这个搜索的一个算法里面另外一个重要的地方 当然了，就是这个 foreach 的循环。
如果大家还记得的话，这个 foreach
的循环就是把 我们选择了这个变量里面的值域，把里边不同的可能性就
是它的数值 d 呢，一个一个去检查。
我们要检查就是希望 知道呢，这个 d
这个数值呢，跟我们之前做的决策是否有 冲突。
我们最简单的，实现这个 foreach 的循环呢，就是
把我们这个值域里面的数值呢，从小到大去 检查这个是最简单的方法，但是呢，其实这个
foreach 的循环呢 是直接会影响到呢，我们去搜索这个树里面的分支之间，它们的左右的
顺序的，如果我们可以有一个有效的方法 去把这个值域里面的数值去排序，
那我们是有可能呢，可以把这个搜索树上面包含我们要找的解这个分支呢放
到这个搜索树靠左的一边 靠左的一个地方，这样子呢，根据我们搜索的方法呢，我们
就可以提早呢，把我们要找的解呢，就可以找到了。
而且呢，要强调一下就是我们这样子的 利用这个
foreach 把值域里面的数值去排序呢
对于如果我们要搜索单一个解的时候呢，是非常重要的。
直接会影响我们找到这个解的效率，因为刚才已经讲过了
如果我们有一个有效的排序的话，我们就可以尽量把这个有解的分支呢，尽量
推到这个左边，那我们就可以提早地把我们要找的解可以找到了。
但是呢，我们现在这个 foreach
里面对这个值域的排序 对于如果我们这个问题需要我们把问题里面全部的解都找到的话
我们这个把这个 值域里面的数值排序呢，就没有什么重要了。
我们要问问大家到底这个是为什么呢？大家可以想一想，然后
我们之后再跟大家讨论这个问题。
但是，虽然我们现在在讲的就是解决这个
约束求解的问题，到后来呢，我们会讨论呢 怎么解决这个优化的问题。
到了我们要解决优化的问题呢 这个把值域里面的
数值好好地排序呢，变得更重要了。
我们刚才呢，提到这个算法呢，只是
单纯地做这个搜索，但是我们其实，如果大家还记得呢，我们之前
曾经提过一个非常重要的技术，这个就是约束全部的技术。
这个约束的全部技术呢，就是帮助我们把一些
变量到值域里面，一些确保不会出现在我们的解 里面的数值呢，把它们移除了。
如果我们可以把这个 变量套到值域里面没有用的数值移除的话
那在我们做搜索的时候，每一个搜索的树上的节点呢
就有更小的分支的系数了，就是说我们这个搜索树 呢，就可以变得更小。
所以呢，其实我们之前学过 的这个全部的技术，跟我们现在介绍这个搜索的
这个技术呢，他们大家是可以合作地非常好的。
呃，这个思路其实是非常简单，在我们搜索的时候，在每一个节点上面，我们
在要准备搜索下一个变量之前呢，我们就进行这个约束的传播
就可以了，我们在下面就可以显示一下，看看这个 传播跟这个搜索，怎么可以好好地合作，把我们要
搜索的范围，就是我们的搜索树变得更小。
好了，还是我们原来的问题，就是一个小的
小型的一个问题就是有三行跟两个列的抽屉，在下面呢
就是我们也列出每一个抽屉里面现在可能的
草药的属性还有什么，当然在开始的时候，每一个抽屉里面呢
我们还有五种不同的属性，就是金木水火土了。
好了，但是我么一开始就看我们第一个抽屉了。
我们在选择其中一个可能的属性之前呢，我们就应该做这个约束的
传播，我们一做约束的传播呢，我们就发现原来大家 还记得那第一个抽屉里面，我们不能够选择一个是金的属性的
草药，所以我们没有开始搜索之前，我们已经发现这个第一个选择 已经没有了。
所以我们第一个尝试的选择呢，就是木这个选择。
我们放到这个木这个选择之前呢，在我们要看
抽屉之前呢，我们就在要做一趟的约束的传播。
我们发现呢，约束的传播非常厉害的。
我们发现很多其他的 变量，它们里边的可能性已经大大地减少了。
譬如说我们看看这两个 抽屉，就是第二行跟第三行第一个抽屉，我们发现呢
就算我们只是放了一个木在第一个抽屉呢，在第二个
跟第三行这两个抽屉呢，里面的可能性已经减少到只有剩下两个，为什么呢？因为我们已经
利用得到我们第三个条件就是我们列的条件，我们要求就是我们的每一个列
在上面呢，起码有一个金、 起码有一个土，或者最多是两个金。
最多是两个土这样子属性的一个草药，所以因为我们第一个抽屉已经放了木
所以他们就知道了在这两个抽屉里选择的草药，一定是金
或者是土的，我们可以做相同的推理呢，就可以知道其他的抽屉
它们剩下来的可能性，那这个就是非常厉害的一个 传播，已经给我们推导了很多重要的信息。
好了，所以呢，我们就可以知道，当我们要选择第一行
第二个抽屉的时候，其实它只是剩下一个可能性，所以呢，我们就不需要选择
另外的四个，我们就可以选择这个土的可能性了，我们放了这个土之后呢，我们就可以
再做这个传播，但是这个传播已经在没有什么改变，所以我们就可以看看
第二行第一个抽屉，然后呢，我们发现我们只剩下两个可能性 就是金跟土。
当然呢，我们就可以随便选一个，我们先尝试金吧。
做了这个金之后呢，我们再做约束的传播。
我们发现呢，其他的
抽屉里面的可能性呢，再进一步地减少。
然后 我们就可以看看第二行第二个抽屉，因为我们没有其他的选择，因为它们
只剩下木这个可能性，所以我们就选择木，我们在做
约束的传播，但是已经没有什么可以改变了。
然后所以我们知道呢，在这个第三行的
第一个抽屉呢，只剩下土这个可能性，选了土这个可能性之后，再做这个
传播也没有什么改变，但是我知道最后一个抽屉呢
只有最后一个选择，就是一定要放金这个属性的 这个草药。
在短短的 几部这个搜索里面，而且呢，我们可以看见这个传播
帮助我们把很多没有可能的选择呢，一早就把它移除，我们的
在搜索的时候用花的努力就减少了很多。
而且很快呢，我们已经为我们这个问题呢，取到一个解了。
好了，这个呢就是我们很简单地去把我们原来的
bagsearch 这个算法呢变成了一个强化的版本。
就是把这个搜索跟传播呢结合在一起，我们叫这个新的算法呢就是 prop_search
这个 prop_search 呢里面总共有三个参数。
其实呢，开始这两个参数 F0 跟 Fn
呢就是 之前的这个约束，但是我们现在要处理的不是约束，而是
传播期，而且呢，F0 这个传播期呢就是开始的时候，我们已经假定
我们不应该调用它们的，调用它们也不会对这个值域有任何的改变的，Fn呢就是有机会
我们调用它们的时候就可以给这个值域做成改变的。
我们在这合格prop_search里面呢 就是第一步要做呢就是去调用我们之前看过
这个传播这个隐形，做了这个传播隐形之后呢我们就会
把我们这个问题里面不同的变量的值域里面一些一定不可以
不可行的一些数值呢已经移除了，其他的部分呢根本就跟我们之前的差不多。
唯一不同的地方呢，就是我们现在要处理的不是约束
是这个，是传播器，所以呢我们要
加进去的是这个X=D的传播器，而不是X=D这个约束本身。
这个就是我们强化了的搜索的一个版本。
好啦，其实呢 在今天我们应用的求解器呢
里面我们的搜索的方法呢都不是好像刚才一样选择了一个
变量之后我们就一个一个检查它的变量的值域
的每一个值，我们通常呢都是做一个所谓是二叉分支的方法。
所谓这个二叉的分支方法是怎么样呢？我们叫，我们这个新的算法呢 叫bin_search，就是二叉的搜索的一个方法。
我们开始的时候当然还是要调用我们的这个传播的 引擎，做了这个之后呢，我们就会
看看到底有没有空的值域。
有的话，我们就知道呢 我们这个问题原来是没有解的。
如果呢 所有的变量它的值域呢
它们的大小都是只有单元素的话，那我们就已经把所有的变量 都给固定了，所以我们就已经找到一个解了。
好了，但是如果我们都 不是不满足这个问题是有解的，所以我们
下一步要做呢，就是利用truth这个函数呢把这个
我们这个问题划分为两个子问题 这两个子问题包括就是c1跟c2。
然后呢，我们就利用这个 递归的方法，这个bin_search呢来处理第一个子问题。
然后 解决了之后，我们才在处理这个第二个子问题。
那当然呢 这个truth这个函数到底是怎么把我们的问题划分为
两个子问题呢？我们下面就跟大家比较详细地去分析。
好啦，刚才提过这个truth这个 函数呢是非常重要的，因为这个划分点呢
是会直接影响我们这个搜索数的 大小，也是直接地影响呢我们搜索的效率的。
我们通常呢是会怎么做呢？我们通常呢这个truth这个函数呢
会选择一个它的值域呢有多于1个元素的
值域，我们要选择一个变量，它的值域呢有多于一个元素的。
找到这样子 的一个变量之后呢，我们就在它的值域里面选择其中一个元素出来
一个数值出来。
然后呢，我们分开两个子问题呢就是分别 x=d这个子问题跟这个x≠d这个子问题。
就是说我们先处理假设x=d会有什么
情况发生呢，有没有解呢？然后我们解决了这边的第一个子问题之后呢
我们才处理呢x≠d这个子问题，我们这样子做呢我们叫
叫做，这个方法就叫做这个标签化的赋值的一个方法。
我们其实呢，特别在这个问题里面 如果这个x这个变量它的值域是非常庞大的
非常多这个元素在里面的话，我们还有另外一个方法呢来把我们的问题 划分。
这个划分的方法就是也是在里面呢选择其中一个可能性的 数值，有了这个数值之后呢，我们划分出来
的两个子问题呢，第一个就是x≤d， 另外一个子问题呢就是x≥d+1，就是
这两个的划分出来的子问题呢把我们原来的 问题呢划分开来了。
我们这个方法呢，叫做这个值域的分割。
好，但是有一点我们需要留意的，如果我们在这个值域里面选取
的这个数值呢，就是我们值域里面最小的值的话，我们这个标签化的赋值
跟我们这个值域的分割呢其实是出来的效果呢是一样的。
好啦，我们这个利用这个传播
求解的跟这个搜索加起来的求解的一个方法
其中一个好处的地方呢是什么呢？就是我们作为一个用户呢其实是可以
给我们的求解器呢指定一个特定的搜索的 策略的。
所谓是策略呢，就是我们要告诉我们的求解器 它们在这个搜索的过程之中在这个搜索树的每一个
节点呢，我们就可以给它一些额外的信息告诉它
他它应该是怎么去做这个搜索的。
如果一个好的搜索的策略呢，其实是可以为我们的搜索的效率 带来指数级的这个差异的。
但是呢，我们有一点是要注意的。
我们是不需要对所有的变量都需要给它标签化的。
因为呢，因为我们在一个问题里面，很多时候呢我们的变量分开是主要的变量
也有辅助的变量，很多时候呢辅助的变量呢在我们主要的变量已经拿了这个，已经
给赋值之后，那我们的搜索的过程呢就
会已经自动替这个辅助的变量呢 就会为它赋值的。
所以呢，我们就不需要对我们问题里面所有的变量都需要 给它标签化了。
好啦，在这个minizinc这个语言里面
其实就有一些语法可以帮助我们可以
把我们的一些对这个搜索的策略的建议可以
告诉这个求解器知道。
那当然呢，我们要明白一点 我们只是可以给建议，这个求解器呢不一定会把
我们的建议去采用的，譬如说我们给的建议是给这个约束求解这个
算法的，但是如果我们minizinc当时是调用一个MIP
的求解器或者是一个局部搜索的求解器的话，这些对这个约束求解的
搜索的建议呢根本就对这两类的求解器呢是没有 作用的。
所以呢它们就一般这样子的情况之下就不会 采用我们的建议了。
好啦，讲了这个之前呢我们就可以 知道呢在介绍呢在minizinc上面呢我们有一些所谓是
搜索的注解，这个搜索的注解呢就是帮助我们用加呢把我们搜索的
策略呢告诉我们的求解器的。
这个搜索 的注解呢就是通常都是用在这个solve项
上面的，我们分别有这个int_search，bool_search 跟float_search，这是针对这个整数的搜索。
这个bools值的搜索，还有这个浮点数的搜索。
那当然呢 我们的专注这个整数的搜索。
无论我们做什么的搜索呢 这个搜索的注解呢都有四个参数。
第一个参数呢就是一系列的变量。
就是说我们要搜索的变量是什么来呢，然后第二个参数呢就是
告诉这个求解器我们怎么选择
下一个变量来搜索呢，然后第三个参数呢就是决定
我们选择了一个变量之后，它里面这个变量它的值域里面
的不同的数值我们应该利用什么的顺序来检查每一个值域里面的数值呢？
第四个参数呢，我们可以不理它的，它现在还留下来呢是因为历史的因素。
我们永远都是放complete这个字在这里呢就可以了。
而且呢，我们也需要知道我们这个第一个参数Vars是不需要
把我们问题里面所有的变量都放在里面的，如果 这个Vars没有包括我们问题里面所有的变量的话，
我们把这个Vars里面的变量都经过这个
做完这个搜索之后呢，这时候这个MiniZinc就会 这个求解器就会利用这个默认的这个搜索的策略，
来处理剩下来的变量。
好，我们现在可以比较详细的看看
到底我们这个搜索的标签是由什么来 选择的。
我们再看一看我们这个搜索的标签呢 是有四个参数。
第一个参数刚才已经提过了，就是一个 变量的数组，就是我们要搜索的变量。
第二个参数呢就是所谓是Varchoice 就是呢，我们怎么选择下一个变量来搜索呢，大家要记住
这个呢是非常重要的一个选择。
因为这样选择哪一个变量呢， 是可以为我们的搜索的效率带来 指数级的差异的。
其实大家MiniZinc里面其实 这个第二个参数呢提供了四个不同的可能性。
第一个可能性呢 我们叫 input_order，这个 input_order
呢就是基于这个变量给定的输入的顺序 来选择下一个这个变量。
第二个可能性呢就是first_fail，first_fail呢就是选择 下一个选择的变量呢就是要求呢它的值域的大小呢是最 小的。
如果我们选择这个变量它的值域是最小的话
我们有的选择值是最小，有的选择值是最小呢就是我们可以有可能
要失败就比较早一点，所以这个选择呢我们叫first_fail。
另外剩下来两个呢就是基于我们这个变量的值域里面的最小的值，
我们要选择一个变量里面的值域里面有的最小的值是 为最小的，这个就是smallest。
largest 呢就是选择一个变量，它的值域里面最大的值 现在所有的变量里面是最大的，这个呢四个恒心呢就是给我
们的Valchoice就是我们怎么选择下一个变量，对于这个
数值的选择呢，我们也有四个可能性。
再讲一次，这个数值的选择就是它的顺序呢，
是会影响到呢我们的解会不会更早 的出现在我们的搜索处，就是是不是在我们搜索处的
比较靠谱的地方出现，因为这样子的话我们就可以提早的把这个解集 找出来了。
我们其实也有四个可能性，第一个可能性呢就是非常简单，
就是根据这个值域里面的顺序，从小到大，这样子去检查里面的数值。
另外一个indomain_max就是刚刚相反，就是从大到小去这个顺序来 调里面的数字。
indomain_median就是先选择我们这个值域里面的中位数，
然后去和这个indomain_random呢就是做一个随机的一个选择就可以了。
好啦，现在就鼓励大家呢就是可以去跑一跑这个
MiniZinc，虽然呢我们故事里面的朋友呢他们都
已经不可以用minizinc，但是你们还可以的，所以我建议你们也跑跑
把这个MiniZinc呢跑一跑，我们这个
药方这个模型 你们可以利用这个
不同的策略，就是利用我们刚才提到的，对于这个选择哪一个变量有四种方法，
对于选了一个变量之后怎么 检查，根据什么顺序去检查里面的
值域的数值呢也有四个选择，建议 大家呢可以在里面这个minizinc模型里面，
去试试这四种 不同的变量的选择，四种不同的数值的选择。
看看出来的效果是怎么样？而且呢，其实你们也可以把问题里面的
r就是行数跟它的c，它的列数相加，看看里头怎么可以找出一个
最棒的一个搜索的策略出来，而且我也非常
建议呢大家可以尝试呢，把这个不同的搜索策略出来呢搜索树，
搜索树呢画出来，你们也可以其实可以利用我们机构这个求解器Vars
供带的一个叫gist这个系统呢来帮助 你们去浏览这个出来的搜索树。
看看它们的形状是怎么样的？ 好了，除了我们可以利用这个MiniZinc
来求单一的解之外呢，我们也当然可以用这个MiniZinc这个 iii
呢来要求这个MiniZinc呢把我们的问题里面全部的解都求出来的。
我就建议大家呢基于一个比较详细的问题吧，就是r=3跟c=2
去比较一下不同的数值的选择会对这个搜索它的效率
带来有什么的影响？我不知道大家如果尝试过之后会不会留意到一些
比较特别的结果呢？
我们发现呢，这个我们也可以在minizinc里面呢
我们也可以声明一个我们所谓是注解的参数，
我们就是利用这个ann来证明我们这个var_select就是一个
注解的参数，这个search也是一个注解的参数，然后呢我们
就可以赋值first_fail给这个var_select这个参数，然后呢
也赋值这个int_search这个搜索的策略，则是利用刚才这个
var_select来做这个选择这个变量，然后利用这个indomain_radom- 来选择它的数值。
来赋值给这个search这个注解的参数，然后呢我们
可以利用这个search这个注解呢来建议给这个求解器，我们希望
利用first_fail跟这个indomin_radom呢来作为我们的搜索的这- 个策略。
这个就有了这个注解的参数呢，我们要改我们的
搜索的策略呢是非常容易的，因为我们就可以把这个
注解的参数，它的赋值改一改，我们就可以用一个新的 搜索的策略来解决我们这个问题。
好啦，我们利用最简单的， input_order跟indomain_min都已经可以把我们原来这个
埋藏的药方这个问题呢解决了，这个就是我们这100种常药
它的属性应该是什么样才可以满足我们刚才提到的三种不同的条件。
就是这个其中一个解。
其实呢我们刚开始 介绍这个搜索，其实呢还有更多的高级的搜索的方法
我们还没有介绍包括这个顺序的组合，还有一些 比较动态的变量选择的策略包括这个
dom_w_deg， impact research，activity
research，还有一个非常重要的就是我们叫Restarts，就是重启式的 搜索。
还有呢从不同的方法去探索我们的搜索树呢
包括这个有限的偏离的搜索啊，广度优先呢 最佳优先呢，还有更有呢这个搜索的组合子。
我们在未来呢会把其中一部分呢 高级的搜索的方法呢会给大家去介绍
好了，我们可以来一个总结，就是我们这个约束编程这个
求解的方法呢其实就是交替的进行下面这个步骤，
第一个步骤呢就是对一个变量做一个猜测，就是猜一个数值
给这个变量做一个决策，然后呢就利用我们学到过的这个传播呢
推理这个基数，把这个约束全部拆除，这个呢全部的目的就是为了把
变量里面的值域，一定是肯定没有可能不会出现在
解里面的数值呢把它们移除，这个呢出来的结果呢就是把
可以把我们搜索的范围呢大大的减少，啊，而且如果我们
利用这样子的方法来解决我们的约束求解问题的话，我们最重要其中一个一个一个基数呢就是
要控制我们这个搜索的一个过程，在MinZinc里面呢我们要控制我们这个
搜索的过程呢就是可以利用这个搜索的注解，就是帮助我们这个用户呢可以告诉我们的求解器
我们觉得要解决这个问题有什么好的
搜索的策略是可以用，可以更方便更高效的 帮它去解决这个问题的。
我们要控制这个搜索呢
通常我们要选择的就是哪一个变量来搜索，而且我们也可以选择呢就是怎么样去限制
怎么利用我们的约束，我们的成果器去限制这个 变量，这个就是约束变成求解器
这个最主要的部分了。
[空白_录音] [空白_录音]
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
