对于多人完成多个代价不同的任务的指派问题,匈牙利算法是一种有效的解决方案,本文记录相关内容。
叫做
匈牙利算法
的事实上有两个算法,分别解决指派问题
和二分图最大匹配求解问题
,此处算法指求解指派问题的匈牙利算法。
每行每列最小元素非负
进行试指派,以寻求最优解。为此,按以下步骤进行。
有A、B、C、D、 E五项任务,需要分配给甲、乙、丙、丁、戊 五个人来完成。他们完成任务所需要支付的酬劳如下表所示,问,如何分配任务,可使总费用最少?
〇
行打钩 √
〇
行有 〇
列打钩 √
√
列有 〇
行打钩 √
√
行划线√
列划线得到覆盖所有0元素的最少直线数。
√
的行列)
甲 | 乙 | 丙 | 丁 | 戊 | |
---|---|---|---|---|---|
任务安排 | B | C | E | D | A |
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