匈牙利算法详解与实现
匈牙利算法是一种高效的二分图最大匹配或最优分配算法，常用于解决任务分配问题，例如将工人分配给任务以最小化成本。该算法通过多步矩阵操作和调整来寻找最优匹配，保证了分配成本的最小化。
算法概述
1. 矩阵减法
首先对矩阵进行行列减法：
- 行减法：每行减去该行的最小值，使每行至少有一个零。
- 列减法：在行减法的基础上，每列再减去该列的最小值，使每列至少有一个零。
2. 划线覆盖零元素
用尽量少的直线（横线或竖线）覆盖矩阵中的所有零元素。如果划线数量等于矩阵维度，则已找到最优解，否则进入下一步。
3. 调整矩阵
找到未被线覆盖的最小元素并调整矩阵：
- 未被覆盖的元素减去最小值。
- 交叉线的交点元素加上最小值。
- 其他已被线覆盖的元素保持不变。
4. 寻找匹配
使用调整后的矩阵寻找最优匹配。优先选择那些行或列中只有一个零的元素进行匹配。
5. 计算最小成本
根据原始成本矩阵，计算匹配方案的总成本。
例子：工人与任务分配问题
假设有3个工人和3个任务，分配成本如下：
| 任务1 | 任务2 | 任务3 | |
|---|---|---|---|
| 工人1 | 4 | 1 | 3 |
| 工人2 | 2 | 0 | 5 |
| 工人3 | 3 | 2 | 2 |
1. 行和列减法
行减法：
- 工人1：
4, 1, 3→0, 1, 0 - 工人2：
2, 0, 5→0, 0, 5 - 工人3：
3, 2, 2→0, 2, 2
矩阵变为：
| 任务1 | 任务2 | 任务3 | |
|---|---|---|---|
| 工人1 | 0 | 1 | 0 |
| 工人2 | 0 | 0 | 5 |
| 工人3 | 0 | 2 | 2 |
列减法：
- 任务1列不变：
0, 0, 0 - 任务2列不变：
1, 0, 2 - 任务3列不变：
0, 5, 2
调整后：
| 任务1 | 任务2 | 任务3 | |
|---|---|---|---|
| 工人1 | 0 | 1 | 0 |
| 工人2 | 0 | 0 | 5 |
| 工人3 | 0 | 2 | 2 |
2. 划线覆盖零元素
通过观察，使用两条线就能覆盖所有零：
- 一条线覆盖任务1列。
- 一条线覆盖工人2的行。
3. 调整矩阵
最小未覆盖元素为 1。对矩阵调整如下：
- 未被覆盖的元素减去
1。 - 交点元素加
1。
调整后矩阵：
| 任务1 | 任务2 | 任务3 | |
|---|---|---|---|
| 工人1 | 1 | 0 | 1 |
| 工人2 | 0 | 0 | 4 |
| 工人3 | 0 | 1 | 1 |
4. 寻找最优匹配
开始匹配：
- 工人1分配任务2，删除该行列。
- 工人2分配任务1，删除该行列。
- 工人3分配任务3。
5. 计算最小总成本
总成本为：
- 工人1 → 任务2，成本为
1 - 工人2 → 任务1，成本为
2 - 工人3 → 任务3，成本为
2
总成本：1 + 2 + 2 = 5
Python实现
使用 scipy 库的 linear_sum_assignment 方法快速实现匈牙利算法。
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
工人多于任务的情况
当工人多于任务时，可以通过向矩阵添加虚拟任务来平衡工人和任务的数量。虚拟任务的成本可以设为0或极大值，以确保虚拟任务不会被实际分配。
例如，4个工人和3个任务的成本矩阵如下：
| 任务1 | 任务2 | 任务3 | |
|---|---|---|---|
| 工人1 | 4 | 1 | 3 |
| 工人2 | 2 | 0 | 5 |
| 工人3 | 3 | 2 | 2 |
| 工人4 | 6 | 4 | 3 |
为了平衡，添加虚拟任务4，矩阵变为：
| 任务1 | 任务2 | 任务3 | 任务4 (虚拟任务) | |
|---|---|---|---|---|
| 工人1 | 4 | 1 | 3 | 0 |
| 工人2 | 2 | 0 | 5 | 0 |
| 工人3 | 3 | 2 | 2 | 0 |
| 工人4 | 6 | 4 | 3 | 0 |
调整后可继续使用匈牙利算法进行求解。
Code
AI_With_NumPy
此项目汇集了更多AI相关的代码实现，供大家学习使用，欢迎点赞收藏👏🏻
备注
个人水平有限，有问题随时交流~