匈牙利算法矩阵形式详解：从成本约减到最优分配的完整推导

前阵子有个做调度优化的朋友来问，说看网上的匈牙利算法教程，流程图一摆、代码一贴，看着都懂，可自己拿个成本矩阵一算就发懵，尤其是“矩阵形式”这一层，总觉得像魔术：为什么行减一减、列减一减，答案就自己冒出来了？我跟他聊了半小时，发现许多教程都默认跳过了最关键的数学解释，直接教操作。所以我干脆把这套东西从矩阵视角完整捋了一遍，从为什么能这样减，到每一步在做什么，再到一段可以手算的完整例子，一次性讲透。

这篇文章适合几类人：正在学运筹学或算法课、被指派问题绕晕的学生；需要用匈牙利算法解决任务分配、工单调度等问题的工程师；以及只想搞清楚“矩阵操作背后的数学原理”而不是背步骤的好奇型读者。我会尽量用“算一遍”的方式来讲，保证你看完能独立用手算出一个4阶矩阵的最优分配，也明白为什么结果一定是最优。

1. 整体设计与思路拆解

1.1 指派问题：先搞清楚矩阵在描述什么

匈牙利算法解决的是经典指派问题：有 n 项任务和 n 个人，每个人做每项任务有一个成本（或耗时），要求一人一岗、一岗一人，求总成本最小的分配方案。

一个很自然的数学表达就是成本矩阵 C，其中 C[i][j] 表示第 i 个人做第 j 项任务的成本。一个完整的分配方案，就是从每一行、每一列里各挑一个元素，而且任何两个被挑中的元素不能在同一行或同一列。这个“行行不重、列列不重”的要求，本质上就是 n 个位置构成一个“排列”。

我们最终要找的是一组排列，使得选出的 n 个元素之和最小。这就是矩阵形式要表达的核心：从矩阵中选出 n 个互不同行、互不同列的格子，让它们的数字加起来最小。匈牙利算法之所以叫匈牙利算法，是因为它源于匈牙利数学家提出的一个定理，后来被用来解决这个指派问题，但算法本身的漂亮之处在于：把“选 n 个数让和最小”这个问题，转化成“在矩阵里找 n 个零”的问题。

1.2 矩阵形式的整体框架：三步走

匈牙利算法的矩阵形式，整体上可以拆成三块：

• 约减：通过行减、列减，把成本矩阵变成非负矩阵，并制造出尽可能多的零元素。
• 试指派：看能不能从零元素里挑出 n 个互不同行、互不同列的“独立零”。能挑出来，答案就有了。
• 迭代调整：挑不够时，用“划线-调整-再找零”的循环，直到挑出 n 个独立零。

这三步里，第一步和第三步是最容易让人困惑的。很多人不明白为什么随便减一减就等价；也不明白为什么划线后要执行那套“未覆盖行减、被覆盖列加”的规则。下面我会把每一步背后的数学逻辑拆开讲。

1.3 为什么“矩阵形式”值得单独拿出来理解

算法的代码实现有很多种，但矩阵形式是最贴近数学本质的。它把所有抽象的对偶、增广、匹配关系，都具象成了“划掉行/列”“加一减一”这样的可视化操作。

对于想真正理解算法的人来说，矩阵形式提供了三个直接的好处：第一，可以手算验证，不需要写代码；第二，可以把每一步操作和“为什么它不影响最优解”一一对应起来；第三，它天然解释了算法的收敛过程——每一次调整都会让某些零的位置发生变化，最终会充实到一个完整匹配。

2. 核心细节解析与实操要点

2.1 行约减、列约减：为什么“随便减”不影响最优解

很多人第一反应是：你把一整行都减掉一个数，明明数字全变了，凭什么最优方案不变？

这里的关键在于约减是对“整行”或“整列”做等量偏移。假设某人 i 做所有任务的成本都同时减少 5，那么不管最终分配方案怎么选，这个人只要被安排任务，总成本一定比原来少 5。由于任何方案中第 i 行恰好只被选中一个元素，因此每种方案的目标函数都会减少相同的 5。比较方案时，大家都减去同一个常数，大小关系当然不会变。

列约减也是一个道理：第 j 列所有元素同时减 3，意味着不管哪个方案用到第 j 列，都会且只会选一个元素，所有方案同时减少 3。

这个“选一行只取一个元素、选一列只取一个元素”的结构性质，让整行整列的加减成了不改变最优解的自由操作。这也是矩阵形式最核心的数学基础。

实际操作时，一般先对每一行减去该行最小值，再对每一列减去该列最小值。做完这两步，矩阵中每一行至少出现一个零，每一列也至少出现一个零。注意，列约减之后某些行可能又出现了新的零，但原来的零不会被破坏，只是增加。所以行、列约减通常只需要按顺序做一轮即可，不需要反复做。

2.2 独立零：零元素里的“黄金组合”

行、列约减之后，矩阵里会出现很多零。接下来要想的问题就是：能不能从这些零里选出 n 个互不同行、互不同列的格子？如果可以，那就直接得到了最优解。

为什么这么说？因为约减后的矩阵里所有元素都非负，而一个完整指派选出来的 n 个位置如果全是零，累计成本就是 0。任何其他方案选出的 n 个元素，每一项都大于等于 0，总成本不可能小于 0。所以一组“n 个独立零”对应的分配，就是最优分配。

这里要特别区分“零”和“独立零”。判断零是不是独立，需要同时满足不同行和不同列。比如一个 3 阶矩阵里，零出现在 (1,1)、(2,1)、(3,2)，虽然有三个零，但 (1,1) 和 (2,1) 同在列 1，不能同时选。能同时选的最大数量只有 2，这就不构成完整指派。

找独立零，本质上是在一个二分图里找最大匹配：左边是行，右边是列，每个零就是一条边。n 个独立零就是大小为 n 的匹配。手工小规模算的时候可以目测；规模大了，需要跑 DFS 增广匹配算法。这里先理解概念，第 3 节会演示具体怎么挑。

2.3 划线覆盖与矩阵调整：算法最微妙的一步

如果找不到 n 个独立零，算法就进入核心迭代。这一步的数学逻辑也最容易被误解。

直观上讲，我们需要判断：当前这些零，到底是零太少、位置不好，还是真就凑不出 n 个？匈牙利算法用一个工具来回答这个问题：最少直线覆盖。用若干条横线或竖线去覆盖矩阵里所有的零元素，线数最少要用多少条？

这里有一条非常重要的定理（匈牙利算法的数学内核之一）：矩阵中最少覆盖所有零的直线数量，等于最大能选出的独立零数量。也就是说，如果你用 3 条线就覆盖了所有零，那么当前最多只能选出 3 个独立零，自然达不到 n。这条定理把“零的位置问题”转化成了“线覆盖问题”，非常巧妙。

当最少线数小于 n 时，需要做一次矩阵调整，目的是制造新的零，让独立零的最大数量增加。调整规则是这样的：设未被任何直线覆盖的最小元素值为 k，然后：

• 所有未被覆盖的行，每个元素都减去 k；
• 所有被覆盖的列，每个元素都加上 k；
• 既被覆盖又在未覆盖行（即交叉点）的元素，减 k 再加 k，刚好不变。

我第一次看到这条规则时也觉得很神秘，但拆开看就清楚了。先看“未覆盖行减去 k”：这是为了在未覆盖区域引入新的零——那一个值最小的元素会变成 0。再看“被覆盖列加上 k”：这是为了补偿那些“位于被覆盖列且属于未覆盖行的元素”，避免它们因为行减 k 而变成负数。补偿之后，原本那些正元素不会退化成负值，新出现的零却保留了下来。整个操作的结果是：矩阵仍然非负，零的集合发生了变化，且最优解对应的等价关系不变。

为什么这个调整一定会推进？因为最小被覆盖行减少后，原先生成一个新零；更重要的是，这一系列操作会让“最少覆盖线数”增加至少 1，因此最大独立零数量也会增加。重复若干轮，一定可以凑齐 n 个独立零。理解这一点后，规则就不再是生硬的背诵，而是“引入新零、同时保证非负”的必然设计。

2.4 完整流程：一图一样的文字版步骤

为了后面不致迷路，把完整步骤像清单一样列出来：

1. 输入 n 阶成本矩阵 C。
2. 每行减去该行最小值，得到行约减矩阵。
3. 每列减去该列最小值，得到列约减矩阵。
4. 在工作矩阵中寻找 n 个独立零：
   • 能找到，直接对应最优分配，计算原成本相加，结束。
   • 找不到，进入第 5 步。
5. 用最少直线覆盖所有零元素。
6. 找到未被覆盖元素中的最小值 k。
7. 未覆盖行的所有元素减 k，被覆盖列的所有元素加 k，其他元素不变。
8. 回到第 4 步。

实际工程实现时，第 4 步“找独立零”和第 5 步“最少直线覆盖”经常会合并处理，用二分图最大匹配求解。但手工理解时，分成两步更清楚。

3. 实操过程与核心环节实现

3.1 完整手算示例：4 阶矩阵一步到位

我准备了一个经典的 4 阶成本矩阵，从约减到选出独立零，完整推一遍。

成本矩阵 C：

12 7 9 8 6 9 5 7 8 6 4 7 7 5 8 6

先做行约减，每行减去本行最小值：

• 第 1 行最小值 7，减后得到 5 0 2 1；
• 第 2 行最小值 5，减后得到 1 4 0 2；
• 第 3 行最小值 4，减后得到 4 2 0 3；
• 第 4 行最小值 5，减后得到 2 0 3 1。

得到：

5 0 2 1 1 4 0 2 4 2 0 3 2 0 3 1

再对每一列减该列最小值。第 1 列当前是 5、1、4、2，最小值为 1，减后变为 4、0、3、1；第 2 列是 0、4、2、0，最小值为 0，不变；第 3 列是 2、0、0、3，最小值为 0，不变；第 4 列是 1、2、3、1，最小值为 1，减后变为 0、1、2、0。

于是得到约减后的矩阵 B：

4 0 2 0 0 4 0 1 3 2 0 2 1 0 3 0

现在要找 4 个独立零。我直接给出一种选择：

• 第 1 行选第 2 列，元素 B[1][2] = 0；
• 第 2 行选第 1 列，元素 B[2][1] = 0；
• 第 3 行选第 3 列，元素 B[3][3] = 0；
• 第 4 行选第 4 列，元素 B[4][4] = 0。

四组行、列都不重复，确实凑齐了 4 个独立零。这时对应到原矩阵里的成本是：

• 第 1 行第 2 列：7；
• 第 2 行第 1 列：6；
• 第 3 行第 3 列：4；
• 第 4 行第 4 列：6。

总成本 = 7 + 6 + 4 + 6 = 23。

这就是最优分配。原因也很直接：约减后的矩阵每一项都非负，而我们选出的四个位置全是零，累计为 0；任何其他方案在约减矩阵里的累计值都不可能小于 0，所以原成本不可能小于 23。这个例子最直观地说明了“找 n 个独立零”为什么等价于“求最小成本”。

3.2 需要迭代的例子：当零凑不齐时怎么办

上面的例子太顺利，不代表算法真正难的部分。下面这个 3 阶例子会强制进入“划线-调整”流程，正好看清楚迭代逻辑。

成本矩阵 C：

2 5 7 3 7 8 5 1 4

先做行约减：

• 第 1 行减 2，得到 0 3 5；
• 第 2 行减 3，得到 0 4 5；
• 第 3 行减 1，得到 4 0 3。

行约减后：

0 3 5 0 4 5 4 0 3

再做列约减：

• 第 1 列最小值为 0，不变；
• 第 2 列最小值为 0，不变；
• 第 3 列当前是 5、5、3，最小值为 3，减后变为 2、2、0。

得到：

0 3 2 0 4 2 4 0 0

这个矩阵里，零出现在 (1,1)、(2,1)、(3,2)、(3,3)。最多只能选出 2 个独立零，比如 (1,1) 和 (3,2)，第 2 行就没有可用的独立零了。于是我们需要划线。

用最少直线覆盖所有零，一种选择是：第 1 列画一条竖线，第 3 行画一条横线。这样 (1,1)、(2,1) 被竖线覆盖，(3,2)、(3,3) 被横线覆盖，所有零都被盖住，总共 2 条线。

接下来找未被覆盖的最小元素。未被覆盖的区域是：第 1 行第 2、3 列（3 和 2），第 2 行第 2、3 列（4 和 2）。最小值是 2。

执行调整：

• 未覆盖的行是第 1、2 行，它们各减 2；
• 被覆盖的列是第 1 列，它加 2；
• 第 3 行是被覆盖行，不执行减 2，但第 1 列加 2 会影响它。

逐元素算一下。

第 1 行：0 3 2，先减 2，得 -2 1 0；但第 1 列是被覆盖列，还需要加 2，因此第 1 个元素变为 0。最终得到 0 1 0。

第 2 行：0 4 2，同理先减 2，得 -2 2 0；第 1 列加 2，变为 0。最终得到 0 2 2。

第 3 行：4 0 0，它是被覆盖行，不执行减 2；但第 1 列加 2，因此变为 6 0 0。

调整后的矩阵：

0 1 0 0 2 2 6 0 0

现在再看独立零：可以选出 (1,3)、(2,1)、(3,2)，三个独立零正好凑齐。

对应原矩阵里的成本：

• 第 1 行第 3 列：7；
• 第 2 行第 1 列：3；
• 第 3 行第 2 列：1；

总成本 = 7 + 3 + 1 = 11。

也可以反推验证：调整后选出的三个约减矩阵位置全是 0，等价于原最优成本 11。如果你用穷举法把 6 种分配方案都列出来，会发现确实没有比 11 更小的方案。这个例子虽然只有 3 阶，但完整走了一遍“约减-找不到-划线-调整-再找”的过程，算法核心部分就全在这里了。

3.3 算法实现时该注意的工程细节

如果只是学习原理，手算就够。如果是写程序实现，有几个地方需要额外注意。

第一，找 n 个独立零和找最少覆盖线，这两步建议直接用一个二分图最大匹配函数一起做。把零元素视为边，求最大匹配；最大匹配的规模如果等于 n，就得到独立零并结束；如果小于 n，再从最大匹配出发，找到一条从自由行开始的交替路径，路径上的行集合和列集合就能确定最少覆盖线。这样比“先目测划线、再找独立零”可靠得多。

第二，浮点成本要小心。如果成本是小数，约减和调整过程会出现非常接近 0 的小负数，比如 1e-15。判断零时不要让绝对值小于某阈值就当作零，宁可严格判等于 0，也不要因浮点误差误判出虚假独立零，否则结果会不稳定。稳妥的做法是先用整数或定点化处理数据，或在比较时设置一个很小的容差。

第三，关于不可行或规模扩展。指派问题如果人和任务数量不一致，需要补零行或补零列来凑成方阵；如果有“某个人不能做某件事”的限制，可以把对应位置设成非常大的数（比如 10^9），让算法自动避开它。最大化利润问题，则可以把利润矩阵整体取负，或转换为“大数减利润”后求最小化，本质都是转化成标准最小化成本问题。

4. 常见问题与排查技巧实录

4.1 常见问题速查表

我把自己在实际使用和辅导别人过程中遇到过的问题整理了一下，做成速查表。

4.2 最容易犯的几个认知误区

第一个误区：以为行约减、列约减之后，直接每一行随便挑一个零就能得到答案。实际上零很可能互相冲突，需要“不重复行、不重复列”，所以本质上是在求匹配，不是在逐行贪心。

第二个误区：以为“最少覆盖线”必须用手算，划不出来就卡住。手工规模小可以瞎试，但程序必须依赖最大匹配，否则数据稍大就错。理解“最小线数 = 最大匹配数”这层关系，才能明白手工划线的方向。

第三个误区：以为矩阵调整是在“碰运气”造零。其实它是构造性地把一个和最优成本等价的问题切到另一个等价问题上，保证最大匹配数增加。所以不要跳过调整步骤去人工修改矩阵，那样很可能改变问题本身。

第四个误区：以为多解是算法错了。很多时候最优方案并不唯一，尤其是有零的交叉结构时。只要最优成本一致，多解是正常的。工程中如果想固定选一个，可以加入扰动规则。

4.3 独家避坑心得：先手算一个小例子再上库

我在实际工程里的一个体会是：无论你最后用哪种工具或库，都要先用手算一个不超过 4 阶的小矩阵，把最优解和成本验证清楚，再移植到真实数据。这不是浪费时间，而是给自己建立参照基准。

有一次我给一批任务做分配，数据改成浮点后，直接跑出来一个“成本很小”的结果，但人工抽查发现有些任务匹配到了成本极高的人。排查下来，是因为数据里有缺失值被默认处理成了 0，而 0 被算法当成了“成本极低”，直接抢走了匹配。这个坑让我意识到：矩阵里出现零值是一个强信号，算法会优先选它；所以零值必须有意义，要么真的成本为 0，要么用大数表示不可行，不能随便留空。

另外，如果矩阵阶数比较大，千万别用手工划线的方法判断。二分图最大匹配的实现并不复杂，几十行就能写完，但它的性能和小规模目测完全不是一个量级。匈牙利算法本身的复杂度是 O(n^3)，配合最大匹配实现，工程上足够用。

4.4 从数学层面对照检查：三个“为什么”都回答了吗

最后做一个自查，确保不是只学会了操作，而是真理解了矩阵形式：

1. 为什么约减不影响最优解？因为每个方案在各行各列都恰好选一个元素，整行整列加减同一个数，所有方案的目标函数增量相同。
2. 为什么 n 个独立零是最优？因为约减后矩阵非负，独立零方案的总成本是 0，已经达到下界。
3. 为什么调整规则有效？未覆盖行减 k 引入新零，被覆盖列加 k 防止元素变负，同时等价性保持，最大匹配数每轮增加。

这三个问题如果都能顺畅回答，那“匈牙利算法的数学上理解——矩阵形式”这个主题就算真正拿下了。我个人在实际操作中最受益的一个习惯是：每轮矩阵变换后，暂停下来，用“最优成本 = 原成本 - 累计约减总量”反推一下当前矩阵的目标值，既验证正确性，也帮助理解算法究竟在追踪什么。你也可以试试这种做法，它会让矩阵里的每一次加减都变得有方向感，而不是机械操作。