优化是决策的一般形式，在我们的社会中很常见。它的应用包括从求解数独谜题到婚礼上的座次安排。同样的技术可以调度航班和机组成员，协调钢铁生产，组织铁矿从矿井到港口的运输。人力资源和材料管理上好的决策可以令企业提升上百万的盈利。同样的问题很多也在我们日常生活出现，成为决定每天送货路线，决定学校时间表，传输电力到家里等种种问题的一部分。除了它们的重要性，这些问题如果用传统的本科计算机科学方法难以求解。 这门课程为已经完成离散优化高阶篇的同学设计。 请看这门课程的宣传视频：http://www.cpr.cuhk.edu.hk/cutv/detail/988
3.1.4 传播引擎
Loading...
En provenance du cours de The Chinese University of Hong Kong
离散优化算法篇 Solving Algorithms for Discrete Optimization
notes
À partir de la leçon
基础约束编程
这个模块开始时用例子说明约束编程求解器的基础技术，也就是约束传播和搜索。值域代表了变量可能的取值，而约束可用于在值域上进行推理。约束本身可以以值域传播器和边界传播器的形式表示。你将会学习到一个传播引擎如何处理一组传播器，并通过变量值域协调沟通约束传播得到的信息。你也将会学到基础搜索，变量，数值选择等概念，还有传播和搜索是如何紧密而高效地连接起来的。最后，这个模块介绍了如何在Minizinc中进行编程化搜索。
Rencontrer les enseignants
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
天空平稳如初，但
人间的灾难未平，世人仍活在疾病肆虐之下。
有一神农氏四处奔走救治病人，女娲便劝诸葛亮随同 神农氏到各处医治。
两人路经一处村庄，发觉此处的孩童受到诅咒， 时常患病。
天有二十八星宿， 而孩童按双星宿而生，各个星宿可有多个卦象附带。
孩童健康与星宿卦象相关。
男童双星卦象需符合大吉之咒，而女童双星卦象不可相同。
太阴运行时会将某个孩童的某个星宿的卦象随意固定。
若另一星宿有一卦象与此卦象相和，孩童则安然无恙。
否则将陷于疾病。
神农氏希望用法力 消去星宿的部分卦象，令孩童免受疾病所害。
诸葛亮召唤时空飞龙求助。
>> 诸葛亮跟神农去到一个 被诅咒的村庄。
他们发现呢在这个村庄里面的小孩呢 很多时候就会这个无缘无故就生病了起来了。
原来他们发现在这个村庄里面的小孩他们出生的时候 都会有两个不同的星宿。
这个星宿呢分为这个主的星宿跟这个副的星宿。
在天上面呢我们总共有二十八个星宿。
在这个村庄里面就是有 29 个男孩跟这个 9 个女孩。
他们星宿，他们出生之后他们星宿的环境就是用这个 线来代表了。
黑色的线呢是给男生的，红色的线呢就是给女生的。
如果你们还记得呢，我们还有这个八卦这个概念。
而且呢 八卦里面是有八个卦象的。
这个八卦跟这个星宿有什么关系呢？ 原来我们发现呢，原来每一个星宿呢它们是
会受到某一些的八卦的卦象去影响的。
我们 这里呢就举了好几个例子。
譬如说这个星宿呢就给这个 水呀、 地呀跟山呢是会影响它的。
然后这个就是我们二十八个星宿分别
它们会受到哪些八卦的卦象影响呢的一个表。
那这个又有什么的关系呢？ 原来呢，这个八卦的卦象跟怎么去
影响这个星宿呢，是直接可以影响一个小孩呢 到底他是不是健康的，或者要生病的。
在这个 旁边这个表呢，我们就列出了这个每个小孩。
这个每个男孩他的主星宿跟这个副星宿
如果是受到不同的这个卦象影响的情况之下，
如果在这个表里面呢，这个男孩呢他就会健康。
如果不在这个表里面呢，这个男孩呢就会生病的。
譬如说，我们看看这个男孩 他的主星宿呢现在是受这个水影响，他的副星宿呢是受这个风影响的。
这个水跟风的组合呢刚好就在这个表里面，所以呢这个男生就是 会健康了。
相反呢，如果当他的主 星宿是受这个天，他的副星宿是给这个地
影响的话，那因为这两个这个组合呢 不在这个表里面，所以呢这个男孩呢就可以生病了。
给女生呢，这个情况比较简单一点。
她们主要就是希望呢 要求就是她们的主星宿跟她们的副星宿呢是要不等、 不相等。
如果它是相等的话，这个女孩呢你看见她就生病了。
如果她是不相等 的话，这个女孩呢就健康了。
好了，我们理解了这个星宿 受了什么的卦象影响，怎么去影响
这个小孩的健康，那为什么还是有一些小孩会生病呢？ 原来这个村庄是给诅咒了。
所以呢这个月亮呢每一天晚上
就会选其中一个小孩，譬如说今天晚上他们选的这个男生。
明天呢有可能他们选的这个女生，再后一天呢有可能他们选另外一个男生。
好了，选了一个小孩之后呢就会发生什么事情呢？他们
就会随意，这个月亮会随意锁定
有可能是他的主星宿，有可能是锁定他的副的星宿。
锁定其中一个卦象
就是说这个卦象呢就现在就是影响这个星宿了，所以在这个 例子里面呢，这个小孩他的主星宿今天晚上就给
锁定，受了这个水这个卦象去影响。
好了，现在要做的事情就是要看看他另外一个没有给
锁定的星宿，看看呢它有可能的卦象里面有没有一些卦象呢
是可以跟这个锁定的卦象呢是可以配合的。
那刚好呢，在这个例子里面我们发现呢 水原来呢是可以起码跟
其他三个卦象呢是可以配合的、 兼容的。
所以呢，因为我们可以找到卦象跟这个水去 配合，所以呢这个小孩呢就可以是健康了。
如果、 如果假设呢，锁定的是另外一个卦象
在这个例子里面也是他的主星宿，锁定是这个卦象。
我们发现呢，根据这个表呢，无论我们在他的副星宿里面选取
任何其他哪一个的卦象呢，也没有办法呢是满足这个表里面 这个健康这个条件的。
所以呢，如果我们找不到 这样子的卦象的话，这个小孩呢就会生病了。
幸好我们的神农呢它是有法术的，它是可以帮这个 这样子的小孩呢去治病。
他治病的方法呢就是把这个小孩的主
星宿跟这个副星宿里面一些，一定不可行的一些 卦象要把它移除。
这样子呢这个小孩呢就不会再生病了。
好了， 我们就看看这个被诅咒的这个村庄的这个问题。
我们给定的就是每一个
在这个村庄里面的小孩生来呢就带有一个主的星宿 和一个副的星宿。
而且呢每一个不同的星宿呢都有一些可能附带着的 八卦的卦象。
我们希望当然呢就是任何一天都没有生病的孩子。
怎么可以没有生病的孩子呢，就是不管哪一天月亮选中
哪一个小孩，不管这个月亮选中这个小孩之后锁定哪一个星宿，
也不管选中这个小孩的星宿上面附带着 锁着哪一个八卦的卦象来影响这个星宿。
我们都应该希望呢，可以在这个小孩的另外一个星宿呢找到另外一个卦象
是可以满足这个小孩呢一个不生病，或者是健康的 这个兼容的一个卦象出来。
这样子呢我们才可以 保证每一天都没有生病的孩子。
那我们怎么才可以解决这个问题呢？ 我们先来看一个比较笨一点的方法。
因为这个方法 比较笨一点呢，所以呢我们要这个做的例子呢比较 简化一点。
我们假设我们这个村庄里面呢只有三个小孩。
在这里呢三个都是男生来的。
因为他们都是有可能有病，所以他们都需要排队。
去看这个神农，希望神农呢可以帮助他们把这个不可能的
星宿里面不可能的卦象呢把它们移除。
好了，我们先看看这个第一个小孩。
这个第一个小孩呢他的主星宿跟这个副 星宿还有它们相关的、 有可能的卦象呢都已经列了出来了。
我们利用一条线把两个可以连到这个小孩健康的 卦象呢把它连起来。
我们可以看到呢，这两个的卦象呢是没有连到
另外一个星宿的卦象的，这个就是代表呢如果我们选
了这个卦象的话，我们就根本就没有可能在这个星宿里面，有可能的卦象里面
找到一个可以令到这个小孩健康的卦象呢，所以呢这一类的
卦象是不好的，所以我们需要把它们移除。
好了，移除了之后呢，当然呢这个孩子呢就应该可以病好了，就应该不会
生病了，因为无论我们这个月亮锁定的这个主圣兽也好，锁定的这个副圣兽也好
选择锁定的其中一个的卦象我们都可以在对面的圣兽
里面呢找到一个兼容的一个卦象，令到这个小孩是健康的。
好了，看完第一个小孩之后，我们当然就要看另外一个小孩。
另外一个小孩呢，我们也是把他的两个圣兽，而且他们圣兽
有可能的卦象也是列出来，我们也可以看见呢
这个小孩这个副圣兽里面，这个水这个卦象跟这个山这个卦象呢，是没有
这个线把它们，跟其它连起来的。
所以它们呢就是不可以留在这个圣兽
的卦象，可能的卦象里面，所以呢神农呢就需要把这两个卦象呢都移除。
好了，医好了，治好这个小孩之后呢，神农就要去 治疗另外一个小孩。
我们发现这个新的小孩呢 里面它们很多圣兽，它们之间都没有连起来的，因为这一类的卦象呢
都是不好的，所以呢我们都需要把这所有没有线连的卦象都移除。
做好这个之后呢，当然呢神农也把第三个小孩呢也治好了，但是他是否已经把
所有的小孩都治好呢？不是，因为呢你可以看见这一批的小孩呢他们之间
是有共享一些圣兽的，也因为我治疗一个小孩的时候呢会有可能影响我们更早
治疗的小孩，所以呢，因为有这个卦象
要给我移除，所以呢神农要重新给所有的小孩 也再看病了，所以要重新看第一个小孩。
发现呢，发现里面还有 这个卦象是不行的，所以要把它移除。
然后看第二个小孩， 也发现有卦象不行的，所以把它移除。
然后呢看第三个小孩 发现，这个小孩里面已经没有卦象，是不可行的，所以就可以
做完了，把他治好了。
但是因为刚才第一个小孩跟第二个小孩也是有
这个卦象给移除，所以呢神农又要又需要重新为所有的小孩再看病了。
一个小孩，我们发现呢，所有的卦象都有跟另外一个圣兽的卦象
有连起来，所以呢，这个小孩就不需要治疗了，已经是可以健康的。
另外一个小孩也是，出来结果也是一样，所以他也 不需要治疗。
第三个小孩情况也是一样。
好了，刚过去呢这个三个小孩呢都不需要治疗，他们都是健康的，所以呢神农就
已经把这个村庄里面的三个小孩呢都治好，他们都是可以变成健康的小孩了。
好了，这个我们刚才提到的比较笨的一个方法呢，就是要神农不断
不断地把这个村庄里面所有的小孩都一一去给他们治病。
如果其中，有其中一个小孩是有病的，要把这个
里面的卦象要把它移除的话
神农就要把所有其他的小孩都要看一遍，所以呢我们就说这个方法呢 有一点点地笨。
那我们下面呢看一看 到底我们有没有一个比较好的方法可以处理这个问题。
好了，我们就希望可以提供一个更好的思路。
这个新的思路呢就是 我们呢要维持一条队列，这个队列里面所
有的小孩呢都是有可能没被这个治愈的小孩来的。
就是说在这个列队里面的小孩呢都是有机会生病的，我们不
知道他们是不是健康的小孩，他们是有机会生病的。
好了，我们呢因为 有一个更好的思路，所以我们现在看这个例子呢是可以
人数比较多一点，分别呢我们有两个女生 跟这个六个男生。
好了，我们先看看第一个女生吧。
把这个女生提出来，她的主圣兽跟她的副圣兽列出来。
而且也看到她的所有的卦象，而且呢因为一个
女生呢她什么这个才可以健康呢，就是需要她的两个圣兽的卦象不相等， 她们就可以健康了。
所以你们可以看见呢她们之间两个圣兽的卦象 都有很多线把它连起来的，所以呢这个女生基本上是健康的。
好了，因为是这样子的话她没有生病呢，所以我们就可以把这个女生呢移除，
不需要在这个队列里面，所以我们就需要把这个女生呢放到 我们的旁边，然后我们去看另外一个女生。
看见这个另外这个女生呢，她也是健康的，没有这个卦象需要给移除，所以呢我们也需要- 把她放在 一旁。
好了，到了一个男生，男生呢要健康就比较困难一点，我们也看见呢这个男生呢
这个卦象跟这个卦象呢是没有线连起来的， 所以呢我们就要把它移除。
好了，移除之后呢，我们就把他治好了。
治好之后但是他有可能还是有病的，所以呢我们需要把这个男生呢放在这个队列的后面。
然后呢，我们就再看下一个男生。
下一个男生呢我们发现呢他是
所有的卦象都是可以的，都是跟对面的圣兽的卦象有联系的。
所以呢，因为他是健康的，所以呢我们就可以把这个男生呢也放在旁边。
好了，到了另外一个男生呢，我们发觉他有这个卦象是需要给移除的。
而且呢，这个男生呢，这个圣兽呢跟刚才这个女生的圣兽呢
是有相同一个圣兽，也因为这个圣兽里面的卦象 有给移除，所以呢，现在这个女生呢有机会
有机会是可以生病的，所以呢我们就需要把这个女生呢也放回我们这个队列
里面，而且刚才治好这个男生呢，也需要放到这个队列的最后的地方。
然后我们就再看新的一个小孩，这个新的小孩呢因为
是基本上是健康的，所以我们也可以把他放在一旁。
新的另外一个小孩，这个新的小孩呢有一个圣兽里面的卦象我们需要移除的。
也因为这个卦象呢，这个圣兽呢是跟这两个小孩呢的圣兽呢
有共同的圣兽，所以这两个小孩呢也需要回到 这个队列里面，而且刚刚治好的也应该放在这个队列的尾巴。
好了，到了另外一个小孩呢，我们因为又移除了很多
的卦象，所以呢，也需要把他放在我们的队列的最后。
好了，然后另外一个小孩也有移除了，而且呢他这个圣兽
也是跟这个小孩有共同用的，所以呢这个小孩跟原来这个小孩呢也 应该放在这个队列的最后。
如此类推，我们呢就是 一个一个小孩去看，一个小孩如果刚治好呢，要把他放在后面。
如果另外一个小孩治好要放在后面， 反正就是如果需要把这个卦象移除呢，我们就要把
把他放在后面，有东西要移除，要放在后面再排队，
有东西移除，也放在后面要排队，直到有一个小孩呢没有需要移除
卦象的，我们就可以把他放在一旁。
另外一个小孩有东西 移除的，所以就 可以放在一旁。
而且呢这个 也是可以放在一旁，因为没有东西需要给这个移除。
到了最后，因为刚才这个呢有 东西要移除，而且呢他们也有共同的这个
圣兽，所以呢这个又回到我们的队列了。
我们慢慢根据刚才的方法呢，也是一步一步去做，到了最后呢
经过了二十六步之后呢，我们就可以保证在我们旁边这个队列
这里面的小孩呢，他们基本上都是健康的，就是无论
我们选择锁定哪一个圣兽，锁定里面哪一个的卦象，我们就都可以在
另外一个圣兽的卦象里面选到一个呢，令到这个小孩健康的一个卦象出来。
我们这个 更好的方法呢，总共用了 26 步，这个还是不错的。
好了，其实呢我们刚才讲这个故事里面的问题呢，
跟我们学习的材料呢也是有一点关系的。
不知道大家有没有留意其实呢 在我们这个问题里面呢，就是有很多不同的圣兽，这个圣兽呢基本上呢就是
一个变量来的，因为这个圣兽受在每一天受哪一个的
卦象去影响呢，就是我们要做决策的东西。
所以呢，对每一个圣兽来讲呢，这个圣兽有可能的卦象呢
就是这个这个变量的值域的数值。
这个这个也是代表了每一个变量它的可能的数值，可以取的数值。
在我们的问题里面呢其实呢我们也
也有一个条件就是定义，到底一个男生他是不是可以健康的
他的所谓是健康呢就需要影响他的主圣兽跟影响他的副圣兽的卦象
之间呢要兼容，兼容的定义呢就是在这个表格里面，所以基本上呢这个是一个 健康的一个约束。
但是到了现在呢，大家也应该是理解 所谓一个约束呢，也是用来帮助我们设计一个 传播器的。
所以呢我们在这个 问题里面呢有一种的传播器是给这个 男生的。
当然呢对女生来讲呢也有她的约束跟她的 传播器就是不等于，不等这个，这个这个约束。
好了，这个神农为了这个小孩去治病，是怎么
治病呢？他要保证呢，就是无论这个小孩的哪一个圣兽给锁定，哪，锁定到哪一个
无论哪一个卦象也好，它也可以保证呢，在另外一个圣兽呢
都可以找到一个卦象呢是可以满足这个健康这个条件的。
啊，这个，为这个小孩治病这个过程呢，其实呢神农呢
是在做的事情就是我们之前看过的值域的传播。
所以我们的希望的结果就是希望任何一天都没有
孩子会生病的，其实呢我们的相对我们学过的东西呢
就是希望保证呢，在我们问题里面，每一条的约束，它都它们都可以保持到 值域的相容。
好了，其实呢 我们就可以把我们刚才的故事重新定义一下。
我们给我们给定的包括有一个 变量的集合，我们叫每一个变量都是
Xi 每一个变量 Xi 呢都有相对应的一个值域
D(Xi) 当然呢在这个问题里面因为我们也有约束，所以呢，每一个约束呢
就是，就有一个，有一个传播器了，所以在这个问题里面给定的
都有一个，就有一个变量的集合，每一个集合
变量呢都有一个值域，而且呢我们也有一个传播器的集合。
这个传播器我们是用来干嘛呢？是为了把我们值域里面
一些不可能的数值呢，把它们移除的，所以呢我们要计算呢就是
为了每一个变量的值域呢，要计算一个最大的子集。
然后呢，计算到出这个最大的
子集呢，要使得它要满足一个非常重要的条件，这这个新的条件呢就是什么呢？
就是无论我们怎么再调用我们这个问题里面的
传播器，调用到我们这个
新的值域里面的时候也不会再这个把这个 值域呢变化了。
就是说 D' 是等于 f(D')，这个就是我们要
达到的目标，就是我们这个传播器已经 把这个值域里面所有估可能的
数值呢基于我们的约束就把它们都已经移除了。
我们 无论在去调用任何一个传播器呢都不会
再有可能在这个值域里面再移除任何的一个数值。
这个就是我们希望达到的一个目标。
好了，下面呢其实我就，我们就是希望把刚才
我们这个比较好的思路，把它的算法好好地描述出来。
我们呢刚才其实呢调用
的一个算法呢，我们叫它作作为这个传播的引擎。
在这个传播的引擎里面呢，就是我们有一个集合的传播器。
我们希望呢把这个问，问题里面的不同的
传播器一直地把它们调用，希望达到一个状态。
这个状态就是什么呢？就是无论我们调用我们这个问题里面
任何一个传播器，我们把它调用到我们的值域上面，都不会把我们值域 去改变的。
如果我们所有的，如果一个传播器达到这个条件就是 f(D)
= D 的话，我们就说我们这个传播器呢相对于这个值域来讲
就达到一个不动点了，就达到一个不动点了。
所以我们这个 传播引擎的这个算法呢就是希望把所有的
传播器相对于我们的值域来讲都已经达到这个不动点了。
我们就叫我们这个算法呢叫 isolv。
呐这个 isolv 呢有 3 个参数的，这 3 个参数是什么来的？首先我们就假设
我们的所有的传播器里面呢我们分开为两批，一批我们放在这个 F0
里面，另外一批呢我们就放在 Fn 里面。
我们放在 F0 里面的传播器呢 那就是我们假设它已经达到这个不动点了，就是说放在这个
F0 里面的传播器呢 我把它调用到这个 D 的时候呢，返回的还是
D 来的，就是你调用它也没有 用的，没有东西可以移除的。
另外其余的传播器呢，有机会可以 不是在这个不动点呢，我们就把它放到这个
Fn 这个集合里面，而这个 D 就是我们这个问题里面的 值域。
好了，在这个算法里面首先我们就把 F
呢用来放 我们所有的传播器，就是 F0 跟 Fn 的 并集。
另外呢我们有一个非常有趣的一个 队列，我们叫
Q，这个 Q 呢就是我们刚才这个算法里面用来
放所有有机会，有机会会生病的小孩的。
就是，在这里呢就是 我我，我们呢要放的就是有机会这个传播器呢是不满足
这个不动点这个条件的，我们呢就把它放到这个 Q 这个队列里面。
所以开始的时候，就是所有在 Fn 里面的传播器呢，我们都把它放到这个 Q 里面。
然后我们这个算法就非常简单了，就只是有一个 while 的循环。
这个 while 的循环呢 我们什么时候停止呢？就是直到呢我们
这个 Q 这个队列呢，里面已经再没有传播器在里面。
好了，我们进去这个循环里面看看怎么做吧。
在这个 循环里面第一步呢就是在这个 Q 这个队列里面，我们拿一个传播器出来。
拿一个传播，随便拿一个也可以。
然后呢，我们就拿了 出来之后，我们就要把这个传播器呢，调用到我们的
相对我们问题里面的值域，来算一个新的值域出来。
做好这一点之后呢，我们就基于刚才我们这个值域呢 到底有没有改变，我们就有用一个叫
new 的函数呢 就要把一些在原来这个 f
里面的传播器 如果经过这个传播器的的调用之后，有机会变成
不满足这个不动点的传播器 都要把它重新放回这个 Q 这个队列里面。
然后呢我们这个循环就继续做，做到
我们这个队列呢再没有一些传播器呢是有可能 不满足这个不动点这个这个条件的。
好了，你可以看见呢在这个 算法里面呢有两个非常重要的这个函数。
第一个函数呢就是 choose。
这个 choose 就是在这个队列里面选一个传播器出来。
另外就是 new 这个这个函数，这个 new 这个函数呢就是基于刚才这个
传播器的调用，我们要把一些其它的传播器，看看它们有没有
有没有机会有可能变成呢不满足这个不动点的，我们都需要把它
加进这个 Q 这个队列里面。
我们 要再记住这个 Q 这个队列呢就是给我们放一些有机会
不满足这个不动点这个条件的传播器来的。
好了，我们怎么去实现、 设计这个 choose
跟 new 这两个函数呢？一般来说呢，这个 choose 是非常简单的。
这个 choose 其实呢我们通常都是会 是一个限进项、
限出的一个队列，就是说 每一趟呢我们就把这个
Q 这个队列里面已经放的时间最长的一个传播器
把它拿出来了就可以了，但是最重要的一点就是这个 Q
呢虽然 说它是个队列，其实呢我们真要把它实现的时候
它应该是一个不但是个队列也是一个集合来的。
我们就是 不允许在这个 Q 这个队列里面呢有一些传播器是给重复添加的。
好了，另外呢我们就看看这个 new 这个这个 函数。
这个 new 这个函数就是根据我们刚才 刚调用的传播器。
f 就是所有的、 其他的传播器，而且呢就是原来的 集域。
调用了 f，小 f 这个传播器的集域，
之后新的集域，根据这几个参数呢来决定到底有什么的
其他的传播器有机会变成呢不满足这个、 这个
f'（D'）不等于 D' 这个、 这个条件的。
其实呢我们要实现这个 new 呢，有一个、 一个比较普通的一个版本。
这个版本 其实是非常简单，就是基于我们看看我们新的 值域。
如果我们发现某一个变量它的新的值域呢跟它原来的值域 在调用的这个
f 这传播器之后，如果有 不一样的话，而我们发现有另外的传播器呢，它里面呢
是有一个已经改变了值域的变量在这个传播器里面，那我们就要 把这个、
这一类的传播器呢收集起来，然后呢把它加入这个 Q 这个队列里面。
好了，我们再看清楚这个定义。
我们就是 要求呢这个 new 这个函数呢就是把所有的
如果这个传播器它里面的变量
这个变量呢它的新的、 新的值域跟
旧的、 原来的值域是不相等的话，那我们就需要把这个
传播器收集起来，然后把它呢就放到这个 Q 这个队列里面。
那我们这个、 这个投影片它的题目是"哪里可能会出错呢？"
所谓是出错不代表是我们的算法有错误。
我们这里问哪里 可能会出错呢，就是到底有什么地方如果我们根据这样子去定义
我们这个 new 这个函数有什么地方呢效率是不太好呢？原来我们发现呢
如果就算一个传播器它里面的
变量的值域改变了，也不代表它一定呢 需要再被调用的。
因为呢很多时候就算一个 传播器它的变量的值域给改变了，我们再调用它
出来的结果呢还是不会改变这个值域，不会把这个值域里面一些的数值呢 去砍掉的。
所以呢，我们大多数的时候呢，传播器 我们把它重新唤醒放到这个
Q 里面，我们出来的 结果呢都是没有造成这个值域的
新的改变，所以呢我们好像浪费了 这个传播器的调用了。
所以我们下面要讨论的就是我们 可不可以把这一点做的更好呢？就是为了这个 new
这个 函数把它优化一点呢？
在下面呢，我们先要介绍几个不同的概念。
第一个概念呢我们叫幂等的。
我们说一个传播器它是幂等的是什么意思呢？
就是这个传播器呢无论我调用它一趟跟我调用它两趟 或者三趟、
四趟，出来的结果呢是跟调用它一趟呢是一模一样的。
我们如果我们的传播器有这样子的一个特性呢，我们就叫这个传播器呢 是个幂等的传播器。
为什么 幂等的传播器那么重要呢？因为一个幂等的传播器呢
给调用之后，我们就不需要马上就把它放回这个 Q 这个队列里面。
如果你们还记得呢，我们之前呢如果根据这个 new
的定义呢就是 我们调用了一个传播器，然后呢因为这个传播器当然呢就把一些
值域改变了，变量的值域改变了。
那当然这个传播器 根据我们刚才这个 new
的这个定义呢，也是需要返回这个 Q 这个队列里面的。
但是如果 如果我们知道这个传播器是幂等的，我们就不需要这样子做了。
因为 一个幂等的传播器呢给调用之后呢，它就应该
再调用的话就应该完全没有这个效果了。
实际上呢，但是我们要小心，就是呢
因为很多的变量的值域呢中间都存在这个空洞的。
有空洞的话，我们会发现呢它的传播器呢很多时候 都不是幂等的。
我们就可以看看下面这个例子，我们在这个例子里面呢就是我们 已经很熟悉的一个约束就是 X = ▏Y▕。
譬如它的值域呢 D(X)={0,2,4} 值。
D(Y)={-3,1}。
如果我们把我们之前用过一个简单的版本的， 传播去来调用到这个、
这个约束跟它的 变量的值域上面的时候，我们发现呢调用了一趟，我们
就有算到了新的值域就是 {0,2} 跟 {-3,1}，但是原来我们
如果再、 再调用一趟，我们发现呢我们是可以把这个变量的值域
再改变的，就是因为在这个有 有空洞的情况之下呢，我们这个
X=|Y| 的这传播器呢
这个边界的传播器呢是、 不是幂等的。
好像刚才给的一个非常悲观的，觉得这所有的传播器
都不是幂等的，但是呢我们之前学过的，值域的传播器它是幂等的。
就算是最强的边界的传播器也是幂等的。
但是呢，我们要保证呢这个变量的值域里面是没有空洞的。
在这个情况之下呢，最强的边界传播器呢也是幂等的。
又或者呢，很多时候在一个求解器里面呢 我们也可以利用一个所谓是动态的幂等。
这是什么意思呢？每一个传播器呢，我们调用了 之后，它也应该是返回它出来的结果。
有了这个新的 这个值域之后，这个传播器还是不是
幂等的？这个传播器应该把它的是不是幂等的这个结果返回出来。
那我们这个传播引擎呢知道之后就可以决定
到底应不应该把这个传播器呢要放回这个 Q 这个队列里面。
好了，我们看过这个 幂等的这个概念之后呢，我们来看另外一个概念，所谓是调用事件。
所谓是调用事件呢就是 有很多时候呢一个值域的改变
就算我这个传播器里面有一个 变量它的值域是有了改变，不代表、
不代表这个传播器 把它去调用，它可以引致新的值域的改变的。
很多时候只有在特定的事件的情况之下， 才会发生的。
在一般的求解器里面呢， 我们会定义四种不同的调用的
事件，包括 fix(X) 就是当这个 X 这个变量 给固定了。
lbc(X) 就是 X 这个 变量它的下界给改变了。
ubc(X) 呢就是 X 的上界给改变了。
dmc(X) 呢就是 X 这个值域里面有改变了。
我们就要求呢，对某一些的传播器，我们会要求呢有特定的调用
事件发生的时候，我们才会把这个传播器呢重新加进我们 Q
这个 队列里面的，所以我们现在给你们一个问题， X≠Y这个约束，它的传播器你觉得
它应该基于什么的调用事件它才有机会变成这个
有机会再可以去改变别的变量的值域呢？
你们大家可以去想一想，其实呢在X≠Y
这个情况之下呢，我们通常就是需要呢，就是其中一个变量
它的值域呢，其中一个变量给固定了。
其中一个变量给固定了，我们才把它唤醒，把它
重新放到这个Q这个队列里面的，因为只有在这个情况之下 我们在调用这个X≠Y呢才可以引发新的
对这个值域的改变的。
好了，再看看另外一个概念，就是 已解决的传播器，有时候呢我们可以判断
对某一个传播器呢，到了一个地步，对于
所有未来的值域D，不论这个D是什么来的，这个传播器f呢，
它是都是满足这个f（D）＝D这个条件的，那就非常 好了，这是说我们就算在调用这个传播器呢，
它一定我们是可以保证它一定不会对我们的值域再带来任何的改变，
这样子的情况，通常在什么的情况之下发生呢？就是其中一个最常见的
情况就是当这个传播器呢，已经给解决了，就是说我们这个约束呢
里面的所有的解呢，都是我们值域里面所有的解。
我们可以给你们一个例子，就是刚才提到过这个X≠Y这个传播器，
如果当其中一个variable，其中一个变量它的值域已经是
给固定了，我们利用它的传播器呢，我们就可以 从把它另外一个变量它的值域里面把
这个变量它固定的值把它移除，移除了之后其实呢我们已经解决了
这个X≠Y这个传播器，这个之后呢我们永远不再
需要把这个X≠Y这个传播器呢，再放到这个Q这个队列里面了。
好了，基于我们刚才讲过的好几个
概念呢，我们就知道我们怎么可以优化我们这个传播的引擎了。
我们可以优化的地方包括下面这4点，第一点呢就是
我们呢对于所有非等的传播器，如果它的
值域里面都是包含
多于一个元素的话，那如果我们有这样子的非等的传播器呢？
我们都应该把它放到这个F0这个传播器的集合 里面，因为我们都知道呢这样子的话这个非等的传播器呢
无论我们怎么调用它们，如果它的值域里面都有多于一个元素的话，
根本它一定没有可能对这个值域呢进行任何的 引发任何的改变的。
这个是第1点，第2点呢， 就是当其中某个值域变成
单元素的值域的时候，那我们才会把一个非等的传播器
重新把它唤醒，把它放到Q这个队列里面。
这个其实刚才已经讨论过了，不然的话 这个非等的传播器呢，就算我们把它调用，根本就
不会引发任何对这个值域的改变的。
好了 另外一点呢就是，如果我们的调用的传播器是一个值域的传播器的话，它给
调用之后，我们呢不需要就把它
放到这个Q这个队列的后面，我们可以把它放在一旁，因为呢一个
值域的传播器，我们知道它是幂等的，所以
把它连续的调用2趟呢，是不会引发新的这个值域的改变的。
好了，最后呢一个呢就是说，对一个已经解决的
约束，它的传播器呢应该永久的 给移除，什么时候一个约束
会被解决呢？对于一个非等的约束的话，如果它给
传播过1趟，刚才已经讲过了。
它什么时候会被传播就是其中一个 变量它是已经有一个固定的值，然后呢我就应该在另外的一个
变量它的值域里面把这个值呢移除。
那经过这个调用呢，这个非等的约束呢
就已经被解决了，所以呢它就永远不再需要放到我们Q这个 队列里面了。
另外一个可能呢，如果不是非等的约束呢，就是当一个约束
当它最后的值域里面，每一个值域呢都只是包含一个值的，
就是一个单元素的值，就说它2个变量呢都已经给固定了。
所以这个约束呢 已经是给解决了，所以呢我们也可以永远不再需要把这个
约束呢重新再放到我们Q这个队列里面。
我们做了这个优化之后呢，我们就可以
更有效率的把我们这个问题里面所有的传播器呢，达到这个f（D）＝D这个状态了。
我们就看看怎么做了。
我们在开始的时候我们还是有这个Q，这个Q呢
里面的传播器呢都是有可能
可以产生这个，对这个变量的值域产生变化的。
然后呢我们在旁边呢也放了一个地方就是
用来放一些已经给解决了的传播器，我们永远不再需要
去调用它们的，另外呢在旁边的这个传播器呢就是
我们开始的F0就是呢我们知道 这个是非等的传播器，而且呢它们的
值域也不是单元素的，所以我们知道要调用它们也是没有用的，不会 引发任何的值域的改变。
所以呢我们就看看利用我们优化了的引擎 可以怎么把所有的传播器呢都变成这个
达到这个f（D）＝D这个状态。
好了，我们先看第1个 小孩，第一个小孩我们发现有2个的卦象要移除。
但是呢，这个是有一个值域的传播器，所以呢移除了之后它就
不再，它是幂等的，所以呢我们就可以把它放在一旁；第2个
小孩呢发现没有东西要移除，所以呢也是可以把它放在一旁；第3个
有东西要移除，所以呢也是把它放在一旁； 第4个没有东西要移除，所以也是把它放在一旁。
但是呢在最新的 一个呢因为我们有一个东西要移除，而且呢这个传播器呢跟我们一个
旁边的传播器呢有共享的变量，所以呢我要把这个
传播器呢也重新放到这个Q这个队列上面。
然后如此类推，看看另外一个小孩有东西要
移除，而且呢这个新的这个约束呢
跟这个好多的传播器呢都有关系，因为它们都有共享的
变量，所以呢我们要把4条的传播器呢都 放到这个Q这个队列里面。
然后 我们再看，然后这个新这个也因为有这个
有东西要移除，所以有东西呢要移回这个Q上面，再来看新的一个也有东西
要移除，也跟它有共享的变量， 所以呢，要把它移除。
但是呢刚才没有提到， 因为我们调用了2个不等，非等这个的
传播器，而且呢调用了之后我们知道它已经
被解决了，而且也有一个男生它给调用之后呢，它的
变量的值域呢只有单元素，它所以 也是给解决了，所以呢我们都应该把它们都放到旁边
这个旁边呢，我们就永远不会再调用它们了。
好了，这个呢我们也有移除一些卦象
也有移除一些卦象，在有移除一些卦象，但是呢，这个移除了卦象之后呢，因为有这个
有共用的这个变量，所以有把
这个传播器呢放回这个Q这个队列里面，我们一步一步在做呢
我们可以慢慢来看，在18步就可以把这个村庄里面的所有的
小孩呢，都治好了。
刚才我们是用的26步，现在 用18步呢就可以完成了。
那当然你可以说18步比这个26步 也不是有效率得太多，但是
这个只是一个非常小的一个例子，在我们 一般呢一个求解器里面我们有几十、
几百 几千条这个传播器，我们把这个
传播引擎的效率提高了，其实对我们求解的过程呢的效率是提高很多了
好啦，这个就是我们原来的每一个不同的星宿，它们
有可能影响它们的卦象，根据我们刚才利用了我们的传播的引擎
调用过我们的传播器之后呢，我们就可以把里面的很多的不同的
卦象，一些不可行的卦象，都把它移除，这个的就是我们新的
这个星宿，它们新的值域，是什么来啦
好了，我们可以来一个总结 其实我们在这节课里面提到最重要的就是这个
传播的引擎，这个传播的引擎它是做什么呢？其实是重复地在做
一件事情，就是调用在这个问题里面不同的传播器
直到呢，不停不停地调用，直到呢，这些传播器呢，已经不
可以把问题里面变量的值域呢，再有发生任何的改变
到了这个情况之下呢，我们就说，这个问题里面所有的传播器都达到了不动点了
我们也应该知道呢，这个
传播引擎的效率是非常重要的，所谓是效率呢，就是我们应该尽量
要把一些如果我们觉得绝对没有可能可以引发这个值域改变的传播器呢
我们就不应该把它放到我们的队列里面，不应该把它们调用
我们当中提出了几个概念，譬如说，如果一个传播器
它相对的相应的一个约束已经给，已经被 解决了，所以呢，我们就永远不应该再调用这一类的传播器
而且呢，对某一些的传播器来讲，应该是在某一些事件发生了之后
我们才应该重新把它唤醒，把它再放到我们的
Q这个队列里面的，我们刚才已经给过一个例子，就是这个
非等这个传播器呢，它们应该是其中一个变量，它的值域
改变成这个氮元素，在这个事件之情况之下，我们才把它唤醒的
我们在设计这个传播引擎这个算法的时候呢
我们其中一个最重要的关键就是我们要知道，大多数 的时候，当一个传播器我们给它调用的时候，其实
它是不会引发任何对值域的改变的，所以呢我们就要非常
非常的小心，要决定什么时候才要把一个传播器
唤醒，把它放到我们一个有可能引发值域改变的这个
队列里面。
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2019 Coursera Inc. Tous droits réservés.
