匈牙利算法

匈牙利算法（Hungarian Algorithm），也称为Kuhn-Munkres算法，是一种经典的算法，用于解决二分图的最大匹配问题。 它通过迭代地寻找增广路径来找到最优的匹配方案，具有时间复杂度为 $O(n^3)$ 的特点。

匈牙利算法的基本原理

基本概念

二分图（Bipartite Graph）是指其顶点可以分为两个不相交的子集，且每条边连接不同子集中的顶点。最大匹配（Maximum Matching）是指图中边的最大数目，使得没有两条边共享一个顶点。

匈牙利算法通过增加匹配路径来找到最优的匹配方案。增广路径是指一条从未被匹配的顶点开始，交错地经过已匹配和未匹配的边，直到到达另一个未被匹配的顶点的路径。

算法步骤

1. 初始化：为每个顶点分配一个标签（label），表示当前可匹配的最大权重。初始时，所有顶点的标签设为0。
2. 寻找增广路径：
3. 从一个未被匹配的顶点 $v$ 开始。
4. 遍历 $v$ 的邻接顶点 $u$，如果 $u$ 未被匹配，则找到一条增广路径并更新标签。
5. 如果 $u$ 已被匹配，遍历 $u$ 的匹配伙伴 $w$，递归地寻找增广路径并更新标签。
6. 更新匹配：
7. 根据找到的增广路径更新匹配。对于每条增广路径，将未匹配的顶点与匹配伙伴进行配对，将已匹配的顶点与新的匹配伙伴进行配对。
8. 重复：重复寻找增广路径和更新匹配的过程，直到所有顶点都被匹配或无法找到更多的增广路径。

匈牙利算法的数学公式

标签更新公式

在寻找增广路径的过程中，为每个顶点分配一个标签（label），表示当前可匹配的最大权重。标签的更新规则如下： $$\text{label}[v] = \min_{u \in N(v), u \not\in M} \text{weight}(v, u) - \max_{w \in M(u)} \text{label}[w]$$

其中，$v$ 是当前顶点，$N(v)$ 是 $v$ 的邻接顶点集合，$M(u)$ 是顶点 $u$ 在匹配 $M$ 中的匹配伙伴集合。

匹配更新公式

在找到增广路径后，根据路径上的顶点更新匹配。具体步骤如下： - 遍历增广路径上的每条边，将未匹配的顶点与匹配伙伴进行配对，将已匹配的顶点与新的匹配伙伴进行配对。 - 更新匹配 $M$ 为当前的匹配状态。

应用场景

匈牙利算法在多个领域有着广泛的应用，包括但不限于：

1. 任务分配：如车间调度、资源分配等。
2. 最佳匹配问题：如员工与职位的最佳匹配。
3. 图像处理：如图的分割和配对。

通过理解匈牙利算法的基本原理和数学公式，我们可以更好地解决二分图的最大匹配问题，并将其应用于实际场景中。