匈牙利算法详解（Python实现任务分配与最优匹配）

什么是匈牙利算法？

匈牙利算法是一种用于解决分配问题（Assignment Problem）的组合优化算法。它由 Harold Kuhn 在1955年提出，基于两位匈牙利数学家的工作而得名。

简单来说，假设你有一个 n×n 的成本矩阵，其中每个元素 cost[i][j] 表示将第 i 个任务分配给第 j 个工人的成本。目标是找到一种分配方式，使得每个任务只分配给一个工人，每个工人只接受一个任务，并且总成本最小。

算法基本思想

匈牙利算法的核心思想是通过对成本矩阵进行行和列的变换（减去最小值），使得矩阵中出现足够多的“零”，然后尝试用这些零构造一个最优匹配。

主要步骤如下：

1. 对每一行，减去该行的最小值；
2. 对每一列，减去该列的最小值；
3. 用最少的横线或竖线覆盖所有零；
4. 如果线的数量等于矩阵阶数 n，则找到了最优解；否则，调整矩阵并重复步骤3。

Python 实现匈牙利算法

虽然我们可以手动实现完整算法，但 Python 的 scipy 库已经提供了高效、稳定的实现。下面我们将先展示如何使用 scipy.optimize.linear_sum_assignment，再简要介绍手动实现的关键逻辑。

方法一：使用 scipy（推荐）

from scipy.optimize import linear_sum_assignmentimport numpy as np# 定义成本矩阵（例如：4个任务分配给4个工人）cost_matrix = np.array([    [4, 1, 3, 2],    [2, 0, 5, 3],    [3, 2, 2, 3],    [1, 3, 4, 2]])# 调用匈牙利算法row_indices, col_indices = linear_sum_assignment(cost_matrix)# 输出结果print("任务分配方案：")for i in range(len(row_indices)):    print(f"任务 {row_indices[i]} → 工人 {col_indices[i]}")print("\n最小总成本：", cost_matrix[row_indices, col_indices].sum())

运行上述代码，你将得到类似以下的输出：

任务分配方案：任务 0 → 工人 1任务 1 → 工人 0任务 2 → 工人 2任务 3 → 工人 3最小总成本： 5

方法二：手动实现（简化版）

为了帮助理解，这里给出一个简化版的手动实现（适用于教学目的，不建议用于生产环境）：

def hungarian_algorithm(cost_matrix):    n = len(cost_matrix)    # 步骤1：行减最小值    for i in range(n):        min_val = min(cost_matrix[i])        for j in range(n):            cost_matrix[i][j] -= min_val        # 步骤2：列减最小值    for j in range(n):        col_min = min(cost_matrix[i][j] for i in range(n))        for i in range(n):            cost_matrix[i][j] -= col_min        # 注意：完整实现需包含“覆盖零”和“调整矩阵”步骤    # 此处仅为演示思路，实际匹配需更复杂逻辑    return cost_matrix# 示例调用（仅展示矩阵变换）matrix = [[4, 1, 3, 2],          [2, 0, 5, 3],          [3, 2, 2, 3],          [1, 3, 4, 2]]result = hungarian_algorithm([row[:] for row in matrix])  # 深拷贝print("变换后的矩阵：")for row in result:    print(row)

⚠️ 注意：完整的手动实现非常复杂，涉及图论中的增广路径等概念。因此，在实际项目中，强烈建议使用 scipy 等成熟库。

应用场景

• 任务分配：如调度系统、作业分配；
• 最优匹配：如婚恋匹配、学生-导师配对；
• 计算机视觉中的特征点匹配；
• 物流中的车辆-订单分配。

总结

通过本文，你已经了解了匈牙利算法的基本原理，并学会了如何用Python实现来解决任务分配和最优匹配问题。记住，在实际开发中优先使用 scipy 提供的函数，既高效又可靠。

希望这篇教程能帮助你迈出算法应用的第一步！如果你有任何疑问，欢迎在评论区留言交流。