匈牙利算法详解与实现
匈牙利算法是一种高效的二分图最大匹配或最优分配算法,常用于解决任务分配问题,例如将工人分配给任务以最小化成本。该算法通过多步矩阵操作和调整来寻找最优匹配,保证了分配成本的最小化。
算法概述
1. 矩阵减法
首先对矩阵进行行列减法:
- 行减法:每行减去该行的最小值,使每行至少有一个零。
- 列减法:在行减法的基础上,每列再减去该列的最小值,使每列至少有一个零。
2. 划线覆盖零元素
用尽量少的直线(横线或竖线)覆盖矩阵中的所有零元素。如果划线数量等于矩阵维度,则已找到最优解,否则进入下一步。
3. 调整矩阵
找到未被线覆盖的最小元素并调整矩阵:
- 未被覆盖的元素减去最小值。
- 交叉线的交点元素加上最小值。
- 其他已被线覆盖的元素保持不变。
4. 寻找匹配
使用调整后的矩阵寻找最优匹配。优先选择那些行或列中只有一个零的元素进行匹配。
5. 计算最小成本
根据原始成本矩阵,计算匹配方案的总成本。
工人与任务分配问题
例1:3个工人和3个任务(工人任务匹配的情况)
假设有3个工人和3个任务,分配成本如下:
任务1 | 任务2 | 任务3 | |
---|---|---|---|
工人1 | 4 | 1 | 3 |
工人2 | 2 | 0 | 5 |
工人3 | 3 | 2 | 2 |
1. 行和列减法
行减法:
- 工人1:
4, 1, 3
→3, 0, 2
- 工人2:
2, 0, 5
→2, 0, 5
- 工人3:
3, 2, 2
→1, 0, 0
矩阵变为:
任务1 | 任务2 | 任务3 | |
---|---|---|---|
工人1 | 3 | 0 | 2 |
工人2 | 2 | 0 | 5 |
工人3 | 1 | 0 | 0 |
列减法:
- 任务1列:
3, 2, 1
,最小值是1 - 任务2列:
0, 0, 0
,最小值是0 - 任务3列:
2, 5, 0
,最小值是0
减去每列的最小值:
- 任务1列:
3 - 1, 2 - 1, 1 - 1
→2, 1, 0
- 任务2列:
0 - 0, 0 - 0, 0 - 0
→0, 0, 0
- 任务3列:
2 - 0, 5 - 0, 0 - 0
→2, 5, 0
调整后:
任务1 | 任务2 | 任务3 | |
---|---|---|---|
工人1 | 2 | 0 | 2 |
工人2 | 1 | 0 | 5 |
工人3 | 0 | 0 | 0 |
2. 划线覆盖零元素
通过观察,使用两条线就能覆盖所有零:
- 一条线覆盖任务2列。
- 一条线覆盖工人3的行。
3. 调整矩阵
最小未覆盖元素为 1
。对矩阵调整如下:
- 未被覆盖的元素减去
1
。 - 交点元素加
1
。
调整后矩阵:
任务1 | 任务2 | 任务3 | |
---|---|---|---|
工人1 | 2 - 1 | 0 | 2 - 1 |
工人2 | 1 - 1 | 0 | 5 - 1 |
工人3 | 0 | 0 | 0 |
具体调整如下:
- 工人1的第1列:2 - 1 = 1
- 工人1的第3列:2 - 1 = 1
- 工人2的第1列:1 - 1 = 0
- 工人2的第3列:5 - 1 = 4
交叉线的交点元素(工人3的第2列)加上1:
- 工人3的第2列:0 + 1 = 1
调整后的矩阵:
任务1 | 任务2 | 任务3 | |
---|---|---|---|
工人1 | 1 | 0 | 1 |
工人2 | 0 | 0 | 4 |
工人3 | 0 | 1 | 0 |
4. 再次划线覆盖零元素
现在我们再次用尽量少的直线覆盖所有的零元素:
- 一条线覆盖任务2列。
- 一条线覆盖工人2的行。
- 一条线覆盖工人3的行。
这次我们用3条直线覆盖了所有的零元素,直线数量等于矩阵的维度(3),说明我们已经找到了最优解。
5. 寻找最优匹配
优先选择那些行或列中只有一个零的元素进行匹配:
- 工人1的第2列:0
- 工人2的第1列:0
- 工人3的第3列:0
匹配结果:
- 工人1分配任务2
- 工人2分配任务1
- 工人3分配任务3
6. 计算最小成本
根据原始成本矩阵,计算匹配方案的总成本:
- 工人1 → 任务2,成本为
1
- 工人2 → 任务1,成本为
2
- 工人3 → 任务3,成本为
2
总成本:1 + 2 + 2 = 5
完整示例代码
import numpy as np
from scipy.optimize import linear_sum_assignment
# 成本矩阵
cost_matrix = np.array([
[4, 1, 3],
[2, 0, 5],
[3, 2, 2]
])
# 求解最优分配
row_ind, col_ind = linear_sum_assignment(cost_matrix)
# 输出结果
print("工人分配到任务的对应关系:")
for i, j in zip(row_ind, col_ind):
print(f"工人 {i + 1} 分配到任务 {j + 1}")
# 计算总成本
total_cost = cost_matrix[row_ind, col_ind].sum()
print(f"总成本: {total_cost}")
输出结果:
工人分配到任务的对应关系:
工人 1 分配到 任务 2
工人 2 分配到 任务 1
工人 3 分配到 任务 3
总成本: 5
例2:4个工人和3个任务(工人任务不匹配的情况)
当工人多于任务时,可以通过向矩阵添加虚拟任务来平衡工人和任务的数量。虚拟任务的成本可以设为0,以确保虚拟任务不会被实际分配。
假设我们有4个工人和3个任务,分配成本如下:
任务1 | 任务2 | 任务3 | |
---|---|---|---|
工人1 | 4 | 1 | 3 |
工人2 | 2 | 0 | 5 |
工人3 | 3 | 2 | 2 |
工人4 | 6 | 4 | 3 |
为了平衡,我们添加一个虚拟任务4,成本设为0:
任务1 | 任务2 | 任务3 | 任务4 (虚拟任务) | |
---|---|---|---|---|
工人1 | 4 | 1 | 3 | 0 |
工人2 | 2 | 0 | 5 | 0 |
工人3 | 3 | 2 | 2 | 0 |
工人4 | 6 | 4 | 3 | 0 |
1. 矩阵减法
行减法:
- 工人1:
4, 1, 3, 0
→4 - 0, 1 - 0, 3 - 0, 0 - 0
→4, 1, 3, 0
- 工人2:
2, 0, 5, 0
→2 - 0, 0 - 0, 5 - 0, 0 - 0
→2, 0, 5, 0
- 工人3:
3, 2, 2, 0
→3 - 0, 2 - 0, 2 - 0, 0 - 0
→3, 2, 2, 0
- 工人4:
6, 4, 3, 0
→6 - 0, 4 - 0, 3 - 0, 0 - 0
→6, 4, 3, 0
矩阵变为:
任务1 | 任务2 | 任务3 | 任务4 | |
---|---|---|---|---|
工人1 | 4 | 1 | 3 | 0 |
工人2 | 2 | 0 | 5 | 0 |
工人3 | 3 | 2 | 2 | 0 |
工人4 | 6 | 4 | 3 | 0 |
列减法:
- 任务1列:
4, 2, 3, 6
,最小值是2 - 任务2列:
1, 0, 2, 4
,最小值是0 - 任务3列:
3, 5, 2, 3
,最小值是2 - 任务4列:
0, 0, 0, 0
,最小值是0
减去每列的最小值:
- 任务1列:
4 - 2, 2 - 2, 3 - 2, 6 - 2
→2, 0, 1, 4
- 任务2列:
1 - 0, 0 - 0, 2 - 0, 4 - 0
→1, 0, 2, 4
- 任务3列:
3 - 2, 5 - 2, 2 - 2, 3 - 2
→1, 3, 0, 1
- 任务4列:
0 - 0, 0 - 0, 0 - 0, 0 - 0
→0, 0, 0, 0
调整后:
任务1 | 任务2 | 任务3 | 任务4 | |
---|---|---|---|---|
工人1 | 2 | 1 | 1 | 0 |
工人2 | 0 | 0 | 3 | 0 |
工人3 | 1 | 2 | 0 | 0 |
工人4 | 4 | 4 | 1 | 0 |
2. 划线覆盖零元素
通过观察,使用三条线就能覆盖所有零:
- 一条线覆盖任务4列。
- 一条线覆盖工人2的行。
- 一条线覆盖工人3的行。
3. 调整矩阵
最小未覆盖元素为 1
。对矩阵调整如下:
-
未被覆盖的元素减去最小值:
- 工人1的第1列:2 - 1 = 1
- 工人1的第2列:1 - 1 = 0
- 工人1的第3列:1 - 1 = 0
- 工人4的第1列:4 - 1 = 3
- 工人4的第2列:4 - 1 = 3
- 工人4的第3列:1 - 1 = 0
-
交点元素加最小值:
- 交点元素是被两条或多条直线同时覆盖的元素。在这个例子中,交点元素是:
- 工人2的第4列:0 + 1 = 1
- 工人3的第4列:0 + 1 = 1
- 交点元素是被两条或多条直线同时覆盖的元素。在这个例子中,交点元素是:
调整后的矩阵:
任务1 | 任务2 | 任务3 | 任务4 | |
---|---|---|---|---|
工人1 | 1 | 0 | 0 | 0 |
工人2 | 0 | 0 | 3 | 1 |
工人3 | 1 | 2 | 0 | 1 |
工人4 | 3 | 3 | 0 | 0 |
4. 再次划线覆盖零元素
现在我们再次用尽量少的直线覆盖所有的零元素:
- 一条线覆盖任务4列。
- 一条线覆盖工人1的行。
- 一条线覆盖工人2的行。
- 一条线覆盖工人3的行。
这次我们用4条直线覆盖了所有的零元素,直线数量等于矩阵的维度(4),说明我们已经找到了最优解。
5. 寻找最优匹配
优先选择那些行或列中只有一个零的元素进行匹配:
- 工人1的第2列:0
- 工人2的第1列:0
- 工人3的第3列:0
- 工人4的第4列:0
匹配结果:
- 工人1分配任务2
- 工人2分配任务1
- 工人3分配任务3
- 工人4分配任务4(虚拟任务)
6. 计算最小成本
根据原始成本矩阵,计算匹配方案的总成本:
- 工人1 → 任务2,成本为
1
- 工人2 → 任务1,成本为
2
- 工人3 → 任务3,成本为
2
- 工人4 → 任务4(虚拟任务),成本为
0
总成本:1 + 2 + 2 + 0 = 5
完整示例代码
import numpy as np
from scipy.optimize import linear_sum_assignment
# 成本矩阵
cost_matrix = np.array([
[4, 1, 3, 0],
[2, 0, 5, 0],
[3, 2, 2, 0],
[6, 4, 3, 0]
])
# 求解最优分配
row_ind, col_ind = linear_sum_assignment(cost_matrix)
# 输出结果
print("工人分配到任务的对应关系:")
for i, j in zip(row_ind, col_ind):
if j < 3:
print(f"工人 {i + 1} 分配到任务 {j + 1}")
else:
print(f"工人 {i + 1} 未分配实际任务")
# 计算总成本
total_cost = cost_matrix[row_ind, col_ind].sum()
print(f"总成本: {total_cost}")
输出结果:
工人分配到任务的对应关系:
工人 1 分配到任务 2
工人 2 分配到任务 1
工人 3 分配到任务 3
工人 4 未分配实际任务
总成本: 5
注意事项
- 匈牙利算法适用于最小化问题:匈牙利算法主要用于最小化成本或代价。如果问题是最大化问题(如求取IOU最大匹配问题),则需要进行适当的转换,例如将最大化问题转换为最小化问题。
- 调整矩阵:如果直线数量少于矩阵的维度,调整矩阵以增加零的数量,直到找到最优解。
有趣的网站
可以使用以下网站来实验自己的例子,验证匈牙利算法的结果以及中间过程:
- Hungarian Algorithm Calculator
Code
AI_With_NumPy
此项目汇集了更多AI相关的代码实现,供大家学习使用,欢迎点赞收藏👏🏻
备注
个人水平有限,有问题随时交流~