匈牙利算法详解与实现

匈牙利算法是一种高效的二分图最大匹配或最优分配算法，常用于解决任务分配问题，例如将工人分配给任务以最小化成本。该算法通过多步矩阵操作和调整来寻找最优匹配，保证了分配成本的最小化。

算法概述

1. 矩阵减法

首先对矩阵进行行列减法：

• 行减法：每行减去该行的最小值，使每行至少有一个零。
• 列减法：在行减法的基础上，每列再减去该列的最小值，使每列至少有一个零。

2. 划线覆盖零元素

用尽量少的直线（横线或竖线）覆盖矩阵中的所有零元素。如果划线数量等于矩阵维度，则已找到最优解，否则进入下一步。

3. 调整矩阵

找到未被线覆盖的最小元素并调整矩阵：

• 未被覆盖的元素减去最小值。
• 交叉线的交点元素加上最小值。
• 其他已被线覆盖的元素保持不变。

4. 寻找匹配

使用调整后的矩阵寻找最优匹配。优先选择那些行或列中只有一个零的元素进行匹配。

5. 计算最小成本

根据原始成本矩阵，计算匹配方案的总成本。

工人与任务分配问题

例1：3个工人和3个任务（工人任务匹配的情况）

假设有3个工人和3个任务，分配成本如下：

1. 行和列减法

行减法：

• 工人1：4, 1, 3 → 3, 0, 2
• 工人2：2, 0, 5 → 2, 0, 5
• 工人3：3, 2, 2 → 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

调整后：

2. 划线覆盖零元素

通过观察，使用两条线就能覆盖所有零：

• 一条线覆盖任务2列。
• 一条线覆盖工人3的行。

3. 调整矩阵

最小未覆盖元素为 1。对矩阵调整如下：

• 未被覆盖的元素减去 1。
• 交点元素加 1。

调整后矩阵：

具体调整如下：

• 工人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

调整后的矩阵：

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个任务，分配成本如下：

为了平衡，我们添加一个虚拟任务4，成本设为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列：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

调整后：

2. 划线覆盖零元素

通过观察，使用三条线就能覆盖所有零：

• 一条线覆盖任务4列。
• 一条线覆盖工人2的行。
• 一条线覆盖工人3的行。

3. 调整矩阵

最小未覆盖元素为 1。对矩阵调整如下：

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. 交点元素加最小值：

   • 交点元素是被两条或多条直线同时覆盖的元素。在这个例子中，交点元素是：
     • 工人2的第4列：0 + 1 = 1
     • 工人3的第4列：0 + 1 = 1

调整后的矩阵：

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相关的代码实现，供大家学习使用，欢迎点赞收藏👏🏻

备注

个人水平有限，有问题随时交流~