最烦的一种场景是你手上明明有完整的成本表格任务和人一一对应可你就是找不到一个让人人都满意、总成本又最低的分配方案。订单排期、工位分配、维修任务派单全是这类问题。指派问题就是这么来的而匈牙利算法是解决它最经典、最高效的算法没有之一。我用一个最小化的指派问题说明n 个人做 n 件事每人做每件事的成本不一样每个人只能做一件每件事也只能由一个人做怎样让总成本最低。匈牙利算法的整个流程看起来像一堆矩阵变换看起来很“魔法”但只要把每一步为什么这么做拆开它其实非常朴素。这篇内容适合运筹学初学者、做调度系统开发的工程师、准备算法面试的人尤其是那些想真正理解匈牙利算法而不是只会调库的读者。我会从数学模型讲起用一个 4×4 实例完整手算一遍再给出可以直接抄的 Python 实现和实际项目里最常见的坑。1. 指派问题到底在解什么先花五分钟把数学模型建起来1.1 从“几个人分几件事”到代价矩阵假设你有 4 名员工甲、乙、丙、丁4 项任务 A、B、C、D员工做不同任务的成本不完全相同可能是工时、物料成本或者运输距离。把这些成本写成一个矩阵员工任务A任务B任务C任务D甲5798乙6487丙7596丁8675这个矩阵就是代价矩阵通常记作 c[i][j]表示第 i 个人做第 j 件事的成本。我们的目标是找一组一一对应的分配使所有 c[i][p[i]] 之和最小p[i] 表示第 i 个人被分配到的任务编号。更形式化地说指派问题是一个 0-1 整数规划x[i][j] 1 表示把任务 j 分配给员工 i否则为 0。约束是每行每列有且仅有一个 1目标是最小化 Σc[i][j]·x[i][j]。这组约束看起来不起眼但它是后面所有推导的基础。1.2 为什么不能用穷举硬算4×4 还好说4! 24 种排列笔算都可以。但如果变成 10 个人 10 件事排列数是 10! 3628800 种到 15 个人15! 大概是 1.3 万亿种。等排到 20 个人普通计算机已经很难在合理时间内跑完了。这也是指派问题真正的难点解空间按阶乘增长但问题的结构又足够特殊不需要像通用整数规划那样大动干戈。1955 年 Kuhn 提出的匈牙利算法正是利用了“每一行每一列同时减去一个常数不会改变最优解”这个性质把问题一步步简化最终把复杂度压到 O(n³)。O(n³) 是什么概念n 1000 时大约是 10 亿次基本运算现代计算机在单线程下也就是秒级到十几秒完全可接受。这就是为什么在排班、资源分配这类系统里匈牙利算法几乎是标配。1.3 匈牙利算法的适用边界不是所有分配问题都适合直接用匈牙利算法它的限制要先说清楚要求人或任务两边数量能对齐通常整理成 n×n 方阵非方阵需要补虚拟行/列。目标函数是线性求和不考虑两个人协作、任务先后顺序这类复杂约束。成本矩阵可以理解为二分图边权本质上是求二分图的最优完美匹配。如果你的问题带有优先级、容量限制、互斥关系那它可能不是单纯的指派问题而是需要建更复杂模型的调度问题。但如果核心就是“一一配对、总成本最小”匈牙利算法就是最合适的选择。2. 算法核心思想行列归约为什么不会破坏最优解2.1 归约的数学本质换了个等价问题匈牙利算法第一步是行归约每一行都减去该行的最小值第二步是列归约每一列都减去该列的最小值。很多教程直接说“每行减去最小数”但没说为什么可以这么干。关键性质在这里把某一行所有元素同时减去一个常数 k不会改变这一行的“相对大小”因此也不会改变包含这一行的任何一个可行方案的比较结果。比如甲做任务 A 成本 5做任务 B 成本 7两者之差是 2整行减去 5 后变成 0 和 2差值还是 2。穷举所有排列时甲的选择差异完全不变。列归约的道理一样不过是把视角换成“任务这边”。这个性质在数学上等价于代价矩阵加减行向量和列向量后所有方案的总成本会相差一个固定常数所以最优解不变。这一点是整个算法的基石也是很多人第一次接触时最容易忽略的地方。经过行列归约后矩阵保证每一行每一列至少有一个 0。我们不再盯原始成本而是盯这些 0 元素如果能从每行每列各挑出一个 0就找到了当前等价问题下的最优指派。2.2 独立零元素与最优指派的关系“每行每列各挑一个 0”不是随便挑要求是选出的 n 个 0 两两不同行、两两不同列这叫独立零元素组也对应二分图里的一个完美匹配。为什么挑出 n 个独立 0 就完事了因为归约后的矩阵所有元素都非负任意方案的总成本一定大于等于 0。如果存在一个方案能选到 n 个独立 0那它的成本就是 0而 0 已经是理论下界不可能有比它更小的方案。所以找到 n 个独立零元素就等于找到了最优解。但现实往往没那么顺利。归约之后矩阵里的 0 可能很多也可能扎堆在同一列。比如某个任务特别“便宜”所有人做它都是 0那这列有 n 个 0其他列一个也没有根本凑不出 n 个独立 0。这就是匈牙利算法后续步骤要解决的问题不断制造新 0直到能凑齐 n 个独立零元素。2.3 标准流程四步总览在动手算之前先把完整流程立起来后面每一步都会对号入座行归约每行减去该行最小值。列归约每列减去该列最小值保证每行每列都有 0。试指派在 0 元素中找独立零元素组也就是找最大匹配。调整矩阵如果独立零元素不足 n 个用最少数量的直线覆盖所有 0再从未被覆盖的元素中找最小值 k对未覆盖行减 k、对已覆盖列加 k产生新 0重复第 3、4 步直到找出 n 个独立零元素。第 4 步里“覆盖所有 0 的最少直线数”由 Kőnig 定理保证二分图里最大匹配数等于最小点覆盖数。当最小覆盖线数小于 n说明还能靠调整增加匹配当覆盖线数等于 n匹配就是完美的。3. 一个4×4算例的手算全过程每一步矩阵都摆出来3.1 从代价矩阵到行列归约就用前面那个 4×4 矩阵完整走一遍。原始矩阵员工任务A任务B任务C任务D甲5798乙6487丙7596丁8675行归约每行减去本行最小值。甲行最小值 5减完是 [0, 2, 4, 3]乙行最小值 4得 [2, 0, 4, 3]丙行最小值 5得 [2, 0, 4, 1]丁行最小值 5得 [3, 1, 2, 0]。列归约再看每一列最小值。第 1 列最小值是 0第 2 列最小值是 0第 3 列最小值是 2第 4 列最小值是 0。只有第 3 列要整体减 2得到员工任务A任务B任务C任务D甲0223乙2023丙2021丁3100现在每行每列都有 0但能不能凑出 4 个独立 0还不能一眼保证。3.2 第一次试指派匹配数还不够试指派就是找独立零元素组。手工找的时候优先选那些“这一行/列只有它一个 0”的位置会省很多事。这里我先选出一个匹配甲做任务A丙做任务B丁做任务C。对应矩阵中的 0 是 (甲,A)、(丙,B)、(丁,C)。数一下这个匹配只覆盖了 3 个人乙还没有安排任务 D 也空着。再看乙它的 0 在任务 B但任务 B 已经被丙占了任务 D 在丁那行有 0但丁已经做了任务 C(丁,D) 也是 0可 D 列还没被占用。现在的问题不是完全没希望而是独立 0 凑不齐 4 个最大匹配数只有 3小于 4。这说明当前矩阵还需要调整。真正工程化的试指派可以用二分图增广路来找最大匹配手工算时重点就是判断“最大匹配是不是已经达到 n”。这里没有达到。3.3 画最少覆盖线找最小缺口当最大匹配数小于 n就用 Kőnig 定理找最小覆盖线。覆盖线的意思是用最少的横线或竖线把矩阵里所有 0 都盖住。如果线数小于 n就说明矩阵里还有调整空间如果线数等于 n就已经是完美匹配了。画线前先做个标记过程从没有匹配的行开始。当前匹配是甲—A、丙—B、丁—C乙未匹配。从乙行开始乙行里的 0 在任务 B所以给任务 B 这一列打勾任务 B 列里的已匹配 0 在丙行继续给丙行打勾丙行里唯一的 0 又回到任务 B已经打过去了过程停止。现在画线规则是对没有打勾的行画横线对打勾的列画竖线。没有打勾的行是甲、丁打勾的列是任务 B所以画甲行一条横线、丁行一条横线、任务B一条竖线一共 3 条线。检查一下确实把所有 0 都盖住了甲行的 0 被甲行横线盖住乙行的 0 在任务 B 被竖线盖住丙行的 0 也被竖线盖住丁行的两个 0 被丁行横线盖住。当前最小覆盖线数是 3小于 4所以要调整矩阵。3.4 调整并二次指派得到结果找出所有未被覆盖线盖住的元素取最小值 k。整个矩阵里乙行的任务A、C、D 分别是 2、2、3丙行的任务A、C、D 分别是 2、2、1其他元素都被线盖住了。所以 k 1。调整规则所有未覆盖行整体减 k所有已覆盖列整体加 k。这里未覆盖行是乙、丙两行已覆盖列是任务 B 这一列。算完后矩阵变成员工任务A任务B任务C任务D甲0323乙1012丙1010丁3200现在 0 的位置是(甲,A)、(乙,B)、(丙,B)、(丙,D)、(丁,C)、(丁,D)。重新试指派很容易找到一组 4 个独立 0甲做任务A乙做任务B丙做任务D丁做任务C。原矩阵里对应的总成本是甲做A 成本 5乙做B 成本 4丙做D 成本 6丁做C 成本 7合计 22。3.5 用穷举验证总成本22光说 22 是最优不够有说服力可以快速验证几个相邻排列如果甲做A、乙做B、丙做C、丁做D成本是 549523如果甲做A、乙做B、丙做D、丁做C是 546722如果甲做B、乙做A、丙做C、丁做D是 769527如果甲做D、乙做C、丙做B、丁做A是 885829。这里 22 明显是当前排列里能取到的最小值再配合算法原理可以确认它就是全局最优解。我建议你拿到任何算例后都做一次这样的回代把算法结果代回原代价矩阵求和再和几个手算的排列对比。这步花不了两分钟但能极大减少对算法结果的怀疑。4. 工程实现可以直接抄的Python代码和逐行解释4.1 手写算法还是直接调库实际项目里我会分情况。任务量小、想在面试里展示原理手写一份很有价值业务代码里追求稳定和效率直接用 scipy 更省心。scipy 的linear_sum_assignment底层用的是 Jonker-Volgenant 算法和匈牙利算法同源性能更好支持非方阵只要不是面试场景没必要重复造轮子。但如果面试官让你手撕或你想彻底搞懂原理理解基于势函数dual variables的实现非常关键。下面这份代码是在 ACM 竞赛、算法课里流传很久的 O(n³) 匈牙利算法实现我加了一些注释内部逻辑和前面手算的四步法等价只是把“矩阵调整”换成了更工程化的“顶标修正”。4.2 基于势函数的O(n³)实现def hungarian(cost): n len(cost) # 人数 m len(cost[0]) # 任务数 # 要求 m n如果 m n 需要补虚拟列 u [0] * (n 1) v [0] * (m 1) p [0] * (m 1) # p[j] 任务 j 分配给的员工 way [0] * (m 1) # 增广路回溯 for i in range(1, n 1): p[0] i j0 0 minv [float(inf)] * (m 1) used [False] * (m 1) while True: used[j0] True i0 p[j0] # 当前要匹配的员工 delta float(inf) j1 0 for j in range(1, m 1): if not used[j]: cur cost[i0 - 1][j - 1] - u[i0] - v[j] if cur minv[j]: minv[j] cur way[j] j0 if minv[j] delta: delta minv[j] j1 j for j in range(m 1): if used[j]: u[p[j]] delta v[j] - delta else: minv[j] - delta j0 j1 if p[j0] 0: break while True: j1 way[j0] p[j0] p[j1] j0 j1 if j0 0: break assignment [-1] * n for j in range(1, m 1): if p[j] ! 0: assignment[p[j] - 1] j - 1 return assignment这段代码怎么理解u和v是行顶标和列顶标维护一个“可行势”“cur”表示当前边权与顶标之间的松弛量。内层 while 循环每轮找一个未匹配的列通过不断减小松弛量来扩大匹配。way数组记录的是路径找到增广路后从终点沿way回溯更新匹配。它和你手算的“给未覆盖行减 k、给覆盖列加 k”本质上是同一件事delta就是那个 k顶标更新就是在做矩阵调整。区别在于手算要动整个矩阵而势函数实现只需要维护 u、v 两个一维数组所以复杂度才能稳定在 O(n³)。4.3 scipy一行求解冲冲冲写业务代码时我更推荐直接用 scipyimport numpy as np from scipy.optimize import linear_sum_assignment cost np.array([ [5, 7, 9, 8], [6, 4, 8, 7], [7, 5, 9, 6], [8, 6, 7, 5] ]) row_ind, col_ind linear_sum_assignment(cost) print(row_ind) # 员工索引 print(col_ind) # 对应分配的任务索引 print(cost[row_ind, col_ind].sum())输出里row_ind是员工编号col_ind是分配给每个员工的任务编号。比如结果可能是[0,1,2,3]对应[0,1,3,2]就表示甲做任务A、乙做任务B、丙做任务D、丁做任务C总成本 22。scipy 的接口会自动处理矩形矩阵不需要先补成方阵。这一点在实际业务里非常省事因为真实场景经常是 8 个人做 10 个任务或反过来。4.4 代码里的坑非方阵、浮点与inf用上面自写版本时有两个前提一是 m n否则有些员工注定没活干不符合严格的一一指派定义二是默认每个任务都能做不存在“某人做不了某任务”的禁配关系。如果有禁配关系标准做法是把对应成本设成一个很大的数或inf。对自写版float(inf)参与运算可能会带来奇怪的表现最好用一个足够大的有限数比如矩阵最大值的 100 倍这样算法不会选它又不会破坏数值稳定性。浮点型成本也能跑但顶标和松弛量都是浮点数迭代次数会增多。如果成本是金额建议换算成整数分再算速度和稳定性都会好很多。5. 实际项目里绕不开的四个问题5.1 任务数和人数不相等怎么办不相等分两种情况。人比任务多总有人闲着可以补“虚拟任务”虚拟任务对所有人成本都是 0算法会把成本最低的 n 对先匹配掉剩下的人自然空闲。任务比人多每人最多做一个任务时有些任务做不完scipy 支持直接传 m×n 矩阵它内部会处理自写实现就得补上虚拟员工。补虚拟行/列时要注意成本填 0 还是填一个大数这取决于需求。如果你想让算法优先让人干满虚拟成本设 0还是优先排在前面的人虚拟成本设一个稍小的数答案是虚拟成本设置直接决定你倾向让谁优先分配。设成 0 表示虚拟匹配不占成本算法会尽量让真实任务找到最小成本组合剩余的真实人员被迫闲置。5.2 求最大收益而不是最小成本指派问题常见的变形是最大化利润。匈牙利算法默认求最小化但最大化问题可以转换把每个收益取相反数变成最小化负收益或者用一个足够大的常数 M 减去每个收益变成最小化“亏损”。我一般用第二种思路因为负成本在某些实现里没问题但用M - benefit后矩阵元素都非负手算和自写算法都更安全。M 取所有收益的最大值即可通常M max(benefit)就够这样最优转换不会影响分配结果。5.3 多个最优解同时存在匈牙利算法一次只返回一个最优解但指派问题经常有多个最优解。原因很简单经过归约后如果矩阵中独立零元素的组合不止一种那成本最小值都对应 0多个方案同时最优。项目里如果需要处理多个最优解一个朴素但有效的办法是用匈牙利算法拿到一个解然后给已选中的某个分配位置加一个很小的扰动再算一遍或者用回溯/DFS 枚举所有独立零元素组合找出所有成本等于最优值的方案。不过要提醒一句枚举所有最优解的最坏情况是指数级的一般只有小规模场景才会这样做。大多数业务只需要“任选一个最优解”那就没必要自找麻烦。5.4 大规模数据下如何取舍n 到几千的时候匈牙利算法仍能工作但你要注意矩阵构建本身的代价。比如 5000×5000 的代价矩阵光存储就是 2 亿个浮点数约 1.6GB这往往比算法本身更快成为瓶颈。我实际处理过的一个排班场景是200 多个员工、200 多个订单成本矩阵接近 5 万个元素跑 scipy 不到 1 秒就出结果非常稳。如果 n 再上一个量级建议先做一轮启发式剪枝把明显不可能匹配的边过滤掉或者换用 OR-Tools 这类更重量级的工具而不是抱着裸匈牙利算法硬冲。还有一个体会是任何算法落地前先把脏数据处理干净。成本矩阵里出现负数、空值、过大的值都会直接干扰算法结果。我的习惯是先用np.isfinite(cost).all()检查一遍矩阵再做分配计算。如果你正被“人多活少、人工排班靠拍脑袋”这类问题困扰匈牙利算法值得认真掌握一遍。它不像深度学习那样需要大量数据一个成本矩阵加几十行代码就能在业务里产生实际价值。我第一次把排班从手工调整换成算法计算时最直观的感受是以前要花半天纠结的分配方案现在一秒出解而且我再也不用担心人为拍脑袋漏掉了更优组合。
匈牙利算法详解：从指派问题到最优分配的实现与优化
最烦的一种场景是你手上明明有完整的成本表格任务和人一一对应可你就是找不到一个让人人都满意、总成本又最低的分配方案。订单排期、工位分配、维修任务派单全是这类问题。指派问题就是这么来的而匈牙利算法是解决它最经典、最高效的算法没有之一。我用一个最小化的指派问题说明n 个人做 n 件事每人做每件事的成本不一样每个人只能做一件每件事也只能由一个人做怎样让总成本最低。匈牙利算法的整个流程看起来像一堆矩阵变换看起来很“魔法”但只要把每一步为什么这么做拆开它其实非常朴素。这篇内容适合运筹学初学者、做调度系统开发的工程师、准备算法面试的人尤其是那些想真正理解匈牙利算法而不是只会调库的读者。我会从数学模型讲起用一个 4×4 实例完整手算一遍再给出可以直接抄的 Python 实现和实际项目里最常见的坑。1. 指派问题到底在解什么先花五分钟把数学模型建起来1.1 从“几个人分几件事”到代价矩阵假设你有 4 名员工甲、乙、丙、丁4 项任务 A、B、C、D员工做不同任务的成本不完全相同可能是工时、物料成本或者运输距离。把这些成本写成一个矩阵员工任务A任务B任务C任务D甲5798乙6487丙7596丁8675这个矩阵就是代价矩阵通常记作 c[i][j]表示第 i 个人做第 j 件事的成本。我们的目标是找一组一一对应的分配使所有 c[i][p[i]] 之和最小p[i] 表示第 i 个人被分配到的任务编号。更形式化地说指派问题是一个 0-1 整数规划x[i][j] 1 表示把任务 j 分配给员工 i否则为 0。约束是每行每列有且仅有一个 1目标是最小化 Σc[i][j]·x[i][j]。这组约束看起来不起眼但它是后面所有推导的基础。1.2 为什么不能用穷举硬算4×4 还好说4! 24 种排列笔算都可以。但如果变成 10 个人 10 件事排列数是 10! 3628800 种到 15 个人15! 大概是 1.3 万亿种。等排到 20 个人普通计算机已经很难在合理时间内跑完了。这也是指派问题真正的难点解空间按阶乘增长但问题的结构又足够特殊不需要像通用整数规划那样大动干戈。1955 年 Kuhn 提出的匈牙利算法正是利用了“每一行每一列同时减去一个常数不会改变最优解”这个性质把问题一步步简化最终把复杂度压到 O(n³)。O(n³) 是什么概念n 1000 时大约是 10 亿次基本运算现代计算机在单线程下也就是秒级到十几秒完全可接受。这就是为什么在排班、资源分配这类系统里匈牙利算法几乎是标配。1.3 匈牙利算法的适用边界不是所有分配问题都适合直接用匈牙利算法它的限制要先说清楚要求人或任务两边数量能对齐通常整理成 n×n 方阵非方阵需要补虚拟行/列。目标函数是线性求和不考虑两个人协作、任务先后顺序这类复杂约束。成本矩阵可以理解为二分图边权本质上是求二分图的最优完美匹配。如果你的问题带有优先级、容量限制、互斥关系那它可能不是单纯的指派问题而是需要建更复杂模型的调度问题。但如果核心就是“一一配对、总成本最小”匈牙利算法就是最合适的选择。2. 算法核心思想行列归约为什么不会破坏最优解2.1 归约的数学本质换了个等价问题匈牙利算法第一步是行归约每一行都减去该行的最小值第二步是列归约每一列都减去该列的最小值。很多教程直接说“每行减去最小数”但没说为什么可以这么干。关键性质在这里把某一行所有元素同时减去一个常数 k不会改变这一行的“相对大小”因此也不会改变包含这一行的任何一个可行方案的比较结果。比如甲做任务 A 成本 5做任务 B 成本 7两者之差是 2整行减去 5 后变成 0 和 2差值还是 2。穷举所有排列时甲的选择差异完全不变。列归约的道理一样不过是把视角换成“任务这边”。这个性质在数学上等价于代价矩阵加减行向量和列向量后所有方案的总成本会相差一个固定常数所以最优解不变。这一点是整个算法的基石也是很多人第一次接触时最容易忽略的地方。经过行列归约后矩阵保证每一行每一列至少有一个 0。我们不再盯原始成本而是盯这些 0 元素如果能从每行每列各挑出一个 0就找到了当前等价问题下的最优指派。2.2 独立零元素与最优指派的关系“每行每列各挑一个 0”不是随便挑要求是选出的 n 个 0 两两不同行、两两不同列这叫独立零元素组也对应二分图里的一个完美匹配。为什么挑出 n 个独立 0 就完事了因为归约后的矩阵所有元素都非负任意方案的总成本一定大于等于 0。如果存在一个方案能选到 n 个独立 0那它的成本就是 0而 0 已经是理论下界不可能有比它更小的方案。所以找到 n 个独立零元素就等于找到了最优解。但现实往往没那么顺利。归约之后矩阵里的 0 可能很多也可能扎堆在同一列。比如某个任务特别“便宜”所有人做它都是 0那这列有 n 个 0其他列一个也没有根本凑不出 n 个独立 0。这就是匈牙利算法后续步骤要解决的问题不断制造新 0直到能凑齐 n 个独立零元素。2.3 标准流程四步总览在动手算之前先把完整流程立起来后面每一步都会对号入座行归约每行减去该行最小值。列归约每列减去该列最小值保证每行每列都有 0。试指派在 0 元素中找独立零元素组也就是找最大匹配。调整矩阵如果独立零元素不足 n 个用最少数量的直线覆盖所有 0再从未被覆盖的元素中找最小值 k对未覆盖行减 k、对已覆盖列加 k产生新 0重复第 3、4 步直到找出 n 个独立零元素。第 4 步里“覆盖所有 0 的最少直线数”由 Kőnig 定理保证二分图里最大匹配数等于最小点覆盖数。当最小覆盖线数小于 n说明还能靠调整增加匹配当覆盖线数等于 n匹配就是完美的。3. 一个4×4算例的手算全过程每一步矩阵都摆出来3.1 从代价矩阵到行列归约就用前面那个 4×4 矩阵完整走一遍。原始矩阵员工任务A任务B任务C任务D甲5798乙6487丙7596丁8675行归约每行减去本行最小值。甲行最小值 5减完是 [0, 2, 4, 3]乙行最小值 4得 [2, 0, 4, 3]丙行最小值 5得 [2, 0, 4, 1]丁行最小值 5得 [3, 1, 2, 0]。列归约再看每一列最小值。第 1 列最小值是 0第 2 列最小值是 0第 3 列最小值是 2第 4 列最小值是 0。只有第 3 列要整体减 2得到员工任务A任务B任务C任务D甲0223乙2023丙2021丁3100现在每行每列都有 0但能不能凑出 4 个独立 0还不能一眼保证。3.2 第一次试指派匹配数还不够试指派就是找独立零元素组。手工找的时候优先选那些“这一行/列只有它一个 0”的位置会省很多事。这里我先选出一个匹配甲做任务A丙做任务B丁做任务C。对应矩阵中的 0 是 (甲,A)、(丙,B)、(丁,C)。数一下这个匹配只覆盖了 3 个人乙还没有安排任务 D 也空着。再看乙它的 0 在任务 B但任务 B 已经被丙占了任务 D 在丁那行有 0但丁已经做了任务 C(丁,D) 也是 0可 D 列还没被占用。现在的问题不是完全没希望而是独立 0 凑不齐 4 个最大匹配数只有 3小于 4。这说明当前矩阵还需要调整。真正工程化的试指派可以用二分图增广路来找最大匹配手工算时重点就是判断“最大匹配是不是已经达到 n”。这里没有达到。3.3 画最少覆盖线找最小缺口当最大匹配数小于 n就用 Kőnig 定理找最小覆盖线。覆盖线的意思是用最少的横线或竖线把矩阵里所有 0 都盖住。如果线数小于 n就说明矩阵里还有调整空间如果线数等于 n就已经是完美匹配了。画线前先做个标记过程从没有匹配的行开始。当前匹配是甲—A、丙—B、丁—C乙未匹配。从乙行开始乙行里的 0 在任务 B所以给任务 B 这一列打勾任务 B 列里的已匹配 0 在丙行继续给丙行打勾丙行里唯一的 0 又回到任务 B已经打过去了过程停止。现在画线规则是对没有打勾的行画横线对打勾的列画竖线。没有打勾的行是甲、丁打勾的列是任务 B所以画甲行一条横线、丁行一条横线、任务B一条竖线一共 3 条线。检查一下确实把所有 0 都盖住了甲行的 0 被甲行横线盖住乙行的 0 在任务 B 被竖线盖住丙行的 0 也被竖线盖住丁行的两个 0 被丁行横线盖住。当前最小覆盖线数是 3小于 4所以要调整矩阵。3.4 调整并二次指派得到结果找出所有未被覆盖线盖住的元素取最小值 k。整个矩阵里乙行的任务A、C、D 分别是 2、2、3丙行的任务A、C、D 分别是 2、2、1其他元素都被线盖住了。所以 k 1。调整规则所有未覆盖行整体减 k所有已覆盖列整体加 k。这里未覆盖行是乙、丙两行已覆盖列是任务 B 这一列。算完后矩阵变成员工任务A任务B任务C任务D甲0323乙1012丙1010丁3200现在 0 的位置是(甲,A)、(乙,B)、(丙,B)、(丙,D)、(丁,C)、(丁,D)。重新试指派很容易找到一组 4 个独立 0甲做任务A乙做任务B丙做任务D丁做任务C。原矩阵里对应的总成本是甲做A 成本 5乙做B 成本 4丙做D 成本 6丁做C 成本 7合计 22。3.5 用穷举验证总成本22光说 22 是最优不够有说服力可以快速验证几个相邻排列如果甲做A、乙做B、丙做C、丁做D成本是 549523如果甲做A、乙做B、丙做D、丁做C是 546722如果甲做B、乙做A、丙做C、丁做D是 769527如果甲做D、乙做C、丙做B、丁做A是 885829。这里 22 明显是当前排列里能取到的最小值再配合算法原理可以确认它就是全局最优解。我建议你拿到任何算例后都做一次这样的回代把算法结果代回原代价矩阵求和再和几个手算的排列对比。这步花不了两分钟但能极大减少对算法结果的怀疑。4. 工程实现可以直接抄的Python代码和逐行解释4.1 手写算法还是直接调库实际项目里我会分情况。任务量小、想在面试里展示原理手写一份很有价值业务代码里追求稳定和效率直接用 scipy 更省心。scipy 的linear_sum_assignment底层用的是 Jonker-Volgenant 算法和匈牙利算法同源性能更好支持非方阵只要不是面试场景没必要重复造轮子。但如果面试官让你手撕或你想彻底搞懂原理理解基于势函数dual variables的实现非常关键。下面这份代码是在 ACM 竞赛、算法课里流传很久的 O(n³) 匈牙利算法实现我加了一些注释内部逻辑和前面手算的四步法等价只是把“矩阵调整”换成了更工程化的“顶标修正”。4.2 基于势函数的O(n³)实现def hungarian(cost): n len(cost) # 人数 m len(cost[0]) # 任务数 # 要求 m n如果 m n 需要补虚拟列 u [0] * (n 1) v [0] * (m 1) p [0] * (m 1) # p[j] 任务 j 分配给的员工 way [0] * (m 1) # 增广路回溯 for i in range(1, n 1): p[0] i j0 0 minv [float(inf)] * (m 1) used [False] * (m 1) while True: used[j0] True i0 p[j0] # 当前要匹配的员工 delta float(inf) j1 0 for j in range(1, m 1): if not used[j]: cur cost[i0 - 1][j - 1] - u[i0] - v[j] if cur minv[j]: minv[j] cur way[j] j0 if minv[j] delta: delta minv[j] j1 j for j in range(m 1): if used[j]: u[p[j]] delta v[j] - delta else: minv[j] - delta j0 j1 if p[j0] 0: break while True: j1 way[j0] p[j0] p[j1] j0 j1 if j0 0: break assignment [-1] * n for j in range(1, m 1): if p[j] ! 0: assignment[p[j] - 1] j - 1 return assignment这段代码怎么理解u和v是行顶标和列顶标维护一个“可行势”“cur”表示当前边权与顶标之间的松弛量。内层 while 循环每轮找一个未匹配的列通过不断减小松弛量来扩大匹配。way数组记录的是路径找到增广路后从终点沿way回溯更新匹配。它和你手算的“给未覆盖行减 k、给覆盖列加 k”本质上是同一件事delta就是那个 k顶标更新就是在做矩阵调整。区别在于手算要动整个矩阵而势函数实现只需要维护 u、v 两个一维数组所以复杂度才能稳定在 O(n³)。4.3 scipy一行求解冲冲冲写业务代码时我更推荐直接用 scipyimport numpy as np from scipy.optimize import linear_sum_assignment cost np.array([ [5, 7, 9, 8], [6, 4, 8, 7], [7, 5, 9, 6], [8, 6, 7, 5] ]) row_ind, col_ind linear_sum_assignment(cost) print(row_ind) # 员工索引 print(col_ind) # 对应分配的任务索引 print(cost[row_ind, col_ind].sum())输出里row_ind是员工编号col_ind是分配给每个员工的任务编号。比如结果可能是[0,1,2,3]对应[0,1,3,2]就表示甲做任务A、乙做任务B、丙做任务D、丁做任务C总成本 22。scipy 的接口会自动处理矩形矩阵不需要先补成方阵。这一点在实际业务里非常省事因为真实场景经常是 8 个人做 10 个任务或反过来。4.4 代码里的坑非方阵、浮点与inf用上面自写版本时有两个前提一是 m n否则有些员工注定没活干不符合严格的一一指派定义二是默认每个任务都能做不存在“某人做不了某任务”的禁配关系。如果有禁配关系标准做法是把对应成本设成一个很大的数或inf。对自写版float(inf)参与运算可能会带来奇怪的表现最好用一个足够大的有限数比如矩阵最大值的 100 倍这样算法不会选它又不会破坏数值稳定性。浮点型成本也能跑但顶标和松弛量都是浮点数迭代次数会增多。如果成本是金额建议换算成整数分再算速度和稳定性都会好很多。5. 实际项目里绕不开的四个问题5.1 任务数和人数不相等怎么办不相等分两种情况。人比任务多总有人闲着可以补“虚拟任务”虚拟任务对所有人成本都是 0算法会把成本最低的 n 对先匹配掉剩下的人自然空闲。任务比人多每人最多做一个任务时有些任务做不完scipy 支持直接传 m×n 矩阵它内部会处理自写实现就得补上虚拟员工。补虚拟行/列时要注意成本填 0 还是填一个大数这取决于需求。如果你想让算法优先让人干满虚拟成本设 0还是优先排在前面的人虚拟成本设一个稍小的数答案是虚拟成本设置直接决定你倾向让谁优先分配。设成 0 表示虚拟匹配不占成本算法会尽量让真实任务找到最小成本组合剩余的真实人员被迫闲置。5.2 求最大收益而不是最小成本指派问题常见的变形是最大化利润。匈牙利算法默认求最小化但最大化问题可以转换把每个收益取相反数变成最小化负收益或者用一个足够大的常数 M 减去每个收益变成最小化“亏损”。我一般用第二种思路因为负成本在某些实现里没问题但用M - benefit后矩阵元素都非负手算和自写算法都更安全。M 取所有收益的最大值即可通常M max(benefit)就够这样最优转换不会影响分配结果。5.3 多个最优解同时存在匈牙利算法一次只返回一个最优解但指派问题经常有多个最优解。原因很简单经过归约后如果矩阵中独立零元素的组合不止一种那成本最小值都对应 0多个方案同时最优。项目里如果需要处理多个最优解一个朴素但有效的办法是用匈牙利算法拿到一个解然后给已选中的某个分配位置加一个很小的扰动再算一遍或者用回溯/DFS 枚举所有独立零元素组合找出所有成本等于最优值的方案。不过要提醒一句枚举所有最优解的最坏情况是指数级的一般只有小规模场景才会这样做。大多数业务只需要“任选一个最优解”那就没必要自找麻烦。5.4 大规模数据下如何取舍n 到几千的时候匈牙利算法仍能工作但你要注意矩阵构建本身的代价。比如 5000×5000 的代价矩阵光存储就是 2 亿个浮点数约 1.6GB这往往比算法本身更快成为瓶颈。我实际处理过的一个排班场景是200 多个员工、200 多个订单成本矩阵接近 5 万个元素跑 scipy 不到 1 秒就出结果非常稳。如果 n 再上一个量级建议先做一轮启发式剪枝把明显不可能匹配的边过滤掉或者换用 OR-Tools 这类更重量级的工具而不是抱着裸匈牙利算法硬冲。还有一个体会是任何算法落地前先把脏数据处理干净。成本矩阵里出现负数、空值、过大的值都会直接干扰算法结果。我的习惯是先用np.isfinite(cost).all()检查一遍矩阵再做分配计算。如果你正被“人多活少、人工排班靠拍脑袋”这类问题困扰匈牙利算法值得认真掌握一遍。它不像深度学习那样需要大量数据一个成本矩阵加几十行代码就能在业务里产生实际价值。我第一次把排班从手工调整换成算法计算时最直观的感受是以前要花半天纠结的分配方案现在一秒出解而且我再也不用担心人为拍脑袋漏掉了更优组合。
