指派问题 —— 匈牙利算法

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

指派问题

• 在生活中经常遇到这样的问题，某单位需完成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 元素不变

五、重新圈零

• 重新进行第三步圈零操作 乙和丁的任务可以交换

• 因此指派方案确定

• 最终匈牙利算法的结果

• 总共花费的费用和为 32

Python 实现

• python 解决方案中，用到的是 scipy.optimize.linear_sum_assignment(cost_matrix)
• 以上文的算法示例为例

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())  # 数组求和，求得总花费

• 输出结果

[[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.cnblogs.com/ylHe/p/9287384.html
• https://www.pianshen.com/article/35751358181/
• https://www.freesion.com/article/5336622238/
• https://blog.csdn.net/qq_40894102/article/details/105980364
• https://blog.csdn.net/siss0siss/article/details/51325656