除了士兵逃跑 刘备、 关羽和张飞还苦于马匹短缺的问题
于是他们向富商张世平借用马匹 张世平希望自己的良马能助有能之士
平定暴乱,就向三兄弟出题,并承诺若能解答,就应许相助
张世平要求刘备使用不多于四种颜色,为汉室地图上色,而相邻的州
不可用相同的颜色。
军队急需马匹 但三人面对难题,苦思冥想都不得其解
这时,刘备便取出神算法版,尝试求解
>> 我们之前讲过招兵的问题
现在到了买马了。
当然 一个好的军队也需要好的战马的 所以呢,我们的英雄呢,就到了富商
张世平要求他帮忙了 张世平基本上是
愿意帮忙的,但是他也需要去测试一下 我们的英雄呢,他们是否有能之士
所以,他就向他们提出了一个问题 要求他们利用四种不同的颜色
为这个地图着色 好了,我们来看看这个地图问题的模型
在这个模型里面呢我们有一个新的概念 就是枚举类型的数据。
如果你们还记得呢 我们之前看过的模型里面,数据都是数字来的
但是那数字就没有什么代表性了。
我们 利用这个枚举类型的数据呢,我们就可以给每一个数据
命名,譬如说我们不说 0 1 2 3,我们给它说
绿色,蓝色,粉红色跟黄色 这个就比较有代表性了。
然后就是我们的变量 我们的变量就是在地图上面每一个地方
都有一个变量,这个变量就是代表这个地方要采用的颜色
约束方面,我们看看雍州这个例子吧
雍州跟凉州在旁边 所以呢,它们不可以有相同的颜色
所以呢,我们的约束就要求它们的值不相等的 雍州跟益州也是
相邻,所以呢,我们也要求它们的值是不相等的 也有雍州跟荆州
雍州跟这个泗州,我们也相同,有类似的约束
然后其他的约束呢,就如此类推了
根据这个地图,就可以表达出来 我们可以运行下面的命令,要求
MiniZinc 给我们求解 MiniZinc color.mzn
color.mzn 就是我们刚才这个模型它的档案的名字 这个就是求出来的一个答案
利用这个答案呢,我们就可以为这个地图上面每一个州
放上不同的颜色,来代表不同的地方了 在刚才看见的模型当中,一个新的概念
叫枚举类型,枚举类型 enums
是用来定义一个具有有限对象的集合的 最特别的地方就是在这个集合里面,我们可以为它每一个元素
命名,枚举类型有下面的应用
决策变量跟参数可以是枚举类型的
数组的下标也可以是枚举类型的,集合的元素
也是基于,也可以基于枚举类型来定义的。
但是呢 数组跟集合我们还没有介绍
我们要声明一个枚举类型很简单,就是利用 enum
这个 关键词,然后给这个枚举类型一个名字就可以了
要定义一个枚举类型呢,我们就把,把一个集合
集合里面呢,是不同的标识符
然后把这个集合,赋值给这个枚举类型的名字就可以了
然后,如果我们需要利用枚举类型来声明一个变量
这个变量可能是参数,也可以是决策变量 就看看我们需不需要var这个关键词。
然后枚举类型,这个 类型,然后就是我们变量的名字
假如现在我们的问题也有这个新的改动
就是我们只可以利用三种颜色为这个地图着色 那我们就可以到我们的模型里面
把这个枚举类型的定义,把其中一个颜色去掉 然后我们要求
MiniZinc 求解,然后这个运行结果呢是
有跟之前有一点不一样,它说 UNSATISFIABLE 这个就表明呢,我们新的问题是没有解的
就是说,三种颜色对我们刚才看见的这个地图呢,是没有解的
我们来一个小结
枚举类型呢,是引入了一个已命名对象的集合
是可以帮助我们模型的类型的安全性的
在我们之后的课程,我们也有更多关于枚举类型的内容
我们在这个问题当中,也学到,原来
有一些模型是不可以满足的 就是说,不是每一个模型都一定是有解的
我们看这个地图的着色的 问题呢,其实是一个非常经典的图论的问题
它在编译寄存器分配这个问题里面有应用
对这个时间表的问题,也有广泛的应用 如果我们的问题是个纯的
图着色的问题呢,我们最好就是用专门的算法来解决了
但是在现实当中,我们很多时候我们的问题
还是有其他的约束,其他的条件的,那我们的求解的方法,就比较好了
[空白_录音]
[空白_录音]