优化问题是一种常见的决策问题，它在我们的社会中很常见。它的应用可以从数独问题的解决涵盖到婚礼的座次安排。同样的技术可以用于航班与机组成员的安排，钢铁生产的调节，和钢铁从矿区到港口的调度问题。在生产中，人力资源与生产材料的合理决策可以使企业获得成千上万的利润提升。类似的问题也存在于我们的日常生活中，它们包括决定包裹的运输路径，调整学校课程时间，和传输能源到千家万户。尽管这些问题很基础，不过以一般本科教育的知识来解决这些问题都会十分困难。 这个课程是设计给已完成离散优化建模基础篇的同学。你将学习到更多关于如何使用先进的高级建模语言表述清楚具有挑战性的离散优化问题，并让约束求解器完成其余工作。本课程将重点介绍模型调试与改良，如何把一个复杂的约束定义封装到一个谓词里面，及如何着手各种复杂的项目调度和打包问题。当你掌握这种先进的技术，你将能够解决以前难以想象的问题。
2.5.1 对称与LexLeader
Loading...
来自 The Chinese University of Hong Kong 的课程
离散优化建模高阶篇 Advanced Modeling for Discrete Optimization
3 个评分
从本节课中
对称与支配
在最后的单元中，我们将会探讨在离散优化问题中不同类型的对称。你将会学到如何用不同的方法和特殊的约束来打破这种对称性从而提升解决的效率。你也将会学到支配的概念，一种更广义上的对称，还有打破支配的技巧。你的学习目标有：1. 在问题的陈述中发现对称性; 2. 通过增加适当的打破对称性的约束来更改具有对称性的MiniZinc的模型; 3. 总结模型中存在的不同类型的对称; 4. 通过发现支配来提升模型。
与讲师见面
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
曹军与孙刘联军在赤壁对峙，决战一触即发
战前，曹操派出夏侯惇，偷袭刘备根据地夏口
诸葛亮早已预料到曹军的偷袭 就提前计划，在通往夏口的必经之路上布下连弩陷阱
埋伏，诸葛亮所用的连弩设计精巧
可同时向八个方向射出暗箭攻击，设置陷阱时
多个连弩将布置在方阵中，若放置不当，连弩射出暗箭时将互相破坏
使之威力大减 故放置时，需确保彼此不会互相击中
为防曹军识破连弩陷阱 诸葛亮认为应采用至少 4
种不同的布置方法 因此，诸葛亮取出神算法板求解
>> 诸葛亮他发明这个新的暗器
它叫"八方连弩"，这个连弩呢是非常厉害的一个暗器
如果你把它放在一个地方呢，它就可以同时间向八个不同的方向
射出这个暗箭，这个呢就是这个连弩可以覆盖的范围
如果我们把这个连弩放在这个地方的话 这个红色的地方就是它覆盖的范围。
如果在覆盖的范围里面 有这个敌人存在的话，我们这个连弩呢就可以把他杀掉了
最厉害的地方就是，如果同时间有多于一个敌人
都在这个连弩的覆盖的范围里面，这个连弩呢就可以同时都把他们杀掉 这个就是它最厉害的地方。
但是呢，要把这个连弩呢放置在 安全的地方呢，我们要小心一点
譬如说，这样子呢就不可以，因为如果它们成为一个直线的话
它们呢就会这个互相的攻击，互相的破坏 所以呢这个是不被允许的一个放置的方法
好了，这个呢，这个安排也是不可以的，我们可以
看见呢，有四个的连弩呢，它们都会互相的攻击，互相的破坏
我们看看这个下面，如果我们要放 5
个连弩的话，我们这个图 里面呢，就是个正确的放置的方法了，因为呢
我们看看，中间这个连弩，其余的连弩都不在 它的覆盖的范围里面。
看看这一个 另外四个连弩呢也都不在它覆盖的范围里面
再看另外一个连弩，看它的覆盖的范围，也没有破坏到另外任何的一个连弩
同样的，这个也是，最后这个也是，所以呢
我们这个放置的方法呢，这 5 个连弩呢，它们都不会破坏对方
这个呢就是我们所谓正确的一个放置方法 现在呢，我们的问题是要放
7 个连弩，然后需要它们不会 这个互相的攻击，而且呢诸葛亮也准备把
这个连弩阵放在这个战场上面四个不同的地方
所以呢他希望在这四个地方呢，放置 的方法呢也是不一样的，不然呢，如果这个曹操的军队
看见了一个连弩阵之后，他就会知道另外的 阵，它们的设计是什么样，就可以避开它的攻击了
好了，这个就是我们问题
一个文字的描述，我们就是需要在一个 n x
n 的战场上面，在我们的问题里面，n 就为 7，放置
n 个不同的八方连弩，我们也需要呢
这个连弩呢，虽然它们可以同时向八个不同的方向
射这个暗箭，我们是需要呢，它们不可以互相的攻击的，而且呢，我们希望有 4
种不同的放置的方法，这样子呢，曹操就没有办法
看过一个之后就可以理解另外的放置的方法，从而呢可以避过这个连弩的攻击了
好了，我们就看看我们这个问题，这个模型。
首先 我们有一个数据，这是为 n，然后也有一个范围 1
到 n，就是定义我们这个战场呢 它的大小，而且也是我们需要放置这个连弩的数量。
然后呢 变量方面，我们就一个二维的数组，这个二维的数组呢就是
代表在这个 n x n 的网格上面，每一个位置
到底我们有还是没有放置一个连弩呢 然后我们也要求呢，在整个网格上面
所有位置放了连弩的地方，它的总数应该为 n，就是说呢，我们在上面是放了 n
个连弩在里面的 然后呢，我们也要求要满足这个问题
好了，到了条件方面，也比较简单，我们有
三个不同的条件，就是在同一行上面，在同一个列上面，我们都不可以有两个
连弩在上面，这个要求呢，在同一个
对角线上面，也有同样的要求，这个是很容易的
在同一行上面，我们把所有放了连弩的地方，它的数量加起来 我们要求呢，它是小于等于 1。
在同一个列上面，也要相同的要求 但是呢，对角线呢，我们有两条，一个是这样子，另外是这样子的，在两个不同
的对角线上面，我们也要求呢，把放置连弩的地方，它的数量加起来 要求它们是小于等于
1，另外一条对角线呢，我们也相同的要求 好了，我们有一个简单的模型，然后就
求解，这个呢就是我们拿出来 4 个不同的解了
所以，好像我们已经满足了诸葛亮的 要求。
但是呢，如果我们看清楚的话，我们
第四个跟第一个的解呢，好像如果把我们的头移动一下
它们就变成同一个解，第二跟第三个解 也是有相同的问题。
所以，如果曹操 看见了第一个连弩是利用这个安置的方法的话，他就
很容易可以理解第四个解，它的这个连弩阵的一个 设计了。
所以呢，这个就不满足我们需要 四个解都是互不相同的一个解的这个要求
如果我们要明白问题出在哪里
我们首先要去理解一个新的概念，我们叫它几何对称 首先我们假设，我们这个连弩
陷阱问题有两个解，A 跟 B，如果我们可以从 B
这个解 通过这个旋转或者是翻转呢，可以得到 A 这个解的话
我们就叫 A 这个解呢是 B 这个解的几何对称解
我们也明白这个旋转跟翻转可以反过来做的，所以我们也可以讲 B
这个解也是 A 这个解的几何对称解。
其实，对于一个 正方形的网格的分布来讲呢，我们一共
应该有 7 个不同的几何对称的。
我们首先利用一个 比较小型的一个问题，四连弩这个问题来讲一讲
这 7 个不同的几何对称是怎么来的。
这个呢就是一个四连弩问题的一个解 原来我们发觉呢，通过右转
90 度 180 度，或者是呢 270 度呢，我们都可以得到另外
一个解，因为呢，这个旋转呢，是不会对我们刚才讲过的 条件呢有任何的违反的。
其实，我们也可以通过对 y 轴，或者是
x 轴，然后来一个翻转，我们其实也可以
得到另外一个解，我们做翻转呢，其实也可以相对于两条不同的对角线
做这个翻转呢，效果也是一样。
你们可能觉得，其实呢通过这个
旋转或者是翻转呢，我们得到的都是同一个解来的，只有这个呢是跟我们 原来的解是不同的。
这个原因就是因为我们现在这个问题的大小太小了 如果我们拿一个比较大型的问题来看这
7 个不同的对称的话，我们得到的解呢很可能是不同的
其实，刚才提到这个几何对称 是一种我们叫变量对称，我们下面呢
就给大家介绍一下这个变量对称的一个严谨的定义 我们叫一个叫
g 的双射的函数 如果它满足了下面的条件之后，我们就叫它是一个变量对称
这个条件是什么呢？假如我们有一个赋值，这个赋值呢就是 X1= V1,
...,Xn=Vn，假如它是一个解的话 那如果我们把
g 这个函数呢，应用到这个 赋值上面的变量它的下标，然后我们得到另外一个赋值就是
Xg(1)=V1,...,Xg(n)=Vn，假如这个
赋值呢也是一个解，而且相反呢，如果这个是一个解呢
原本这个赋值呢也是一个解的话，我们就叫这个 g 这个函数是一个变量对称的
我们刚才这个连弩陷阱的问题里面 其实呢里面提过的几何对称，就是把
我们的这个网格呢要做旋转或者是翻转
其实呢，也可以把它们看为呢把我们的解当中的
变量的值互换，所以呢我们刚才看见的几何对称也是这个变量对称
好了，现在我们明白 了这个几何对称，所以呢我们现在知道
原来我们刚才拿到的 4 个解，我们把第 1 个跟第 2 个解
都把它向右转这个 90 度呢，我们就可以拿到
第 4 个跟第 3 个 解了，所以呢我们后两个解呢 跟前两个解呢基本上是一样的
但是我们也应该明白呢，我们再看看第 1 个解跟第 2 个解，无论我们怎么做这个
旋转或者是翻转，我们都不可以从第 1 个解到了第 2
个 解或者是相反过来的，所以呢，这两个方案都是不一样的
好了，通过刚才的一个例子，我们可以理解 如果两个解，它们是互相对方的对称解的话
它们其实是属于同一类的解来的，所以呢，我们就可以定义一个新的概念叫对称类了
假设我们的问题里面有一组的解，而且在这一组的解里面它们可以
互相通过这个对称的变换，而互相得到对方的话
那我们就说这一组的解呢，它们是属于同一个对称类的
我们来看看之前看过这个四连弩的问题，这个四连弩的问题呢
非常简单，因为呢它只有两个解，而且呢我们也知道呢，它这两个解第 2
个 解呢可以通过一个非常简单的转换就可以从第
1 个解里面得出来了 所以呢我们就说这两个解呢，都是属于同一个对称类的
而且呢因为这个四连弩的问题只有两个解，所以呢它只有一个对称类
那我们现在要理解到原来在同一个
对称类里面的解呢，它们都很类似的，所以对于诸葛亮来讲呢
他也希望从每一个对称类呢只需要找一个解就够了 好了，我们来看看这个四连弩这个两个解
这两个解呢虽然它们都是一个二维的数组，其实呢我们可以把这个二维
的数组呢，把它拉平变成个一维的数组，而且呢我们利用 0 来代表 不放这个连弩，
1 来代表我们放了一个连弩在这个地方，所以呢我们就可以看见
这个一维的数组呢 0010 1000
0001 0100 呢就代表了我们其中一个解了。
利用相似的方法我们也可以把 第 2 个解呢也拉平，变成一个一维的数组，而且呢我们也
发觉这两个数组呢，原来我们可以
把它们做比较的，做什么的比较呢？我们就利用这个字典序来比较它
们，我们发现呢，原来左边这个解呢，是基于这个字典序而言呢
比右边这个解呢是更小的。
好了，所以，如果我们可以 在我们的模型里面加入一个约束来保证我们找出来的解呢
肯定是比它的利用这个它
其它的对称解都是根据这个字典序而言是最小的话 我们就可以把这个对称移除了。
这个移除对称的方法我们叫它 LexLeader ，这个
LexLeader 的方法就是要求在我们的问题里面对于每一个解
这个数组呢就是我们求出来的解。
这个呢就是 应用了这个 g 这个对称之后得出来的对称解，我们要求呢
我们求出来的解呢一定相对于这个对称解，一定要基于这个
字典序的话而言呢是更小或者是等于的
好了，我们来看看我们之前看过一个其中一个对称，就是向右 旋转 90
度，这个呢就是我们一个七连弩的一个解 然后通过向右旋转的话，我们就得到
右面这个解，然后我们就要求呢，这两个解之间呢就要满足
我们这个字典序的这个小于等于这个关系。
你们可能说，诶 这个两个解都是一个二维的数组，我们怎么利用这个
字典序来比较它们呢？其实我们可以 把两个解呢，从二维拉平变为一个一维。
拉平的方法呢我们可以基于 横向然后一行一行
来把它拉平，也可以基于这个纵向 一个列一个列一个列，然后把它拉平
在我们的模型里面，我们就可以利用
下面这一条的约束呢，来保证我们这个 向右转 90 度这个对称呢移除了。
我们怎么样做呢？我们就利用这个 let in
来再定义一个新的二维数组，它的大小呢跟我们原来的变量数组是一样的 都是
N 行跟 N 列的，然后呢 在这里呢我们就要利用一个 forall，其实呢来做这个
对变量的数组的下标做这个对称的计算，其实得出来的就是 s 这个数组呢
里面的值呢就是应该是我们原来 的变量
t 这个二维数组的一个向右转 90
度 的这个对称版本了，然后我们再要求呢它们是要
满足这个字典序一个小于等于这个 条件的。
好了，其实呢，我们这里呢是用到这个 lex_lesseq 这个全局约束的。
我们之前呢其实也见过这个 lex_greater
这个全局约束，它们都是属于同一类的 全局约束来的。
刚才看见就是对这个向右转 90
度的这个对称 我们对于其它的对称呢也添加类似的这个约束来保证
它们都是满足这个字典序，那我们就可以把我们问题里面所有的对称都移除了
好了，当我们在这个模型里面加入了 7
条移除对称的约束之后 我们再要求
MiniZinc 把我们的问题求解 我们得到的新的
4 个解呢，我们可以 看清楚它们互相都是不对称的
因为呢，因为我们求出来每一个解我们已经保证它们都不属于同一个对称类当中
好了，刚才我们就看见我们怎么利用这个 lex_lesseq
来帮助我们 来做这个 LexLeader 方法来移除这个对称
其实呢，MiniZinc 里面我们也有一个 约束库，是用来处理我们常见的这个对称的
其实我们刚才这个问题也可以利用这个 var_sqr_sym
这个全局约束呢来帮助我们把 它的参数，它的参数就是一个二维的正方形的一个变量数组
把里面的所有的几何对称都可以把它移除。
我们刚才呢 看见就是每一个对称我们都需要一条的约束，但是我们利用
这个全局约束呢，我们一条的约束呢就可以把所有的对称都移除了
其实如果你们还记得的话，我们从前呢曾经
讨论过怎么利用一个整数的数组呢来表示一个固定势的集合
譬如说如果我们这个固定势的集合里面有三个元素 的话，我们就可以利用一个三个元素的一个整数数组
变量数组来代表它，里面每一个元素那就代表这个集合里面的每一个元素了
但是当然我们也明白，因为它是一个集合，所以我们也要求呢
这个数组里面的每一个元素呢它们都是互相不相同的
有了这个表示的方法之后，我们也遇到一个问题，就是原来呢
用这个表示方法我们有同一个集合呢都有可能有多重的表示
这个就是一个例子了，{1,6,10}这个集合其实根据上面这个的表示方法呢我们有
原来有六个不同的表示方法的，所以呢我们呢为了要解决这个
问题呢，我们上一趟就提出其实我们可以利用
要求这个数组里面的元素呢都要排一个序
从小到大，那我们就可以解决这个 多重表示这个问题。
其实这个多重表示问题呢 就是一个对称的问题，而且呢这个
我们这个排序的方案来解决这个方法其实也是基于我们刚才提到这个lexleader这-
个方法的 其实要解决这个问题，我们还有另外一个方案，我们就是不应该利用这个数组
的方法来表示一个固定势的集合，其实我们用一个集合的变量 会更好。
我们的意思就是可以定义一个集合的变量，然后加入一个
约束来限制这个集合呢它的势为3 这个就可以了，我们这个重新描述问题的
方案的好处呢就是在这个新的模型里面 我们就再没有对称这个问题了，因为在一个
集合里面，它的 元素它的顺序根本就没有关系了
好了，我们来一个小结。
其实呢 对称是一个经常出现在离散优化问题当中，而且呢
也是它们把这个问题的求解的过程变得更困难了 为了要避免这个对称这个问题呢，所以我们就应该
加入一些移除对称的约束了 我们在这一课里面看见的一个对称呢，我们叫它为
变量对称是非常常见的，我们也介绍了一个叫LexLeader的方案
来帮助我们移除这个变量对称 而且呢，我们也介绍了在MiniZinc里面原来有一个约束库呢
专门是用来解决一些常见的对称的，所以呢
如果有可能的话，我们就应该利用在这个库里面的全局约束
我们刚才提到这个连弩这个 问题呢其实就是我们一个非常有名的一个叫
n皇后的问题的一个版本，这个n皇后的问题就是在一个
n乘以n的这个正方形网格当中，我们要放
n个皇后在里面，而且呢我们不允许这个皇后呢她们是可以互相
攻击对方的，其实这个n皇后的问题已经给很多人充分地研究过了
我们还有一点要提出，就是我们为一个问题建模的时候 其实我们也应该有不同的方案，我们要知道
有一些方案呢是有这个对称的问题 但是其他的方案就没有这个对称这个问题的，如果我们的求解器
是支持这个集合变量的话，我们就可以考虑 利用这个集合变量，因为用了集合变量呢，我们就没有了
这个变量的可换性这个问题在里面，所以就没有了这个变量对称这个问题了
[空白_录音] [空白_录音]
