分配(指派)问题
什么是分配问题:分配问题也称指派问题,是一种特殊的整数规划问题,分配问题的要求一般是这样的:n个人分配n项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。简单的说:就是n*n矩阵中,选取n个元素,每行每列各有一个元素,使得和最小。匈牙利算法1、理论基础:若从指派问题的系数矩阵的某行(列)各元素中分别减去或者加上常数
什么是分配问题:
分配问题也称指派问题,是一种特殊的整数规划问题,分配问题的要求一般是这样的:
n个人分配n项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。
简单的说:就是n*n矩阵中,选取n个元素,每行每列各有一个元素,使得和最小。
匈牙利算法
1、理论基础:
若从指派问题的系数矩阵的某行(列)各元素中分别减去或者加上常数k,其最优任务分解问题不变。
2. 匈牙利算法的流程图
3.计算步骤
例如:有A、B、C、D四项任务,需要分配给甲乙丙丁四个人来完成。他们完成任务所需要支付的酬劳如下表所示,问,如何分配任务,可使总费用最少?
得到的支付矩阵是:
Step 1: 行归约
找出每行的最小元素,分别从每行中减去这个最小元素;(能够使每行必出现“0”)
矩阵变换如下:
Step 2 : 列归约
找出每列的最小元素,分别从每列中减去这个最小元素 ; (能够使每列必出现“0”)
Step 3 : 指派任务
① 确定独立零元素
从第一行(列)开始,若该行(列)中只有一个零元素,对该零元素标1,表示这个任务就指派给某人做。
每标一个1,同时将该零元素同列的其他零元素标为2,表示此任务已不能由其他人来做。(此处标1、2的操作与课本画圈、划去操作同理)
如此反复进行,直到系数矩阵中所有的零元素都已经被标为1或者2为止。我们得到的矩阵如下:
此时,只需将0(1)所在位置记为1,其余位置记为0,则获得了该问题的最优解。
最优解为:
即:A任务交给丙负责,B任务交给丁负责,C任务交给甲负责,D任务交给乙负责。
此时总报酬为:1+5+2+3 = 11;
其他情况
① 出现零元素的闭合回路 ②标记成1的元素个数小于n
i.出现零元素的闭合回路(有多于两行或两列存在两个以上的零元素。)
对于矩阵:
我们所有变化后,得到矩阵:
图的第一行的一二列零元素和第四行的一二列零元素构成回路 (第一行(列)和最后一行(列)看做连通的)
这里我们的处理方法是:
先对cost方阵做一个备份(因为会出现多解),然后我们可以顺着回路的走向,对间隔的零元素标记成1,然后对标记成1的零元素所有的行列划一条直线,把这两条直线的其他零元素标记成2,得到一种结果后,再求出多解。
这里我们采用间隔标记法,得到矩阵:
最优解为:
最小酬劳为:1+2+2+2=7
ii. 矩阵中所有标记成1的零元素小于n。
例如矩阵:
经过所有变换后得到矩阵:
被标为1的0总共有3个,小于4。
因此,我们需要对其进行【画盖0线】的操作。(即画出可以覆盖最多0元素的直线)
(1)画盖0线:利用最少的水平线和垂直线覆盖所有的零。
具体操作如下:
① 对没有标记为1的零元素所在的行打√;
②在已打“√”的行中,对标记为2的零元素所在列打√
③ 在已打“√”的列中,对标记为1的零元素所在行打“√”
④重复②和③,直到再不能找到可以打√的行或列为止。
⑤对没有打“√”的行画一横线,对打“√”的列画一垂线,这样就得到了覆盖所有零元素的最少直线数目的直线集合。
对矩阵进行操作:
① 打勾
② 划线
(2)继续变换系数矩阵
①在未被覆盖的元素中找出一个最小元素。
②对未被覆盖的元素所在行中各元素都减去这一最小元素。这时已被覆盖的元素中会出现负元素。
③对负元素所在的列中各元素加上这一最小元素。
对上述矩阵:20为未被覆盖元素中最小的元素。变换矩阵,并寻找得:
Step4
我们发现,在经过一次变换后,独立零元素的个数仍然少于4.此时返回第三步,反复进行,直到矩阵中每一行都有一个被标记为1的元素为止。
例如在上述矩阵中:
矩阵中独立零元素仍然小于n。对矩阵执行打勾、划线等操作,得出未被覆盖区最小元素为5,进行系数变换之后得到矩阵:
我们发现得到的矩阵每行列有多个零元素(零元素的闭合回路),再运用上述方法可以得到矩阵:
最优解为:
最小酬劳为:15+65+25+50=155
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)