图论（16）匈牙利算法与最优匹配算法实战解析

1. 匈牙利算法偶图匹配的魔法棒第一次听说匈牙利算法时我误以为它和匈牙利这个国家有什么关系。后来才知道这个算法之所以叫这个名字是因为它基于匈牙利数学家Dénes Kőnig的定理。不过名字不重要重要的是它确实像魔法棒一样能轻松解决偶图中的匹配问题。什么是偶图简单来说偶图就是把图中的顶点分成两组所有边都连接两组中的顶点组内顶点不相连。比如相亲活动现场男生一组女生一组每个人只和异性配对这就是典型的偶图模型。匈牙利算法的核心思想可以用一个生活场景来理解假设你是个红娘手头有几位单身男女他们之间有些互相有好感存在边有些则没有。你的任务是尽可能多地促成配对且每个人只能配对一次。这时候匈牙利算法就是你的最佳助手。1.1 增广路径算法的灵魂我第一次实现匈牙利算法时最困惑的就是这个增广路径概念。后来发现它其实很简单——就是一条起点和终点都未匹配的路径路径上的边交替出现在匹配和非匹配中。举个例子假设当前匹配是A-1和B-2字母代表男生数字代表女生现在发现路径C-1-A-2C-1是非匹配边1-A是匹配边A-2是非匹配边这条路径就是增广路径。对它进行操作把匹配边变非匹配边非匹配边变匹配边就能得到更大的匹配C-1和A-2。def find_augmenting_path(graph, u, match_to, visited): for v in graph[u]: if not visited[v]: visited[v] True if match_to[v] -1 or find_augmenting_path(graph, match_to[v], match_to, visited): match_to[v] u return True return False def hungarian(graph, num_vertices): match_to [-1] * num_vertices result 0 for u in range(num_vertices): visited [False] * num_vertices if find_augmenting_path(graph, u, match_to, visited): result 1 return result1.2 实战任务分配问题去年我帮朋友公司解决过一个实际任务分配问题有5个项目和5个工程师每个工程师有擅长的项目。用匈牙利算法可以完美解决构建偶图工程师是一组顶点项目是另一组添加边工程师擅长某个项目就添加边运行匈牙利算法最终得到的最大匹配就是最优分配方案。记得当时有个工程师特别抢手三个项目都想要他算法很好地平衡了这种冲突。2. 库恩算法带权匹配的最优解匈牙利算法解决了能不能匹配的问题但现实中我们更常遇到的是怎样匹配更好的问题。比如不仅考虑能不能做还要考虑做得好不好这时候就需要库恩算法Kuhn-Munkres算法。2.1 可行顶点标号算法的基石库恩算法最巧妙的部分就是可行顶点标号。这个概念听起来高大上其实就像给每个人贴标签对左边的顶点比如员工标签是他们的最高能力值对右边的顶点比如任务标签初始为0这些标签需要满足对于任何边两端的标签和 ≥ 边的权重。这就像说员工能力任务基础分 ≥ 实际得分。def initialize_labels(graph, label_u, label_v): # 初始化左部顶点标号为相连边的最大权值 for u in range(len(graph)): label_u[u] max(graph[u]) if graph[u] else 0 label_v[:] [0] * len(label_v)2.2 相等子图关键转换有了可行标号后我们构建相等子图——只保留那些满足标签和边权的边。神奇的是这个子图中的完美匹配就是原图的最佳匹配这就像在相亲中我们只考虑综合评分相等的组合男方自我评分女方自我评分他们之间的匹配度这样的组合一定是最优的。2.3 实战项目奖金分配我曾用库恩算法解决过一个项目奖金分配问题。公司有5个项目完成不同项目组合的奖金不同如何分配项目使总奖金最大构建完全偶图员工vs项目边权就是奖金数额运行库恩算法算法不仅找到了最大奖金分配方案还通过标号的调整过程直观展示了为什么这样分配最优。3. 算法实现中的坑与技巧3.1 匈牙利算法的优化原始匈牙利算法的时间复杂度是O(n³)在大规模数据下会很慢。经过实践我发现这些优化很有效DFS改为BFS用队列实现避免递归深度过大贪心初始匹配先快速找到一个初始匹配减少后续处理邻接表优化对于稀疏图特别有效def hungarian_bfs(graph): n len(graph) match_to [-1] * n result 0 for u in range(n): if match_to[u] ! -1: continue prev [-1] * n root u queue [root] found False while queue and not found: v queue.pop(0) for to in graph[v]: if prev[to] -1 and to ! root: prev[to] v if match_to[to] -1: found True break queue.append(match_to[to]) if found: result 1 while v ! -1: match_to[v], v prev[v], match_to[prev[v]] return result3.2 库恩算法的注意事项实现库恩算法时我踩过几个坑标号调整要小心每次只能调整S中的左顶点和T中的右顶点slack数组的维护这是算法效率的关键浮点数精度问题对于浮点权重要特别处理4. 从理论到实践经典例题解析4.1 例题1棋盘覆盖问题描述在一个N×N的棋盘上有些格子被禁止放置。问最多能放多少个1×2的多米诺骨牌解法将棋盘黑白染色黑色格子作为左部顶点白色作为右部顶点。相邻且未被禁止的格子间连边然后求最大匹配。def max_dominoes(N, forbidden): # 构建邻接表 graph [[] for _ in range(N*N)] directions [(0,1),(1,0),(0,-1),(-1,0)] for i in range(N): for j in range(N): if (i,j) in forbidden: continue u i*N j for di,dj in directions: ni, nj idi, jdj if 0niN and 0njN and (ni,nj) not in forbidden: v ni*N nj graph[u].append(v) return hungarian_bfs(graph) // 24.2 例题2最优任务分配有N个工人和N个任务每个工人完成不同任务的效率不同。如何分配使总效率最高解法这就是典型的加权二分图匹配问题直接用库恩算法解决。我曾经用这个问题测试不同实现方式的性能发现对于N500的情况优化后的库恩算法能在1秒内解决而暴力方法可能需要几个小时。