六、全局约束中的Alldifferent和Cumulative的实现

1、Alldifferent的内部实现

1.1 防御怪物问题

\qquad 假设有$N$个村庄和$K$支军队，且满足$K\ge N$，每支军队都与某些村庄相邻且能够保护他们；一直军队在任一时刻只能保护一个村庄；随机选择一个村庄被袭击，随机选择一个相邻的军队来保护这个村庄，如何调整军队中的职责分配，来保证其他所有村庄在被同时攻击时得到保护？

\qquad 一个全局约束实现出来之后就是一个全局的传播器，一个好的全局约束应该具备传播强度大，快速传播的特点。通常来说，全局约束传播器都不是幂等的，即调用一遍之后，之后再进行调用时仍可以将变量的数量进行减少。

1.2 Alldifferent 值域传播器

\qquad 抽象出一个Alldifferent值域传播的例子如下图所示：

\qquad 希望通过Alldifferent值域传播器得到如下结果：

• 第一步，贪心匹配
  \qquad 从一个给定的部分匹配开始，选择一个未匹配的变量，直到没有替代方案可以选择为止。
  
• 第二步，搜索一条交替路径
  \qquad 从未匹配的变量出发，寻找一条未被匹配的边，之后再寻找一条匹配的边，令未被匹配的边和匹配的边交替出现，最终到达一个未匹配的数值，则找到一个最大匹配。
  
  \qquad 如上图所示，交替路径为$Y\to 3\to Z\to 2\to T\to 5$，最终令未匹配的变量$Y$达到匹配状态。
• 第三步，边定向
  \qquad 对于匹配的边，从变量到数值；对于未匹配的边，从数值到变量。
  
• 第四步，修剪
  \qquad 保留能够从未匹配数值节点到达的边(粉色+绿色的边)
  \qquad 保留在强连通分量(SCC)中的边(蓝色的边)
  \qquad 保留已经处于最大匹配中的边(黑色的实线边)
  \qquad 删除剩余的边(虚线边)
  
  \qquad 最终得到的结果如下所示：
  
  \qquad Alldifferent全局传播器的时间复杂度为$O(n^{2.5})$，基于最大匹配，值域改变事件发生时被调用。

2、Cumulative的内部实现

\qquad 给定$N$个部队，每个部队都有各自的宽度和穿过城门持续的时间如下所示：

\qquad 要求限时30min所有部队均进入城镇；不同部队可以同时穿越城门，但是宽度不能超过城门的宽度限制；骑兵需要在物资马车之前进入城镇。问题是对于一个不对，什么时候应该待命给出更好的预估，使得步兵知道他们何时可以休息？（任务调度问题）
\qquad cumulative传播器的数学抽象表达为：

\qquad 即有$n$个任务需要进行调度，每一个任务有起始时间$S_i$和持续时间$D_i$，且每个任务执行时需要$R_i$个单元的某个资源。这个资源在任意时刻最多有$L$个单元可以使用。当前没有一个实现最强的边界或者值域传播器。这个任务调度问题可以转化为一个二维装箱问题进行处理，如下所示：

\qquad cumulative基于时间表的传播器的运作流程：首先需要确定一个任务必须在运行的部分；之后需要在资源负荷里面增加这些部分；最后利用已知的负荷来调整其他的任务；如下一个示例：

\qquad 一个任务的必要部分指的是任务最早完成时间和最晚开始时间之间的时间差值，如下所示：

\qquad 负荷指的是所有任务必要部分的累和。


\qquad cumulative除了基于时间表的传播器的传播器，还可以设计基于分解的传播器，如下所示，但是基于分解的传播器的时间复杂度要高很多：

THE END