联军屡次告捷 袁绍、
曹操和刘备希望乘胜追击 打败董卓,董卓唯有派出手下猛将吕布迎击
吕布武功高强,战无不胜 吕布出战,单人匹马就打败了多名联军将士
刘备、 关羽和张飞闻讯,前来支援,围攻吕布
他们打算攻击吕布身上的五个弱点
三人武功各有所长,对弱点的打击损伤也各有不同 因此三人计划各攻一处
使吕布难以防守,又尽可能达到最大的进攻效果
刘备取出神算法板,马上求出最佳进攻方案
>> 现在我们的三个英雄要大战吕布了
当然了,我们知道吕布是一个非常厉害的人物 但是呢,我们的英雄也知道吕布的弱点的
就是在他身上的不同的穴道 分别就是百会、
膻中 曲池、 天枢、
涌泉 那我们的英雄呢,他们的武
功也是各有特色,所以呢,他们如果攻击
吕布的不同的弱点的时候,也可以做成不同的 这个破坏、 伤害。
所以呢,我们这个吕布问题 就是需要我们的英雄刘备、
关羽跟张飞 分别攻击吕布的不同的弱点来分散他的注意力
而且当然了,我们需要就是对这个吕布做成最大的伤害
但是呢,我们的吕布问题其实
就是一个纯分配的问题,在这个问题里面,我们有 三个英雄跟五个攻击点,然后我们希望
给每一个英雄呢,分配到一个攻击点,来把这个对吕布的伤害最大化
一个纯分配问题,也是一个
确定函数的问题,在这个问题里面呢,我们就是要给一个集合 我们叫
"DOM" (domain),就是我们的定义域 在这个 DOM
当中呢每一个对象,我们希望可以分配到 一个来自另外一个集合,我们叫
"COD" (codomain) 我们叫"值域",从这个 COD 的
分配到,就是分配到这个 COD 里面的不同的值里面
我们可以把这个问题理 解为要定义这样子一个从
DOM 映射到 COD 的函数
就像我们这个图要表示一样 但是,这个问题的另外一个看法呢就是我们看看
DOM 这个集合
我们就是要把它里面的元素 利用这个
COD 里面的元素来做标记,去割分开来
在我们的问题里面 其实这一类的函数可以是单射的
就是我们现在面对的分配问题;也可以是双射的 双射的意思就是
DOM 的大小跟 COD 的 大小是一样的,那我们的分配问题就变成了 匹配问题。
在我们这个吕布问题当中呢,我们的 DOM 就是我们的英雄了
COD 就是吕布的弱点,所以,我们现在要面对就是分配问题
在这个我们这个问题里面的数据
我们可以看看,这是包括我们的英雄呢,吕布的弱点呢
然后我们还需要一个数组,这个数组呢就代表每一个英雄 攻击吕布的不同的
弱点可以做出来的伤害 那我们的变量是什么呢?
很简单,我们也是一个整型的变量数组
这个数组呢,每一个元素就是给每一个英雄决定
到底我们需要攻击吕布的哪一个弱点 我们的目标也是非常简单
就是要把我们要攻击吕布 的不同的要害,然后要把这个
做成的伤害最大化。
好了 我们的问题有什么约束呢?
这个约束很简单,就是每一个英雄都要攻击一个不同的点
我们可以这样子看,就是每一个攻击点最多可以给分配到一个英雄 我们就可以这样子去写、
表示,就是说 我们看看每一个弱点,然后看看这个弱点
到底有多少个英雄去攻击呢? 我们要求这个是小于,或者是等于
1 换句话说,我们也可以说要求两个英雄被分配到
的攻击点不可以相同,所以我们可以这样子去表达出来,就是说
两个不同的英雄,我们要求他们攻击的地方都是不一样的
那有两个方法来代表
同一个条件,那哪一个比较好呢? 我们的答案就是,我们还是不要选择了
因为呢,不同的求解器它对不同的表示方式都有不同的处理方法
我们需要做的就是把问题的结构
告诉这个求解器,然后让这个求解器去决定
用什么方法来处理是最好的,这个我们就可以利用一个叫
"全局约束"来帮助我们解决这个问题 这个全局约束的设计就是为了要
捕捉问题的结构,然后把这个结构告诉我们的求解器
在我们的问题里面需要的全局约束呢,就是 alldifferent
它的参数就是我们要攻击的点 alldifferent
这个约束大家应该也见过了,但是 当时我们没有好好地去解释它的意义是什么
其实它是限制 我们每一个英雄被分配到不同的攻击点
这个是我们全局约束的第一个例子 而
alldifferent 呢,其实是捕捉了
分配问题的一个子结构 或者可以说呢,它也捕捉了
怎么去确定一个单射函数 这个呢,就是我们这个吕布问题的模型
基本上就是把我们之前提过的东西都加起来
当然有我们的数据呢,我们的变量,还有我们的约束
要注意的地方就是因为我们要用一个全局 约束,所以我们一定要把这个
include 这一句加起来 然后就是我们的目标函数
纯分配问题其实已经
被研究得很透彻,而且已经有专门的算法
基于这个最大加权匹配来算这个分配问题的解
而且这一批的算法都是非常快速的
所以呢,如果你有一个纯分配问题呢,我们的建议
你们应该去用专门设计的算法,不要用这个求解器来做,但是呢
在现实的世界里面永远不是纯粹的,我们很多 时候有一个纯分配的问题,但是也有一些
额外的约束,如果我们增加了这些额外的约束呢,我们这一批 专门的算法很多时候都会
被破坏了,所以呢,它们就不可以用了 我们来做一个小结
确定一个有限的函数是常见的
确定一个单射函数其实是一个分配的子问题 alldifferent
这个全局约束 是很好地去捕捉了这个子结构
全局约束,它的设计就是为了要 捕捉了这个子结构,把它告诉了这个求解器
然后让这个求解器去决定最好的方法来解决它 我们在未来会讲更多的关于全局
约束的问题
[空白_录音]