曹操率军南下，准备与孙刘联军交战 曹操手握大军，而孙刘联军相比之下则显得势单力薄 但曹操大军来自北方，不熟水性 士兵坐船驶至东吴途中，在风浪中颠簸，深感不适 诸葛亮与周瑜商议派庞统前往曹营 建议曹操以铁索连接各战船，可使船只平稳 实则借此联通各船，供孙刘联军火攻，一并全灭 庞统前往曹营说服曹操 曹操早闻庞统学富五车，便采纳建议 令庞统设计如何以铁锁匠将领所住的楼船连接。 庞统建议一个连接方案 曹操不满当中船只分布疏落 便令庞统想出更为紧密的连接方法 庞统一筹莫展，于是秘密回到孙刘联军，向诸葛亮求助 诸葛亮就取出神算法版 >> 曹操对庞统还是没有太信任，所以呢 暂时只是要求他帮忙去解决这个楼船打包这个问题 所谓的楼船呢，其实就是给一些将军呢 他的家人呢，他的随从啊，住的地方 但是呢，曹操的大军大部分人呢都是从北方来的 所以呢，他们根本就不习惯在船上面的风浪 庞统呢，也是利用这一点 去说服这个曹操，应该把所有的楼船呢，都连起来 而且呢，船跟船之间，应该尽量地靠近 这个这样子呢，就可以加强这个船块它的稳定性 好了，我们可以看见呢，曹操呢，所有的楼船呢，都是正方形的 而且呢，不同的大小的楼船呢，它有不同的数量 所以呢这个问题呢，是个典型的正方形打包问题 好了，对庞统来说，每一条船 就是一个正方形，所以呢，他就利用 手动去找出一个方案，给这个曹操看 我们看这个图比较容易明白，因为这个图上面我们可以看清楚每一个正方形它的大小 曹操看了之后，他不太满意，他说 为什么在里面还是有那么多的空间 而且呢，占用的面积呢是太大 所以呢，曹操就要求 这个打包的问题是需要把这个 楼船块占用的面积呢，要最小化的 这个就是我们这个打包问题的一个数学的描述 首先，我们有不同大小的正方形 而且呢，每一个大小的正方形呢，我们都有它的 数量，k1 就是大小为 1 的正方形的数量 k2 就是大小为 2 的正方形的数量，kn 就是 大小为 n 的正方形的数量。 我们的要求非常简单，就是要把这个正方形 都打包到一个最小的矩形的区域里面 好了，我们看看这个问题的 模型，首先当然就是我们的数据 首先我们要定义呢，我们有多少 不同边长的正方形 然后呢，这个定义一个范围，利用这个范围呢，我们就定义一个数组了 这个数组里面每一个元素呢，就是某一个大小的正方形 它的有多少个，这个我们就 ncopy 然后呢，我们也定义两个参数，分别呢就是我们 打包出来这个矩形的最长的可能长度 这个最长的可能长度呢，就基本上可以我们把所有的 正方形，它的边长加起来，我们的意思就是说，把所有的正方形 一列地排出来，这个最长的可能性，这个就是我们的 maxl 我们也定义一个叫 mina，就是我们最小的 area，就是呢，最小的面积，最小的 可能性的面积呢，其实就是我们把我们所有的正方形 它的面积，加起来了，就是我们这个 求出来这个矩形的最小的面积的可能性了 利用这个 maxl 跟这个 mina 呢，我们就可以定义我们的变量 首先，我们有一个变量叫 height，就是高度 跟 width，就是宽度，这个就是我们打包出来这个矩形的高度跟它的宽度 它们的可能范围呢，就是从 n 到这个 maxl 为什么最小的可能性是 n 呢？因为我们起码要把一个最大的正方形呢 放进这个矩形里面，最大的可能性当然呢就是我们刚才算出来的 maxl 了。 同样地，我们的宽度它的范围也是一样 然后呢，我们就要定义一个面积了 area，这个面积呢，其实就是高度乘以这个宽度 我们也给它定义一个范围，它的范围基本上就是最小可能的面积 到了我们最大的可能性就是，我们把所有的正方形呢，都是 一列过的排出来，所以它的面积就是 n 乘以最长的可能性 有了这三个变量之后，我们还要 定义一个辅助的数据 我们叫 nsq，这个 nsq 呢，基本 上就是我们所有的正方形 加起来的数目。 有了这个 nsq 之后呢，我们定义一个范围，利用它来定义 两个变量的数组，这两个变量的数组呢，就是分别代表我们每一个正方形 它最后在这个矩形里面，它们的 x 跟 y 它的坐标 好了，我们也希望大家留意，我们在上面 定义我们的变量的时候，为它们定义的范围呢，我们是 很小心，尽量把它们范围的界限呢 要定得越紧凑是越好的 好了，我们来看一个简化版本的问题 就是假设呢，我们这个问题里面，每一个大小的正方形只有一个 如果我们有四个不同大小的正方形的话，如果 我们要把它们打包，而且呢，要求这个最后的面积是最小的话 这个就是其中一个可能的解，我们最后呢需要的面积呢，是 35 好了，我们要想 关于这个问题里面的约束之前呢，首先我们还要定义另外一个 我们的辅助变量，我们称它为 size 这个 size 呢是个数组来的，每一个元素呢，就是代表我们所有的 正方形，每一个正方形它的大小为多少，我们首先看看下面这个例子 如果你们还记得呢，我们有一个数组叫 ncopy 就是代表了每一个不同大小的正方形它的数量 所以在这个数据里面呢，我们看见，如果大小为 1 的正方形我们有三个 大小为 2 的我们有两个，大小为 3 的我们有五个 大小为 4 的我们有四个，大小为 5 的我们有三个 我们就希望定出来的 size 这个数组呢，基本上就是原来我们有 三个正方形，它们的大小为 1，所以我们第一个、 第二个、 第三个正方形它们的大小为 1 然后我们有两个正方形呢，它们大小是为 2 跟着的三个，五个正方形呢它们的大小为 3 跟着的四个正方形它们大小为 4，最后呢，这三个正方形呢它们的大小为 5 所以你们现在可以明白我们对这个 size 这个数组的要求是怎么来的 我们要把这个数组算出来呢，很简单 我们可以利用我们之前已经看过几趟的 global_cardinality 这个全局约束 我们就要求呢，在这个 size 这个数组里面 出现不同正方形大小的 数量为我们原来数据里面给我们的 ncopy 这个数组 所以呢，我们就需要里面 1 是出现 三趟的，2 是出现两趟的，3 是出现四趟的 五趟的，4 是出现四趟的，5 是出现三趟的，但是呢 这个还不足够，因为我们还是需要要求呢，这个 size 这个数组呢 它们的值，不同的元素的值呢是递增的 好了，有了 size 这个数组之后，我们要表达我们 这个问题里面的两个条件呢，就非常容易。 第一，我们要求呢，我们所有的正方形 都应该在我们打包出来 这个矩形当中，所以很简单 x 跟 y 呢，就是我们正方形它左下角的 这个坐标，我们要求呢，x 坐标 加上呢它的长度，还是在它我们这个矩形的 宽度之内。 同样的，我们也要求 y 这个坐标加上呢这个 正方形它的大小，还是在我们这个矩形的高度之内 这个就是正方形都在矩形当中 而且呢，当然呢，我们也需要要求呢，我们所有的正方形呢，互相不重叠 好了，怎么表达这个约束呢？我们首先就看看我们 所有的正方形里面随意拿两个不同的出来 我们呢，其实两个正方形不重叠呢，有四个可能性都可以满足这个条件 就是第一个呢，可能性就是，我第一个正方形 s1 是在 s2 它的左手边的 而且呢，它加上了它的 x 的坐标，加上了它的大小之后 还是小于我们 s2 这个正方形它 x 的坐标，就是 第一个可能性。 第二个可能性呢就是我们 s2 这个正方形呢，是在 s1 这个正方形的左手边 换句话说，就是 s1 呢是在 s2 的右手边，我们也是要求 s2 它的 x 的坐标加上它的大小之后，还是小于等于 s1 它的 x 的坐标的 对于 y 的坐标，它的要求呢，也是差不多，所以我就不讲了 然后这个问题的目标非常简单，就是我们 要对要求呢这个矩形的面积呢要最小化 好了，我们有了这个模型之后，我们来做一个 为了一个小的实例来求解。 我们这个小的实例里面，只有三种不同的正方形 三种不同的大小。 第一个大小为 1 的 正方形我们有五个，大小为 2 的我们有三个，大小为 3 的我们有两个 然后呢，我们这个模型很快就可以把这个解求了出来，我们总共有十个正方形 我们可以看看呢，我们得到的是一个完美的打包。 因为在这个打包 里面呢，是完全没有浪费的空间的 而且呢，我们需要的总面积呢也是 35 好了，我们就来看看，如果我们采用 曹操的数据又怎么样呢？曹操呢，最大的 楼船，它的大小是 7，所以我们定义 n 是 7 然后呢，我们这个 n copy 的数组呢就代表不同大小的楼船它的数目 我们可以看见呢，原来这个曹操呢，是没有大小为 3 的楼船的，所以呢，这个地方是个 0 所以呢，曹操的楼船总共有六个不同的大小 我们把这个数据放进这个模型里面去跑呢 我们发觉，六秒钟之后，我们得到一个解 它的面积呢是 520。 过了一分钟之后呢 我们有了一个小一点的面积 再过了几分钟，我们有了更小的面积，但是呢，如果我们继续地跑 就算是到了一个小时呢，MiniZinc还没有可能，没可以给我们一个更好的答案 但是呢，它同时也不可以去证明这个最新的解呢就是一个最优的解 所以呢，我们就看看我们可以怎么改良我们的模型了 其实我们提出来改良的方案，我们之前呢都看过了 当然，第一个就是我可以利用这个全局约束，这个是最好用的一个方案 另外呢，就是冗余的约束 还有呢，我们发现在这个问题里面呢，也有 对称的问题呢，所以我们应该呢，把这个对称移除 在我们的问题里面，最重要的一个条件 就是所有的正方形，它们要互相不重叠 在 MiniZinc 里面，diffn 这个全局约束就是为了解决这个问题来设计的 如果我们有一系列的矩形的 形状在二维当中，diffn 这个全局约束呢就保证 这一些的矩形呢，都互不重叠 其实因为 diffn 呢是 为了二维的问题来设计的，所以其实我们觉得它应该叫做 diff2 我们来看看 diffn 的语法。 它有四个参数 第一跟第二个参数呢，就是分别 我们一系列的矩形的它的 x 跟 y 的坐标 第三跟第四个参数呢，就是我们一系列的 矩形，它们的宽度跟它们的长度 有了这个 diffn 之后，我们在模型里面要表达 这个正方形互不重叠呢，就不需要我们之前看见的 一个基于析取式的一个约束，我们只 需要一条的 diffn 的全局约束呢，就可以表示 同一个条件了。 好了 我们也可以利用另外一个全局约束 cumulative，我们之前呢也看见它多过一趟了 我们应该明白到了，如果一个问题 是满足了打包的要求呢，其实 这个问题也一定是满足了 cumulative 这个约束的要求的 但是呢，相反呢，是不对的 我们在下面才给大家去说明这个问题 所以呢，在我们的模型里面，我们就可以添加一些 冗余的 cumulative 的约束到我们这个打包的问题里面 加了这个冗余的约束呢，其实是可以帮助我们提高约束的传播 当然呢，就可以把我们求解的速度提高很多了 所以呢，我们需要为这个 x 这个维度跟 y 这个维度也加进一个 cumulative 这个全局约束 也要求它在两个维度呢，都互相不重叠 好了，我们再来看清楚，看清楚为什么呢 cumulative 这个 全局约束，就算是满足了 也不代表我们可以满足了打包的要求 我们看看我们有 七个不同的方块，如果我们把它当为 这个方块的打包的问题的话，我们发觉呢，我们没有可能把这七个 方块呢，都放进一个矩形里面的 因为我们可以看见，第六个方块呢，它有一个部分是凸了出来 但是如果我们把这个第六个 方块推了进来，我们发现第三个方块呢，也凸了出来 但是如果我们把这些方块当为是一个 任务，对它的高度是代表这个任务呢，对一个 资源的要求的话，然后，然后 我们要求它满足这个 cumulative 这个约束呢，这个是可以的 因为呢，其实我们也知道，一个任务其实不是真的是一个 方块来的，我们只是需要在每一个不同的时间要求所有任务 对这个资源的要求是低于这个资源的限度就可以了 好了，对称 我们发觉呢，在这个问题里面，我们有每一个 正方形的大小呢，都有，有几个副本的 所以呢，其实但是我们发觉呢 同一个大小，不同的副本，其实呢它们是可以互换的 有了这个对称的问题呢，所以我们的模型呢，就导致这个解的多重性了 我们怎么可以解决这个问题呢？其实呢我们可以把 相同的大小的正方形在它的位置上面 添加一个顺序，然后呢，我们就可以解决这个对称的问题了 但是一个正方形的位置呢，其实是个坐标来的 它是一个，一个对，一对的 数字，x 跟 y，我们可以采用什么样的顺序呢？ 原来其实我们可以采用严格的字典顺序 我们给你们 两个坐标，(x1,y1) 跟 (x2,y2) 我们说，(x1,y1) 跟 (x2,y2) 呢，是满足了 严格的字典序，(x1,y1) 是大于 (x2,y2) 的 我们就是，它的意思呢就是 x1 比 x2 要大，或者呢 当这个 x1=x2 的时候，我们就要求 y1 比 y2 要大 在 MiniZinc 里面，当然我们也有一个全局约束，叫 lex_greater 这个全局约束呢，就是针对两个 n 元组 然后我们强制一个严格的字典序 我们把两个不同的 n 元组呢，把它利用 这个数组来表示，就可以放进这个 lex_greater 里面了 它的意思就是第一个 n 元组比第二个 n 元组 呢，为大，大的是基于这个严格的字典序 有了这个之后呢，我们就可以 把我们问题里面相同大小的正方形，给它们排一个顺序了 但是做这个之前呢，我们首先要定义一个新的数组 我们叫 base，这个 base 它的定义呢，是基于一个推导式来定义的 这个推导式呢， 它的下标是基于 这个不同的正方形的大小。 当这个正方形的大小 唯一的时候，这个 base 的元素呢为 0 当这个正方形的大小为 i 的时候 而且这个 i 是大于 1 呢，我们就是 把所有正方形的大小是小于 i 的 正方形的数目加起来，就变成这个 base i 这个元素它的值了 其实这个 base 这个数组呢 就是每一种边长的正方形，它在我们 所有正方形这个变量数组里面的开始的下标 有了这个之后，我们就可以要求每一种正方形的大小 然后再看看相同正方形 大小它们不同的副本，要求呢如果它们是连续的话 它们就要满足这个 lex_greater 这个关系了 好了，我们加进了我们刚才讲过的改进之后 我们现在就在三十秒之内就可以把这个问题呢 解决了。 我们可以看到，这个就是 怎么把不同大小的楼船打包起来 如果我们看这个图，应该比较容易明白，因为在上面呢 我们也把楼船的大小，也这个表示出来 这个也是一个完美的一个打包，因为在中间呢，是没有浪费的空间的 其实我们的模型还有一个地方可以改良 就是这个 size 这个数组的定义。 我们呢 之前是把它定义为一个变量数组来的，然后呢，再利用这个 global_cardinality 还有一个顺序的要求，就可以把这个 size 这个数组呢计算出来了 但是如果我们想清楚的话，我们已经 知道我们有数据告诉我们，每一个不同大小的 正方形呢，它的数量是多少的，所以呢，其实我们可以直接 就把这个 size 这个数组呢 就可以计算出来了。 所以在新的定义里面 我们可以把 size 定义为一个普通的 参数的数组，而且呢，我们不需要利用约束来给它做这个计算 我们就可以利用下面这一条的表达式，就可以把 size 呢，计算出来了 但是这个表达式用的什么技巧呢，我就留给你们慢慢去 去看明白了。 我们来一个小结 我们面对是一个方块的打包问题 这是一个在现实世界当中 CP 一个 非常常见的一个应用。 其实这个问题呢，有很多不同的变体 而且呢是一个比较复杂的组合优化问题 我们知道呢，利用这个 diffn 这个全局约束呢 我们可以把我们问题里面要求我们的正方体 互不重叠这个要求呢，可以保证 diffn 是表示一个二维的互不重叠 其实如果你们还记得的话，我们在面对这个 调度问题的时候，我们也利用到一个全局约束，叫 disjunctive 其实 disjunctive 呢，是表示一个一维的互不重叠的关系 我们也知道呢，利用这个 cumulative 这个约束呢 我们可以帮助这个打包问题呢，提高它求解的 效率，因为呢，在一个打包问题里面，cumulative 这个约束呢，是个冗余的约束 [空白_录音] [空白_录音]
