指派问题 —— 匈牙利算法

本文最后更新于:2022年7月4日 上午

对于多人完成多个代价不同的任务的指派问题,匈牙利算法是一种有效的解决方案,本文记录相关内容。

指派问题

  • 在生活中经常遇到这样的问题,某单位需完成$n$项任务,恰好有$n$个人可承担这些任务。由于每人的专长不同,各人完成任务的代价不同(收益不同)。于是产生应指派哪个人去完成哪项任务,使完成$n$项任务的总代价最小(收益最大)。这类问题称为指派问题或分派问题。
  • 这类问题可以依据人员和代价(收益)建立矩阵,称为效率矩阵或系数矩阵,其元素 $𝑐_{𝑖𝑗}>0(𝑖,𝑗 = 1,2,…,𝑛)$表示指 派第𝑖人去完成第𝑗项任务时的效率(或时间、成本等)。
  • 代价矩阵有一个性质,若从指派问题的系数矩阵的某行(列)各元素中分别减去或者加上常数$k$,其最优任务分解问题不变。

匈牙利算法

叫做匈牙利算法 的事实上有两个算法,分别解决指派问题二分图最大匹配求解问题,此处算法指求解指派问题的匈牙利算法。

算法流程

算法内容

第一步
  • 数矩阵经变换,在各行各列中都出现0 元素。

    • 使指派问题的系数矩阵经变换,在各行各列中都出现0 元素。
    • 从系数矩阵的每行元素减去该行的最小元素;
    • 从所得系数矩阵的每列元素中减去该列的最小元素。
    • 若某行(列)已有0元素,那就不必再减了。

    每行每列最小元素非负

第二步

进行试指派,以寻求最优解。为此,按以下步骤进行。

  • 经第一步变换后,系数矩阵中每行每列都已有了0元素;但需找出𝑛个独立的0元素。若能找出,就以这些独立0元素对应解矩阵 $(𝑥_{𝑖,𝑗})$中的元素为1,其余为0,这就得到最优解。
  • 步骤为:
    1. 从只有一个0元素的行(列)开始,给这个0元素加圈,记作◎ 。这表示对这行所代表的人,只有一种任务可指派。然后划去◎ 所在列(行)的其他0元素,记作Φ。这表示这列所代表的任务已指派完,不必再考虑别人了。
    2. 只有一个0元素列(行)的0元素加圈,记作◎;然后划去◎ 所在行的0元素,记作Φ。
    3. 反复进行(1),(2)两步,直到所有0元素都被圈出和划掉为止。
    4. 若仍有没有划圈的0元素,且同行(列)的0元素至少有两个( 表示对这个可以从两项任务中指派其一)。这可用不同的方案去试探。从剩有0元素最少的行(列)开始,比较这行各0元素所在列中0元 素的数目,选择0元素少的那列的这个0元素加圈 (表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其他0元素。可反复进行,直到所有0元素都已圈出和划掉为止。
    5. 若◎元素的数目𝑚等于矩阵的阶数𝑛,那么这指派问题的最优解已得到。若𝑚<𝑛,则转入下一步。
第三步
  • (𝑚 < 𝑛时的处理办法):作最少的直线覆盖所有0元素,以确定该系数矩阵中能找到最多的独立元素数。
  • 为此按以下步骤进 行:
    1. 对没有◎的行打√号;
    2. 对已打√号的行中所有含◎元素的列打√号;
    3. 再对打有√号的列中含◎元素的行打√号;
    4. 重复(2),(3)直到得不出新的打√号的行、列为止。
    5. 对没有打√号的行画一横线,有打√号的列画一纵线,这就得到覆盖所有0元素的最少直线数。
      令这直线数为𝑙。若𝑙<𝑛,说明必须再变换当前的系数矩阵,才能找到𝑛个独立的0元素,为此需要转第四步:若l=n,而m<n, 应回到第二步(4),另行试探。
第四步
  • 对矩阵进行变换的目的是增加0元素。
  • 为此,在没有被直线覆盖的部分中找出最小元素,然后在打√行各元素中都减去这最小元素,而在打√列的各元素都加上这最小元素,以保证原来0元素不变。
  • 这样得到新系数矩阵(它的最优解和原问题相同)。若得到𝑛个独立的0元素,则已得最优解,否则回到第三步重复进行。

算法示例

有$A、B、C、D、 E$五项任务,需要分配给$甲、乙、丙、丁、戊$ 五个人来完成。他们完成任务所需要支付的酬劳如下表所示,问,如何分配任务,可使总费用最少?

一、减法归约

  • 行归约:每行元素减去该行最小元素。

    • 画圈为行最小值:

    • 每行减去最小值:

  • 列归约:每行元素减去该行最小元素。

    • 每列最小值已经为 0 无须继续归约:

二、圈零划零

  • 找到含零元素最少的行,对零元素打圈,划去打圈零元素所在行和列存在的零元素,重复这个步骤,直到矩阵中所有的零元素都被处理完。

三、打勾划线

  • 打钩
  1. 行打钩
  2. 行有 列打钩
  3. 列有 行打钩

  • 划线
  1. 行划线
  2. 列划线

得到覆盖所有0元素的最少直线数。

  • 此时线数为4,少于节点数5,需要进入下一个调整值的步骤

四、元素调整

  • 在没有被直线覆盖的部分选择最小值,作为调整元素

  • 划线列,不划线行为需要调整的行列 (划 的行列)

  • 调整行减去调整元素

  • 调整列加上调整元素

    此种操作会保证行中的 0 元素不变

五、重新圈零

  • 重新进行第三步圈零操作

    乙和丁的任务可以交换

  • 因此指派方案确定
任务安排 B C E D A
  • 最终匈牙利算法的结果

  • 总共花费的费用和为 32

Python 实现

  • python 解决方案中,用到的是 scipy.optimize.linear_sum_assignment(cost_matrix)
  • 以上文的算法示例为例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from scipy.optimize import linear_sum_assignment
import numpy as np

cost =np.array(
[
[12,7,9,7,9],
[8,9,6,6,6],
[7,17,12,14,9],
[15,14,6,6,10],
[4,10,7,10,9]
])
row_ind, col_ind=linear_sum_assignment(cost)
res = np.zeros_like(cost)
res[row_ind, col_ind] = 1
print(res) # 结果矩阵
print(cost[row_ind,col_ind].sum()) # 数组求和,求得总花费
  • 输出结果
1
2
3
4
5
6
[[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 0 1]
[0 0 0 1 0]
[1 0 0 0 0]]
32

参考资料


指派问题 —— 匈牙利算法
https://www.zywvvd.com/notes/study/math/hubgairan-assignment/hubgairan-assignment/
作者
Yiwei Zhang
发布于
2022年4月9日
许可协议