诸葛亮并不满意利用神算法板
求出的方案,他发现之前未曾考虑旋转船块 其后诸葛亮与庞统商议后,均认为
旋转船块后再连接,可以缩减长度 诸葛亮便取出神算法板
>> 诸葛亮在想清楚 之前拿到这个打包的结果,其实他也不太满意
因为呢,在里面有太多浪费的空间,而且呢结果也太长
后来呢,他也发觉,他漏了一个非常重要的一点 就是原来形状呢,它们是可以有不同的朝向的
好了,这个是一个非常普通的一个形状,这个形状里面呢是用
不同的矩形来组成的,这样子的一个普通的 形状呢,它基本上通常呢有四种不同的朝向
这个是一个,然后我们把它旋转的话,我们可以拿到另外一个朝向
再转的话,我们有另外一个朝向,再转,我们还有另外一个朝向
再转的话,我们就回到,回到这个原来的朝向了
好了,但是在特定的情况之下,譬如说,如果我们的形状只是一个
简单的矩形的话,它只有两种不同的朝向,因为另外两个朝向呢,基本上是重复的
如果是个正方形的话,只有一种的朝向,又或者呢在我们的应用里面
有一些特别的限制,譬如说在我们的故事里面,我们可以
有一个条件就是说,这个船块呢,只可以在特定的方向
移动的话,那另外三个朝向呢,就是不允许了
好了,这个呢是我们之前看见过的。
就是利用 这个,这个四元组来代表一个形状里面不同的矩形 它的偏移。
它的第一个第二个参数呢,就是这个 矩形,它相对于这个
形状的基点的偏移,然后呢,第三跟第四个参数呢 就是这个矩形它
x 跟 y 的长度,这个我们也懂得怎么做了
我们现在的问题就是,如果我们有一个形状 它有一个新的朝向,我们怎么表示它呢?
我们觉得其实这跟处理一个新的形状是没有 区别的。
因为一个新的朝向呢,应该有新的原点
和这个新的偏移,我们就来看看这个例子吧,我们先看看它一个新的朝向
好了,有一个新的朝向之后,它的基底呢 就再不是这个点了,
它的基底呢,就应该来到这里 有了一个新的基底的话,我们发现呢,它里面的每一个矩形
它的里面的偏移跟它的大小呢,都应该改变了
所以呢,对我们来说,这个新的朝向就好像一个,是一个新的一个形状
所以呢,有了这个理解之后,我们 就发觉以前呢来代表一个形状的方法
根本就可以用来代表一个形状的新的朝向,所以呢我们也是应该把这个问题里面
不同的带偏移的矩形都列出来,然后每一个
矩形的偏移呢,我们都给它一个数字,然后呢,对一个形状,我们就说 它是基于第一、
第三跟第四个 带偏移的矩形来组成的,这个是我们的一个形状。
到了它的一个新的 朝向的话,它就是基于不同的带偏移的矩形
了,所以我就说,这个是基于第二个、 第五个跟第六个 这个带偏移的矩形来组成的一个新的朝向来了
但是呢,我们不要忘记一点就是
一个形状呢,现在有最多四种
不同的朝向,我们之前呢,怎么定义一个 矩形呢?我们就说,它是一个带偏移的
矩形的集合,但是现在呢,我们一个形状 有可能有四个不同的朝向,所以呢我们要把这个
形状呢,来重新定义,一个形状应该是一个带
偏移矩形的集合的一个列表,这个列表呢
就是可以用一个数组来代表了,里面呢它的元素应该有四个
那我们也记得呢,有一些形状,它没有
四个不同的朝向了,就是说,有一些朝向呢,我们可以说是不允许 或者呢,它们是重复的。
在这个情况之下,我们就可以利用 空集呢,来表示这一类的不允许的朝向就可以了
好了,我们看看我们这个问题怎么可以修改我们原来的
模型,来把这个不同的朝向也带进来 考虑呢?首先,我们要定义一个新的参数
就是呢,朝向的可能性,我们 总共有四个可能性。
然后呢,我们刚才也提过 形状呢,之前是个一维的数组,现在呢
它变成一个二维的数组,就是给每一个形状
就是每一行,每一行呢,都有一个四个不同的朝向的可能性
每一个朝向呢,都是一个带偏移矩形的集合来的
其余的参数呢,就不需要改变了 好了,我们看看这个我们
加强这个版本,这个问题的文件档
好了,我们发现呢,最基本的参数都不需要改变的,我们还是利用
同一个方法,一个四元组,来代表一个带偏移的矩形,但是呢因为我们也把这个
不同的朝向带进来考虑,所以我们可以看见呢
一个相同的问题里面,我们的矩形的数目多了很多
好了,这个就是我们新的 对这个形状的定义,之前呢,一个形状呢就是一个
一维的数组,现在呢就是一个二维的数组 每一行呢,就是代表一个形状的不同的朝向
OK,总共有四个,第二个形状也是有四个不同的朝向,第三个形状
也是,我们看看第四个形状,它只是用,由一个矩形来组成
所以这个形状基本上就是一个矩形,所以呢它只可以有
两个不同的朝向,所以呢它的所谓第三个跟第四个朝向呢
我们就不重复了,我们就利用一个空集呢来代表 然后这个就是我们第五个形状,它四个朝向的定义了
有了这个数据之后,我们就看看我们这个
模型里面的变量,我们除了每一个 形状,它的基底的
x 跟 y 的坐标之外呢,我们还要定义多一个
新的变量数组,就是代表呢,每一个形状,我们需要选取它哪一个的
朝向,然后呢,我们的要优化的目标函数,跟
之前也是一样,就是呢,打包出来的总长度要最小化
好了,我们就到了我们的模型里面的条件。
首先,我们要增加 一个新的条件,我们呢就要求呢,每一个形状它选取的
朝向呢,不可以是一个不允许的朝向,我们就用一个空集来代表的
之前呢,我们有一个条件呢就是,每一个形状里面的 矩形,都应该在我们最后打包出来这个河道的
范围里面的,我们就要求呢, 每一个选取的形状里面的矩形都要 在这个范围里面。
但是现在呢,我们拿这个矩形出来的,也需要
知道这个形状我们是选取了哪一个的朝向 这个就,把这个加进来呢,就可以表达我们要的条件了
另外一个条件呢就是,带偏移的矩形呢
应该是互不重叠,这个跟之前也是差不多,就是我们在从
形状里面,选取一个矩形,来要求跟它们不重叠
但是我们也需要知道,每一个形状我们选取的它的朝向是哪一个
好了,我们有了新的模型之后,我们就
可以求解,求解出来结果呢,我们可以看到呢,就是比之前的
是少了非常多的浪费的空间,而且呢,出来的结果的长度也短了
这个就是我们可以看见的我们之前是需要 1400 米的
现在一个新的结果呢,只需要这个 1100 米就可以了
好了,看到这里呢你们也觉得我们应该还是有可能把我们的模型改 进的。
当然我们可以利用就是全局约束 因为我们知道在这个问题里面最重要的一个
约束呢就是我们要求呢矩形不可以重叠 我们也知道
diffn 这个全局约束就是来保证
两个不同的矩形呢不重叠的,就算如果我们这个打包问题 是给扩展到
k 维的话,其实我们也有 diffn_k
这个全局约束来帮助我们解决 k 维的打包问题。
但是 diffn_n 呢 它的问题就是没有把这个不同的朝向
也考虑进去,所以呢我们有一个更好的 一系列的全局约束,我们叫它叫 geost。
这个 geost 系列的全局约束呢 除了保证相互不重叠之外,也把我们这个问题
里面不同的形状,它的不同的朝向也考虑进去
然后一起来解决这个问题,所以呢 它求解的效率也比我们利用这个
diffn 呢,可以高很多的 geost 是个一组的全局约束,我们
要解决这个问题呢,我们需要采用这个版本叫 geost_bb
bb 就是代表这个 bounding box,它有很多不同的参数,我们就一一来 看看吧。
第一个参数为 k , k 呢就是代表我们要解决这个问题 它的维度的数量。
在我们的问题呢,k 呢应该为 2 然后第二跟第三个参数就是来代表问题里面
的不同的带偏移的矩形的,在我们原来的数据里面呢
我们每一个带偏移的矩形呢,我们都利用一个四元组来表示的,但是呢 在
geost_bb 里面呢,它要把这个矩形的它的大小跟它的偏移呢都分开来 表示。
好了,先看看它们的大小 这个呢是个二维的数组来的,第一维呢就是代表不同
矩形,就是代表不同的矩形。
第二维呢 就是它里面的元素的
数量呢就应该为 k ,就是用来代表呢一个 k
维 矩形它的大小,在我们的问题里面我们的矩形是个二维的矩形,所以
呢这个在这个数组里面每一行呢就是代表这个矩形的 x 跟
y 的长度了 好了,到了我们矩形的偏移,它们也是一个二维的 数组。
第一维也是不同的矩形,第二维呢就是用来代表 每一个矩形,它跟
x 跟 y 的偏移 到了第四个的参数,就是我们的形状了
这个形状呢是一个一维的数组来的,每一个元素呢就是代表
不同的形状它不同的朝向
它的表示方法呢就是利用一个 整数的集合。
这个集合里面呢每一个 整数就是代表不同的矩形它的编号
到了下面呢,就是我们每一个形状
它的基底、 它的坐标。
这个 跟之前也是一样,每一行就是代表每一个形状,然后呢
第二维呢就是用来代表它的一个坐标 当然呢它的坐标的维数呢要跟这个
k 呢是一样的 另外一个参数呢,我们叫 kind。
这个 kind 呢就是相对于每
一个形状它选取的朝向是什么来的,然后最后 l
跟 u 呢 就是我们这个问题里面,打包进去这个范围,它的 下界跟上界。
好了,其实大家也可以看见我们刚才 看这个
geost_bb 的全局约束呢。
它的参数的要求跟我们原来这个数据 的格式呢不太吻合,所以呢
我们要为这个问题建模也利用到这个 geost_bb
的话 我们里面呢需要很多的约束呢,来帮助我们做这个数据的 转换,其实也挺麻烦的。
但是我们也是做了 出来,如果你们有兴趣的话,你们就可以参考呢
我们提供这个 sbprotategost
.mzn 这个文档呢,就可以看看里面详细的情况了
好了,如果我们愿意把我们的数据的格式 修改一下的话,那我们的模型呢就可以简单得多了
我就先看看我们怎么修改我们的数据文件
这些基本的函数呢我们都不修改了,包括每一个矩形它的 偏移跟它的大小。
要改变的地方呢就是这个所谓是 形状的表示方法。
现在呢其实一个形状呢是不单是一个形状
也包括了它的朝向,所以我们现在看见呢这个集合就代表 利用 1、 2、
3 这个带偏移的矩形组成的一个形状 但是呢它也已经决定了这个形状它某一个朝向了
所以在这里面呢,就是可以代表 每一个形状跟它已经有决定了的一个朝向
这个好处呢就是我们不再需要利用这个空集来表示一些不允许的朝向了
好了,然后我们还需要增加一个新的 一个数据,这个新的数据呢就是来代表
同一个形状它的不同的朝向。
在这里呢就代表 这个集合就代表一个形状,原来呢在上面这个数组里面
第一个集合、 第二个集合、
第三到第四个集合 一起呢,就是代表同一个形状它不同的朝向
然后第五个,到了第八个集合呢,就代表 我们第二个形状它的朝向。
我们再看看我们比较特别的一个形状 它只是一个简单的矩形,所以呢,它只是需要有
两个不同的集合来代表这个形状
有了这个之后,我们就需要把我们 的模型做一点小的改动,首先
我们刚才已经提过了,我们形状的定义要改变,变回一个一维的数组
然后呢,其实我们
刚才呢也没有把我们的数据完全地改变,我们还是利用一个
四元组来代表一个带偏移的矩形
所以呢,我们还是需要两组的约束呢,来
把一个四维四元组分别把它的
大小,一个矩形的大小跟一个矩形它的偏移呢,都把它拿出来放到另外
两个新的数组,以便我们可以把它们输入到我们 geost_bb
这个全局约束里面 我们之前的模型里面呢是利用 x
跟 y 两个数组呢,来代表我们每一个形状它自己的 坐标在哪里的。
但是呢我们也刚才看到这个 geost_bb 呢是需要把
这个坐标呢是放到一个 数组里面来输入的。
所以呢,我们这一个 这一组的条件呢,就是把
x 跟 y 两个数组呢,把它放进同一个数组里面
好了,到了最后我们只需要 一条的 geost_bb
的约束就已经可以把 我们整个问题呢来代表了,分别就是我们一个二维的问题,我们里面的
带偏移的矩形的大小,它的偏移,然后我们问题里面有的不同的 形状跟它的朝向。
这个就是每一个形状它的自己的坐标 然后每一个形状它选择的朝向是什么
然后 0 到 l 跟 0 到 x 就是我们这个河道
这个范围的下界跟它的上界,我们其实还需要呢,要求呢我们选取的
这个朝向一定需要是在我们 shapeind 这个数组
每一个元素代表这个集合里面 就代表了我们
这个朝向真的是从某一个形状里面的 可能的朝向里面选取出来的
好了,我们利用了这个全局约束呢,我们 不需要一、
两秒钟的时间呢,已经可以把同一个解呢,已经可以求出来了 这个所以我们可以看见,这个全局约束可以帮
助我们把我们求解的效率大大地提高 好了,其实我们面对这个把这个
船块打包这个问题呢,是在我们现实当中一个地毯
切割问题的一个变种,譬如说我们 买的一个新房子,我们希望把这个新房子里面每一个房间
都铺上这个地毯,我们怎么做呢?我们首先需要
量度我们每一个房间的大小跟它的形状
在我们现在的房子里面,我们的房间的形状通常都是
直边形的形状来的。然后呢,我们就需要把我们房子里面不同的房间
对这个地毯的形状的要求,在一条宽度固定的地毯卷上面
切割出来,然后我们才可以铺这个地毯到我们的新的房子里面
我们可以知道呢,一个卖地毯的公司呢,他们应该对我们刚才解决
这个问题的模型非常有兴趣,因为如果我们可以把我们需要地毯
卷的长度最小化的话,第一,我们可以减少我们的浪费
第二,这个呢就是说,这个地毯公司可以有,赚更多的钱了
但是,地毯切割这个问题呢,如果加上这个地毯
不同的方向,而且也有这个楼梯有的要求
补丁地毯的要求,或者是编织的要求 的话,这个问题呢,就可以变得非常的复杂了
好了,我们看看,一个普通的地毯,如果上面没有
花纹的话,我们之前已经看过了,它基本上应该有四种不同的朝向
就是有四种不同的方法呢,可以把它切割出来 但是如果我们地毯上面呢有些条纹的话
譬如说是横向的条纹的话,就代表了 我们如果要把这个形状从我们的地毯卷
里面切割出来的话,我们只有两个朝向可以把它切割出来
如果我们的地毯上面是有一个图案的,这样子的图案呢,就会
完全把这个地毯的对称破坏,所以呢,我们只有一种的方法可以把它切割出来
我们 面对的这个打包问题是非常复杂,复杂呢是因为不同的形状
是由不同的组件合成出来的,而且呢,我们还需要保证组成的部分
互不重叠,而且呢,如果我们把这个朝向
也加进了考虑的话,这个问题就变成了非常复杂了
我们当然呢,也有不同的全局约束可以 帮助我们建模,还可以帮助我们把这个
求解的这个效率提高 包括就是
diffn_k 跟这个 geost,但是呢 geost 呢比 diffn_k 更好,是因为
geost 呢,可以把这个 不同的朝向也加进了考虑,来把这个问题解决
虽然呢,我们的全局约束呢,它们都可以解决一些高维的问题的,但是在
实际的情况当中呢,大部分我们的打包问题都应该是二维或者是三维的
[空白_录音]