匈牙利算法（Hungarian Algorithm）是解决二分图最小权匹配问题（也称分配问题，Assignment Problem）的经典组合优化算法。它由 Harold Kuhn 于 1955 年提出，其思想源于两位匈牙利数学家 Dénes Kőnig 和 Jenő Egerváry 的早期工作，因此得名。
下面我将从问题背景、核心思想、算法步骤、数学原理和一个完整示例五个方面，系统地为你讲解匈牙利算法的工作原理。
一、问题背景：什么是分配问题？
设有 ( n ) 个工人和 ( n ) 项任务，每个工人完成每项任务都有一个成本 ( c_{ij} )（例如时间、金钱等）。目标是为每个工人分配唯一一项任务，使得总成本最小。
这可以建模为一个 ( n \times n ) 的成本矩阵 ( C = [c_{ij}] )，我们要找一个排列 ( \sigma \in S_n )（即一一对应），使得：
[ \min \sum{i=1}^n c{i,\sigma(i)} ]
这就是最小权完美匹配问题，在完全二分图 ( K_{n,n} ) 上求解。
✅ 匈牙利算法可在 ( O(n^3) ) 时间内精确求解该问题。
二、核心思想：利用“可行顶标”与“相等子图”
匈牙利算法基于 Kőnig–Egerváry 定理，其关键洞察是：
最小权匹配的总成本 = 最大对偶变量之和
（即原问题与对偶问题的最优值相等）
为此，算法引入两个“顶标”（labels）：
- 对每个工人 ( i )，赋予顶标 ( u_i )
- 对每个任务 ( j )，赋予顶标 ( v_j )
要求满足 可行性条件： [ u_i + vj \leq c{ij}, \quad \forall i,j ]
定义 相等子图（Equality Subgraph）：仅保留满足 ( u_i + vj = c{ij} ) 的边。
🎯 目标：调整顶标，使得相等子图中存在一个完美匹配。一旦找到，该匹配即为最优解。
三、算法步骤（以最小化成本为例）
我们以成本矩阵 ( C ) 为输入，逐步构造最优匹配。
步骤 0：初始化顶标
- ( u_i = \minj c{ij} )（每行最小值）
- ( v_j = 0 )
这样保证 ( u_i + vj \leq c{ij} ) 成立。
步骤 1：构造相等子图
- 保留所有满足 ( u_i + vj = c{ij} ) 的边。
步骤 2：在相等子图中寻找最大匹配
- 使用 DFS 或 BFS 尝试增广路径。
- 若找到完美匹配（大小为 ( n )），算法结束，输出匹配。
步骤 3：若未找到完美匹配，则调整顶标
设当前匹配为 ( M )，从所有未匹配的工人出发，在相等子图中进行交替树搜索（类似匈牙利树）：
- 令 ( S ) = 已访问的工人集合
- 令 ( T ) = 已访问的任务集合
计算： [ \delta = \min{i \in S,\, j \notin T} (c{ij} - u_i - v_j) > 0 ]
然后更新顶标：
- ( u_i \leftarrow u_i + \delta )，对所有 ( i \in S )
- ( v_j \leftarrow v_j - \delta )，对所有 ( j \in T )
🔁 这一操作会新增至少一条边进入相等子图，同时保持可行性。
重复步骤 1–3，直到找到完美匹配。
四、更直观的“矩阵约简”版本（教学常用）
实际教学中，常使用以下等价的矩阵操作流程（适用于手算）：
第 1 步：行约简
每行减去该行最小值。
第 2 步：列约简
每列减去该列最小值。
此时矩阵中出现若干 0，目标是在 0 元素中选出 ( n ) 个互不同行不同列的 0（即独立零元素）。
第 3 步：试指派
用最少的横线（行或列）覆盖所有 0。
- 若所需直线数 = ( n )，则可找到完美匹配，结束。
- 否则，进入下一步。
第 4 步：调整矩阵
- 找出未被覆盖的最小元素 ( \delta )；
- 未被覆盖的行减去 ( \delta )；
- 被覆盖的列加上 ( \delta )；
（这等价于顶标调整）
返回第 3 步，直到能用 ( n ) 条线覆盖所有 0。
五、完整示例
考虑成本矩阵：
[ C = \begin{bmatrix} 9 & 2 & 7 & 8 \ 6 & 4 & 3 & 7 \ 5 & 8 & 1 & 8 \ 7 & 6 & 9 & 4 \ \end{bmatrix} ]
第 1 步：行约简（每行减最小值）
- 行1 min=2 → [7, 0, 5, 6]
- 行2 min=3 → [3, 1, 0, 4]
- 行3 min=1 → [4, 7, 0, 7]
- 行4 min=4 → [3, 2, 5, 0]
得到：
[ \begin{bmatrix} 7 & 0 & 5 & 6 \ 3 & 1 & 0 & 4 \ 4 & 7 & 0 & 7 \ 3 & 2 & 5 & 0 \ \end{bmatrix} ]
第 2 步：列约简（每列减最小值）
各列最小值：[3, 0, 0, 0] → 只需第1列减3：
[ \begin{bmatrix} 4 & 0 & 5 & 6 \ 0 & 1 & 0 & 4 \ 1 & 7 & 0 & 7 \ 0 & 2 & 5 & 0 \ \end{bmatrix} ]
第 3 步：试指派（找独立 0）
尝试选 0：
- (2,1), (1,2), (3,3), (4,4) → 恰好 4 个，互不冲突！
✅ 找到完美匹配！
对应原矩阵位置：
- 工人1 → 任务2（成本 2）
- 工人2 → 任务1（成本 6）
- 工人3 → 任务3（成本 1）
- 工人4 → 任务4（成本 4）
总成本 = ( 2 + 6 + 1 + 4 = 13 )
六、总结
匈牙利算法的本质是通过“对偶变量调整”逐步扩大相等子图，直到其中包含完美匹配。
- 时间复杂度：( O(n^3) )
- 空间复杂度：( O(n^2) )
- 应用广泛：任务分配、多目标跟踪（如 SORT/DeepSORT 中的数据关联）、运筹学、经济学等。
如果你希望看到 Python 实现（如使用 scipy.optimize.linear_sum_assignment），或者想了解如何处理非方阵或最大化问题，我也可以进一步补充。
文章评论