曹操与袁绍的大战越战越烈
一次战事中,袁绍大军派出颜良和文丑出战
两人武功高强,击败大批曹营将士 关羽闻讯后,带同张辽、
徐晃赶赴战场 关羽提议攻击颜良、
文丑的五个弱点 张辽、 徐晃同意。
他们对这些弱点有着不同的打击损伤 但首先出战的颜良配有特制头盔
故攻击头部,只会无功而返。
其后出战的文丑擅长下肢防守
若先行攻击颜良下肢,同样的招式就难以对早有提防的文丑有效
关于回忆起与吕布交战的相似情形
决定使用神算法板,求解最佳 战斗策略,却找不到正确的答案
于是呼叫大师求助
关羽要跟曹操的两名大将,要跟两个非常有名的
将军要对打,分别 就是颜良跟这个文丑
他们首先呢,要攻击颜良 然后再攻击文丑,我们要帮助他们做的就是
替他们选取攻击这两个将军的时候,应该攻击他们什么的要害
我们来看看人体的弱点 分别就是百会
膻中、 曲池,我们叫这三个要害就是人体
上半身的要害,还有天枢跟 涌泉,这个就是人体下半身的要害
因为我们的大将,他们都有不同的功夫,他们攻击不同的
点的时候可以做成的伤害也是不同的。
我们这里看见就是这个伤害的矩阵 好了,先讲一讲这个颜良
因为呢, 他有一个超强的一个头盔 所以呢,基本上我们攻击他的头部是没有用的
所以我们根本就不应该浪费时间去攻击他的头部 还有呢,这是文丑
文丑这个人呢,他有非常高强的下盘功夫 而且呢,如果给他看见你是怎么攻击
颜良的下盘的时候,他就可以想出怎么
很有效的去保护你对他的下盘的攻击了 所以呢,我们应该要求就是,如果一个
大将他攻击了颜良的下盘的时候 他攻击文丑的时候要攻击他的上半身
好了,我们看看这个 问题的数据,而且它的变量跟目标
我们的数据首先有2个 枚举数据来代表我们的英雄跟他们可以攻击的点
然后是一个数组来代表了每一个英雄
攻击每一个点的时候可以做成的是多少的伤害
我们的变量呢分别就是我们 每一个英雄应该攻击颜良的哪一个点
我们每一个英雄应该攻击文丑的哪一个点
我们的目标非常简单,就是把我们所有的英雄
攻击的点,它的可以做成的伤害 它的总和算出来,然后当然要把它最大化
然后就是我们这个问题里面的约束
当然了,我们要求我们每一个英雄攻击颜良的时候 每一个点都是不同的。
攻击文丑的时候也是一样 好了,到了我们最重要的条件
你们还记得就是说,颜良他有非常厉害的头盔保护,所以我们不应该攻击他的头部
而且呢,如果一个英雄攻击了 这个颜良的下盘的时候,他攻击
文丑的时候,就不应该攻击他的下盘, 应该攻击他的上盘 所以呢,
我们首先定义了守是哪几个点呢 是所谓是一个人体的弱点的下盘的弱点,然后还有就是
上半身的弱点,然后我们要求呢,每一个英雄
我们不应该攻击这个颜良的头部
百会穴,然后一个英雄如果
攻击颜良的下盘之后,他再攻击这个文丑的时候呢
他应该攻击他的上半身,这个就是我们的约束了 有了这个模型之后
我们就去跑,然后求得的解就是我们看见的
我们一看就觉得很奇怪了,因为我们已经讲过我们攻击这个颜良的时候
不可以攻击他的头部的,但是我们求出来的解就是建议我们去攻击他的头部
这个是绝对不合理的,就是说我们的模型出了问题了
一个模型出了问题,当然我们需要去调试
我们怎么知道我们的模型是否正确呢 那第一,我们建议你们一定要利用你们已经知道
正确的解的具体的例子来去测试你们的模型
而且呢,一个模型出错的时候有不同的错误的表征的
包括过多的解,就是呢,出了一些解
你们发现这个模型的解呢,不是我们问题的解来的 也有可能就是丢了一些解,就是说
有一些解你们觉得是应该是问题的解的,但是你们模型 求不出来,还有最差劲的就是
根本就是你要求它求解的时候,它就说无解,不可以满足 我们现在要面对的是过多解这个问题
其实这个已经是最容易的情况来的 过多解有两个可能的原因,第一
就是某一些模型的解,其实他不满足我们
问题里面原来要求的条件的,第二个
可能的原因就是我们问题里面很多的解呢
我们都是不感兴趣的,所以模型的解也是对的,但是就是没有用的解来的
在这个情况之下,我们有下面的建议 我们怎么解决这个问题。
因为呢,如果我们发现一个解是 没有用的,我们应该知道在我们模型里面呢
有一些条件是应该是排除这些没有用的解的
如果我们可以把这些条件找出来,然后把它检查
然后也把它修正,我们就可以把这个过多解这个情况 解决了。
我们来看看我们怎么解决 我们故事里面的模型这个问题
我们出现的不合理的解就是要求建议我们去攻击
颜良的头部,但是在我们的模型里面我们其实是有一个
约束是告诉我们不应该去攻击颜良的头部的
肯定问题就出在这个约束里面的 那这个约束出了什么问题呢?原来呢这是我们
对这个运算符的优先级出了一些误解 原来我们这样子表达出来是跟
这一个是等价的,这个绝对不是我们希望表达的一个 方案,其实我们要把这个问题解决非常
简单,我们只需要在这个后面 加上一个括号就可以把问题解决了,这个真的讲
我们不应该攻击颜良的头部,而且如果是攻击了颜良的
下盘的话,我们攻击这个文丑的时候,要攻击他的上半身
这个就是我们原来真的需要讲出来的条件来的 啊
过多的解呢有另外一个情况就是,所有的过多的解都是正确的
但是呢,不是每一个正确的解我们都有兴趣。
我们看看这个例子 我们有一个变量叫A,其实对A来讲没有什么条件,没有约束的
我们就求解了,如果我们求解的时候要求这个minizinc把所有的解都
输出出来的话,我们就有很多很多的解都列出来了 其实我们有两个可能的方案去解决这个问题。
第一个呢,我们就可以考虑 添加一些约束去把一些多余的解去移除
譬如我们可以看看我们的问题里面有没有对称
如果有的话,我们可以添加一些去对称的约束去把对称的解都去掉了
去对称是个非常重要的题目,我们 在未来会跟大家多讨论这个问题
另外一个方案我们就是可以添加一个目标函数
利用这个目标的优化把我们有兴趣的解才求出来 我们来一个小结
我们面对就是一个过多解的这个情况 这个情况出现其中一个最重要原因就是我们
模型里面出的解呢,有可能就是不是我们问题里面的解
我们要解决这个问题的方法就是,把我们模型里面应该把这个错误的解
要移除的这个约束找出来,然后看看错误在什么地方,然后把它修正
我们的模型呢也有,有可能有过多的 正确的解,我们要把一些没有用的解去
减去的话,我们可以添加这个约束 也可以添加目标函数
去挑选我们觉得有用的解才输出出来
[无声]