匈牙利算法简介：从二分图匹配到任务分配

发表于 分类于

匈牙利算法（Hungarian Algorithm）是组合优化领域最经典的算法之一，用于解决两类核心问题：二分图最大匹配和任务分配问题。它由匈牙利数学家 Dénes Kőnig 和 Jenő Egerváry 的理论奠基，后由 Harold Kuhn 于 1955 年正式提出。

什么是二分图？

在深入算法之前，我们需要先理解几个基本概念。

二分图（Bipartite Graph）是一种特殊的图结构，它的顶点可以被划分为两个互不相交的集合 U 和 V，使得图中的每一条边都连接 U 中的一个顶点和 V 中的一个顶点。

简单来说：二分图中的边只会”跨界”连接，不会在同一个集合内部连接。

匹配（Matching）是指图中一组没有公共顶点的边。换句话说，每个顶点最多只被一条边选中。

最大匹配就是包含边数最多的匹配。

匈牙利算法（二分图匹配版）

这是最常见的”匈牙利算法”，用于求解二分图的最大匹配。

核心思想：增广路

匈牙利算法的核心定理是 Berge 增广路定理：

一个匹配是最大匹配，当且仅当图中不存在增广路。

增广路（Augmenting Path）的定义：

  • 路径的起点和终点都是未匹配的顶点
  • 路径上的边交替出现”未匹配边”和”已匹配边”

增广路有一个神奇的性质：如果我们将增广路上所有边的状态取反（匹配变未匹配，未匹配变匹配），匹配的边数会增加 1。

算法步骤

1
2
3
4
5
6
1. 初始化匹配为空
2. 对于每个未匹配的左部顶点 u：
   a. 从 u 开始搜索增广路（DFS/BFS）
   b. 如果找到增广路，翻转路径上的边，匹配数 +1
   c. 否则，u 无法匹配
3. 重复直到所有顶点都尝试过

Python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def hungarian_bipartite(graph, n_left, n_right):
    """
    graph: 邻接表，graph[u] = [v1, v2, ...] 表示左部顶点 u 可以匹配右部的 v1, v2...
    n_left: 左部顶点数
    n_right: 右部顶点数
    返回: 最大匹配数
    """
    match_right = [-1] * n_right  # 右部顶点的匹配对象
    visited = [False] * n_right
    
    def dfs(u):
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                # 如果 v 未匹配，或者可以为 match_right[v] 找到新的匹配
                if match_right[v] == -1 or dfs(match_right[v]):
                    match_right[v] = u
                    return True
        return False
    
    count = 0
    for u in range(n_left):
        visited = [False] * n_right
        if dfs(u):
            count += 1
    return count

# 示例：4 个男生，4 个女生，边的关系如下
graph = {
    0: [0, 1],      # 男生 0 可以和女生 0, 1 匹配
    1: [1, 2],      # 男生 1 可以和女生 1, 2 匹配
    2: [2, 3],      # 男生 2 可以和女生 2, 3 匹配
    3: [3],         # 男生 3 可以和女生 3 匹配
}
print(hungarian_bipartite(graph, 4, 4))  # 输出: 4（完美匹配）

匈牙利算法（任务分配版）

另一种”匈牙利算法”用于解决带权二分图的最小/最大权匹配问题，也称为 Kuhn-Munkres 算法 或 分配问题算法。

问题描述

有 n 个工人和 n 项任务，每个工人完成每项任务的成本不同。如何分配才能使总成本最小？

这就是经典的任务分配问题，可以用一个 n×n 的代价矩阵表示。

算法步骤

1
2
3
4
5
1. 每行减去该行的最小值
2. 每列减去该列的最小值
3. 用最少的线覆盖所有零
   - 如果线数 = n，找到最优分配，算法结束
   - 否则，调整矩阵，返回步骤 3

时间复杂度

任务分配版的匈牙利算法时间复杂度为 **O(n³)**，在多项式时间内解决了这个组合优化问题。

应用场景

场景 算法版本 说明
红娘匹配 二分图匹配 男女配对，使配对数最大
任务分配 任务分配版 工人-任务最优分配
航班-登机口分配 任务分配版 最小化总等待时间
目标跟踪 任务分配版 多目标与多检测的最优关联
课程安排 二分图匹配 教师-教室-时间匹配

复杂度分析

  • 二分图匹配版：O(V×E)，其中 V 是顶点数，E 是边数
  • 任务分配版：O(n³)，其中 n 是矩阵维度

总结

匈牙利算法虽然有两个不同的版本，但它们都源于同一个数学理论：二分图的完美匹配理论。理解增广路的概念是掌握这个算法的关键。

无论是简单的二分图匹配，还是复杂的任务分配问题，匈牙利算法都提供了一个优雅且高效的解决方案。

延伸阅读：

  • 《算法导论》第 26 章：最大流
  • Harold W. Kuhn, “The Hungarian Method for the Assignment Problem” (1955)
  • 网络流算法（Dinic、Edmonds-Karp）