匈牙利算法入门：步骤、原理与实例详解
引言：分配问题的挑战
想象一下这样的场景：你有一组工人，需要完成一组任务。每个工人完成不同任务的效率或成本是不同的。你的目标是为每个工人分配一个任务（并且每个任务只分配给一个工人），使得总的成本最低，或者总的效率最高。
这不仅仅是一个简单的例子，它代表了一类重要的运筹学问题——分配问题（Assignment Problem）。这类问题广泛存在于各种实际应用中，如：
- 生产与调度： 将工人分配到机器，或将机器分配到生产订单，以最小化总生产时间或成本。
- 人员管理： 将员工分配到项目或岗位，以最大化整体绩效。
- 物流与运输： 将车辆分配到配送路线，以最小化总运输成本。
- 资源配置： 将有限资源分配给不同的活动，以达到最优效果。
- 匹配问题： 例如在恋爱匹配、招聘筛选等场景中，找到最优的配对组合。
对于小规模问题，我们或许可以通过枚举所有可能的分配方案来找到最优解。然而，如果工人数量和任务数量都是n，可能的分配方案总数是 n!（n的阶乘）。这个数字增长得极快：5个工人5个任务是 120 种可能；10个工人10个任务是 3,628,800 种可能；而20个工人20个任务的可能性是一个天文数字，超过 2.4 x 10^18。显然，枚举法在实际应用中是不可行的。
我们需要一种更高效的算法来解决分配问题。而匈牙利算法（Hungarian Algorithm）正是为此而生。它由美国数学家哈罗德·库恩（Harold Kuhn）于1955年提出，命名为“匈牙利算法”是为了纪念两位匈牙利数学家：德内斯·柯尼希（Dénes Kőnig）和尤金·埃格瓦里（Jenő Egerváry），他们的早期工作奠定了算法的理论基础（柯尼希定理）。匈牙利算法能够以多项式时间复杂度（通常是 O(n^3) 或 O(n^4)）找到分配问题的最优解，这使其成为解决中等规模甚至较大规模分配问题的强大工具。
本文将带你深入了解匈牙利算法。我们将从其核心原理出发，详细拆解算法的每一个步骤，并通过一个具体的实例手把手演示其应用过程。无论你是学生、工程师还是对优化问题感兴趣的普通读者，希望本文都能为你揭开匈牙利算法的神秘面纱，助你轻松入门。
二、分配问题的数学模型与匈牙利算法的目标
在深入算法步骤之前，我们先用数学语言描述一下分配问题。
假设我们有 n 个工人 $W = {w_1, w_2, …, w_n}$ 和 n 个任务 $T = {t_1, t_2, …, t_n}$。已知工人 $w_i$ 完成任务 $t_j$ 的成本为 $c_{ij}$。这些成本可以组织成一个 n x n 的成本矩阵 C：
$$ C = \begin{pmatrix} c_{11} & c_{12} & \cdots & c_{1n} \ c_{21} & c_{22} & \cdots & c_{2n} \ \vdots & \vdots & \ddots & \vdots \ c_{n1} & c_{n2} & \cdots & c_{nn} \end{pmatrix} $$
我们的目标是找到一个分配方案，也就是一个从工人集合 W 到任务集合 T 的一对一映射（或者说，一个任务集合到工人集合的一对一映射）。这个映射可以表示为一个排列 $p$，其中工人 $w_i$ 分配给任务 $t_{p(i)}$。一个有效的分配方案必须确保每个工人恰好分配一个任务，并且每个任务恰好被一个工人完成。
在数学上，我们可以引入一个 n x n 的二元决策变量矩阵 X，其中 $x_{ij} = 1$ 表示工人 $w_i$ 分配给任务 $t_j$，而 $x_{ij} = 0$ 表示不分配。
分配问题的目标是最小化总成本：
$$ \text{Minimize } Z = \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij} $$
subject to constraints:
$$ \sum_{j=1}^n x_{ij} = 1 \quad \text{for } i = 1, 2, \ldots, n \quad (\text{每个工人恰好分配一个任务}) $$
$$ \sum_{i=1}^n x_{ij} = 1 \quad \text{for } j = 1, 2, \ldots, n \quad (\text{每个任务恰好被一个工人完成}) $$
$$ x_{ij} \in {0, 1} \quad \text{for } i, j = 1, 2, \ldots, n $$
这是一个典型的整数线性规划问题。而匈牙利算法提供了一种比通用整数线性规划求解器更高效的算法来解决这类特定的问题（当工人数量和任务数量相等时，称为完美匹配问题的一种）。
匈牙利算法的核心思想在于，它不直接寻找最优分配，而是通过一系列矩阵变换，在成本矩阵中创建足够多的“0”元素。这些变换不会改变最优分配方案，并且如果能够在这些“0”元素中找到一个包含n个相互独立的（即，每个工人对应一个任务，每个任务对应一个工人）元素组成的集合，那么这个集合对应的原始成本之和就是最小总成本，这个集合就是最优分配方案。
为什么通过矩阵变换创造零元素，并且基于零元素寻找分配是有效的呢？这涉及到算法的数学原理，特别是与柯尼希定理（Kőnig’s Theorem）以及二分图最大匹配与最小顶点覆盖的关系。简单来说，算法通过减去行/列最小值来创建零，这相当于给所有工人/任务一个“补贴”或“罚款”，但这种操作并不会改变不同分配方案之间的相对成本差异，因此最优分配方案保持不变。如果在变换后的矩阵中，我们能找到一个由零组成的完美匹配，这意味着在这个匹配中的所有分配对 $(i, j)$ 对应的变换后成本 $c’_{ij} = 0$。由于变换后的所有成本都是非负的（这是算法步骤保证的），0是可能的最小值，因此总变换后成本为0，这必然对应于原问题的一个最优解。
三、匈牙利算法的核心原理：矩阵变换与零的意义
匈牙利算法之所以巧妙且高效，在于它利用了以下关键原理：
-
等价变换： 如果从成本矩阵的某一行或某一列中减去或加上一个常数，那么原问题的最优分配方案不会改变。这是因为，无论采取何种分配方案，每个工人（每行）和每个任务（每列）都只会被选中一次。因此，对某一行所有元素减去一个常数，相当于给这个工人一个固定额度的补贴，这会使得所有涉及这个工人的分配方案的总成本都减少相同的量。同理，对某一列所有元素减去一个常数，相当于给完成这个任务的工人一个固定额度的补贴。这些等价变换仅仅是改变了总成本的绝对值（或者说，改变了成本的“零点”），但不会改变不同分配方案的相对优劣顺序。
-
零的意义： 在经过等价变换后的矩阵中，一个元素 $c’_{ij} = 0$ 意味着工人 $w_i$ 完成任务 $t_j$ 的相对成本是最低的（相对于该行和该列的其他选项，经过调整后）。如果能够找到一个由 n 个零元素组成的集合，且这些零元素分布在不同的行和不同的列，这就构成了一个由零组成的有效分配方案。根据等价变换的原理，这个由零组成的方案在变换后的矩阵中总成本为零，这已经是可能的最低总成本（变换后的所有成本都是非负的）。因此，这个方案对应的原始分配方案就是原问题的最优解。
-
覆盖零与改进： 如果在变换后的矩阵中，不能立即找到一个由 n 个零组成的独立集合（即无法用零构成完美匹配），这意味着当前的零还不足以构成最优解，或者这些零的分布不够“分散”。算法的下一步是通过画最少数量的直线（水平或垂直）覆盖所有的零。根据柯尼希定理，覆盖所有零所需的最少直线数等于矩阵中独立零的最大数量。如果最少直线数小于 n，说明我们还无法找到 n 个独立的零。此时，算法会利用未被直线覆盖的元素中最小的值来进行进一步的矩阵调整。这个调整的目的是在不改变最优解的前提下，创造新的零或增加现有零的密度，从而增大找到 n 个独立零的可能性。具体做法是：将未被覆盖的所有元素减去这个最小值，并将位于两条直线交汇处的元素加上这个最小值。这个操作确保了：
- 未被覆盖的元素至少会有一个变成零，从而创造新的可能分配位置。
- 被一条直线覆盖的零保持不变。
- 被两条直线覆盖的元素（交汇处）相对成本增加，这是为了维持等价性，因为它们在这轮调整中既没有被减去（因为被覆盖），也没有被加回去（因为被覆盖），为了补偿前面步骤可能对它们产生的隐含影响（例如在行/列减去最小值时），需要加上这个调整量。
通过不断重复“创建零 -> 尝试覆盖 -> 改进矩阵”的过程，直到能够用 n 条直线覆盖所有零，匈牙利算法最终能够找到一个由 n 个独立零组成的集合，从而确定最优分配方案。
理解了这些原理，我们就可以开始学习具体的算法步骤了。
四、匈牙利算法的详细步骤
匈牙利算法适用于求解最小化成本的完全分配问题（即 n 个工人对 n 个任务）。如果是最大化问题或非完全分配问题，需要进行预处理（将在后面介绍）。这里我们以最小化成本的 n x n 矩阵为例。
步骤 1：预处理（矩阵规范化）
如果原始成本矩阵不是方阵（n x m，n ≠ m），则需要将其转化为方阵。
* 如果 n < m，添加 m – n 个“虚拟工人”，他们完成任何任务的成本都为 0。
* 如果 n > m，添加 n – m 个“虚拟任务”，任何工人完成这些虚拟任务的成本都为 0。
这样我们就得到一个 max(n, m) x max(n, m) 的方阵。对于最小化问题，虚拟工人/任务的成本设为0通常是合理的，表示他们不会增加总成本。对于最大化问题，则应设置为一个非常大的负数或0，具体取决于实际情境。在本文的标准介绍中，我们假设输入已经是一个 n x n 的成本矩阵。
步骤 2：行减
对成本矩阵的每一行，找到该行的最小元素，然后将该行中的所有元素都减去这个最小元素。
这一步的目的是在每一行中都至少创建一个零。
步骤 3：列减
在完成行减后的矩阵基础上，对每一列，找到该列的最小元素，然后将该列中的所有元素都减去这个最小元素。
这一步的目的是在每一列中都至少创建一个零。经过行减和列减后，矩阵中会产生更多的零。
步骤 4：尝试覆盖零（寻找独立零的最大数量）
在经过行减和列减后的矩阵中，尝试用最少数量的水平线和垂直线覆盖所有的零。
这一步的目的是找出当前矩阵中能够构成独立分配的最大零数量。如果最少直线数等于矩阵的阶数 n，这意味着存在 n 个独立的零，可以构成一个由零组成的完美匹配。根据原理，这就是一个最优分配方案。算法跳转到步骤 6。
如果最少直线数小于 n，则说明当前的零还不足以构成最优解，需要进行矩阵改进。算法进入步骤 5。
如何找到最少数量的直线覆盖所有零？
这是一个子问题，可以使用一些启发式方法或更系统的方法。一个常用的启发式方法是：
1. 找到包含零最多的行或列，用一条直线覆盖它。
2. 重复步骤 1，直到所有的零都被覆盖。
3. 计算覆盖所有零所需的总直线数。
更严谨的方法基于二分图的最大匹配。柯尼希定理指出，二分图中的最大匹配数等于最小顶点覆盖数。在匈牙利算法中，覆盖零的问题可以转化为在对应的二分图中找到最小顶点覆盖。这里我们不展开这部分内容，只需知道目标是找到最少直线数。实践中，可以尝试一些策略，例如优先覆盖包含零最多的行或列。
步骤 5：矩阵改进（调整未覆盖元素）
如果步骤 4 中最少直线数 L < n，则需要对矩阵进行调整以产生新的零。
1. 找出所有未被任何直线覆盖的元素中的最小值为 $\theta$。
2. 将所有未被任何直线覆盖的元素都减去 $\theta$。
3. 将所有位于两条直线交汇处的元素都加上 $\theta$。
4. 被一条直线覆盖的元素保持不变。
调整完成后，返回步骤 4，重新尝试覆盖零并检查是否达到最优条件（最少直线数等于 n）。
为什么这样做能改进？
* 未被覆盖的元素都减去了 $\theta > 0$。其中至少有一个未被覆盖的元素原本是最小的（值等于 $\theta$），现在变成了 0，创造了新的零位置。
* 被一条直线覆盖的零保持为零。
* 位于交汇处的元素被加了 $\theta$。考虑一个交汇处的元素 $c’{ij}$。它在行减中被减去了 $r_i$，在列减中被减去了 $c_j$。在矩阵改进中，它又被加了 $\theta$。而一个未被覆盖的元素 $c”{kl}$ 在行减中被减去了 $r_k$，在列减中被减去了 $c_l$，但在矩阵改进中被减去了 $\theta$。这种加减操作精妙地保持了最优解的相对位置，同时推动了未覆盖区域向零靠近。
步骤 6：寻找最优分配
当步骤 4 的条件满足（最少直线数 L = n）时，矩阵中存在一个由 n 个零组成的独立集合，这就是最优分配方案。
如何找到这个集合？
可以从零最多的行或列开始，或者从只有一两个零的行或列开始。一个系统性的方法是：
1. 查找只有一个零的行。选择这个零作为分配的一部分，并在矩阵中划掉它所在的行和列（表示该工人和任务已被分配）。
2. 重复步骤 1，直到所有只有一个零的行都被处理完毕。
3. 接下来查找只有一个零的列。选择这个零作为分配的一部分，并划掉它所在的行和列。
4. 重复步骤 3，直到所有只有一个零的列都被处理完毕。
5. 如果仍然存在未分配的行和列，且这些行和列中的零多于一个，则可以任选一个零作为分配的一部分，然后划掉它所在的行和列，并回到步骤 1 或 3 重新寻找只有一个零的行/列。这个过程可能需要回溯（如果某个选择导致无法完成所有分配）。更稳定的方法是使用最大二分图匹配算法来从零矩阵中找到完美匹配，但对于手工计算，上述启发式方法通常足够找到解。
步骤 7：计算最小总成本
将步骤 6 中找到的 n 个零对应的元素，回到原始成本矩阵中查找它们的成本值。这些成本值之和就是最小总成本。
至此，匈牙利算法的整个流程结束。
五、实例演示：手把手求解分配问题
我们来通过一个具体的 4×4 成本矩阵示例来演示匈牙利算法的完整过程。
假设有 4 个工人 (W1, W2, W3, W4) 和 4 个任务 (T1, T2, T3, T4)。成本矩阵如下：
$$ C = \begin{pmatrix} 25 & 18 & 21 & 30 \ 31 & 24 & 27 & 35 \ 28 & 22 & 25 & 33 \ 20 & 16 & 19 & 28 \end{pmatrix} $$
目标是找到一种分配方案，使得总成本最小。
步骤 1：预处理
矩阵已经是 4×4 方阵，无需预处理。
步骤 2：行减
找到每行的最小值：
* 行 1 最小值：18
* 行 2 最小值：24
* 行 3 最小值：22
* 行 4 最小值：16
将每行元素减去其最小值：
$$ \begin{pmatrix} 25-18 & 18-18 & 21-18 & 30-18 \ 31-24 & 24-24 & 27-24 & 35-24 \ 28-22 & 22-22 & 25-22 & 33-22 \ 20-16 & 16-16 & 19-16 & 28-16 \end{pmatrix} = \begin{pmatrix} 7 & 0 & 3 & 12 \ 7 & 0 & 3 & 11 \ 6 & 0 & 3 & 11 \ 4 & 0 & 3 & 12 \end{pmatrix} $$
这是行减后的矩阵。
步骤 3：列减
找到行减后矩阵每列的最小值：
* 列 1 最小值：4
* 列 2 最小值：0
* 列 3 最小值：3
* 列 4 最小值：11
将每列元素减去其最小值：
$$ \begin{pmatrix} 7-4 & 0-0 & 3-3 & 12-11 \ 7-4 & 0-0 & 3-3 & 11-11 \ 6-4 & 0-0 & 3-3 & 11-11 \ 4-4 & 0-0 & 3-3 & 12-11 \end{pmatrix} = \begin{pmatrix} 3 & 0 & 0 & 1 \ 3 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 \end{pmatrix} $$
这是列减后的矩阵。
步骤 4：尝试覆盖零
尝试用最少直线覆盖所有的零。
矩阵中的零位于：(1,2), (1,3), (2,2), (2,3), (2,4), (3,2), (3,3), (3,4), (4,1), (4,2), (4,3)。
策略：优先覆盖零最多的行/列。
* 第 2 列有 4 个零：(1,2), (2,2), (3,2), (4,2)。用一条垂直线覆盖第 2 列。
* 剩下的零：(1,3), (2,3), (2,4), (3,3), (3,4), (4,1), (4,3)。
* 第 3 列有 3 个零：(1,3), (2,3), (3,3), (4,3)。用一条垂直线覆盖第 3 列。
* 剩下的零：(2,4), (3,4), (4,1)。
* 第 2 行有 1 个零：(2,4)。用一条水平线覆盖第 2 行。
* 剩下的零：(3,4), (4,1)。
* 第 3 行有 1 个零：(3,4)。用一条水平线覆盖第 3 行。
* 剩下的零：(4,1)。
* 第 4 行有 1 个零：(4,1)。用一条水平线覆盖第 4 行。
这样共使用了 2 条垂直线（第 2, 3 列）和 3 条水平线（第 2, 3, 4 行）。总共 5 条直线。这不是最少线数。
更高效的覆盖方式：
* 第 2 列有 4 个零。覆盖第 2 列。 (1条线)
* 剩下的零：(1,3), (2,3), (2,4), (3,3), (3,4), (4,1), (4,3)。
* 第 3 列有 3 个零。覆盖第 3 列。 (2条线)
* 剩下的零：(2,4), (3,4), (4,1)。
* 第 4 行有 1 个零：(4,1)。覆盖第 4 行。 (3条线)
* 剩下的零：(2,4), (3,4)。
* 第 2 行有 1 个零：(2,4)。覆盖第 2 行。(4条线)
* 剩下的零：(3,4)。
* 第 3 行有 1 个零：(3,4)。覆盖第 3 行。(5条线)
似乎直线数总是大于 n。这是因为我们没有找到最少的直线数。
正确的找到最少直线数的方法是：
矩阵中的零位置：(1,2), (1,3), (2,2), (2,3), (2,4), (3,2), (3,3), (3,4), (4,1), (4,2), (4,3)。
我们可以看到第2列全是零，覆盖第2列。
$$ \begin{pmatrix} 3 & \xcancel{0} & 0 & 1 \ 3 & \xcancel{0} & 0 & 0 \ 2 & \xcancel{0} & 0 & 0 \ 0 & \xcancel{0} & 0 & 1 \end{pmatrix} $$
剩下的零：(1,3), (2,3), (2,4), (3,3), (3,4), (4,1), (4,3)。
覆盖第3列：
$$ \begin{pmatrix} 3 & \xcancel{0} & \xcancel{0} & 1 \ 3 & \xcancel{0} & \xcancel{0} & 0 \ 2 & \xcancel{0} & \xcancel{0} & 0 \ 0 & \xcancel{0} & \xcancel{0} & 1 \end{pmatrix} $$
剩下的零：(2,4), (3,4), (4,1)。
现在零分布在不同的行和列，无法用更少的列覆盖。尝试用行覆盖：
覆盖第 2 行（包含零 (2,4)）
覆盖第 3 行（包含零 (3,4)）
覆盖第 4 行（包含零 (4,1)）
总共使用了 2 条垂直线（列 2, 3）和 3 条水平线（行 2, 3, 4）。总共 5 条线。
再试一种覆盖方法：
覆盖第 2 列。
覆盖第 3 列。
覆盖第 4 行（包含零 (4,1)）。
剩下的零：(2,4), (3,4)。它们都在第 4 列和行 2, 3 上。
覆盖第 4 列。
总共 3 条垂直线（列 2, 3, 4）和 1 条水平线（行 4）。总共 4 条线。
仔细观察矩阵：
$$ \begin{pmatrix} 3 & \underline{0} & \underline{0} & 1 \ 3 & \underline{0} & \underline{0} & \underline{0} \ 2 & \underline{0} & \underline{0} & \underline{0} \ \underline{0} & \underline{0} & \underline{0} & 1 \end{pmatrix} $$
零位于 (1,2), (1,3), (2,2), (2,3), (2,4), (3,2), (3,3), (3,4), (4,1), (4,2), (4,3)。
最少覆盖线：
覆盖列 2 (4个零)。
覆盖列 3 (4个零)。
剩下 (2,4), (3,4), (4,1)。
覆盖行 2 (1个零)。
剩下 (3,4), (4,1)。
覆盖行 3 (1个零)。
剩下 (4,1)。
覆盖行 4 (1个零)。
总共 2 列 + 3 行 = 5 条线。
这肯定不是最少线数。最少线数等于最大独立零数。
让我们寻找最大独立零数。例如：(4,1), (1,2), (2,4), (3,3)。这是 4 个独立零。所以最少线数应该是 4。
如何用 4 条线覆盖？
覆盖列 1 (1个零)
覆盖列 2 (4个零)
覆盖列 3 (4个零)
覆盖行 2 (3个零)
覆盖行 3 (3个零)
覆盖行 4 (1个零)
换个思路：
覆盖列 2 (4个零) – 1条线
剩下 (1,3), (2,3), (2,4), (3,3), (3,4), (4,1), (4,3)
覆盖列 3 (3个零) – 2条线
剩下 (2,4), (3,4), (4,1)
覆盖行 2 (1个零) – 3条线
剩下 (3,4), (4,1)
覆盖行 3 (1个零) – 4条线
剩下 (4,1)
未覆盖零：(4,1)。需要再加一条线。
正确的最小覆盖方法：
覆盖列 2 (4个零)。
覆盖列 3 (4个零)。
剩下零：(2,4), (3,4), (4,1)。
覆盖行 2 (包含 (2,4))。
剩下零：(3,4), (4,1)。
覆盖行 3 (包含 (3,4))。
剩下零：(4,1)。
覆盖行 4 (包含 (4,1))。
总共 5 条线。仍然不对。
一个系统性的最小覆盖方法（类似于最大匹配）：
矩阵零的位置：
(1,2), (1,3)
(2,2), (2,3), (2,4)
(3,2), (3,3), (3,4)
(4,1), (4,2), (4,3)
尝试匹配零：
W1 – T2
W2 – T4
W3 – T3
W4 – T1
这是 4 个独立零：(1,2), (2,4), (3,3), (4,1)。可以构成一个完美匹配。
根据柯尼希定理，最大独立零数 = 最小零覆盖线数。最大独立零数是 4。所以最少覆盖线数是 4。
如何用 4 条线覆盖这 4 个零？
覆盖 W1 行？ no, not effective for min cover
覆盖 T2 列？ yes, covers (1,2), (2,2), (3,2), (4,2)
让我们换一种更直观的找最小覆盖线的方法。
$$ \begin{pmatrix} 3 & \underline{0} & \underline{0} & 1 \ 3 & \underline{0} & \underline{0} & \underline{0} \ 2 & \underline{0} & \underline{0} & \underline{0} \ \underline{0} & \underline{0} & \underline{0} & 1 \end{pmatrix} $$
覆盖第 2 列 (4个零)
覆盖第 3 列 (3个零未覆盖)
剩下零：(1,3), (2,3), (2,4), (3,3), (3,4), (4,1), (4,3)
覆盖第 3 列 (3个零)
剩下零：(2,4), (3,4), (4,1)
覆盖第 4 行 (1个零)
剩下零：(2,4), (3,4)
覆盖第 2 行 (1个零)
剩下零：(3,4)
覆盖第 3 行 (1个零)
总计 2列 + 3行 = 5线。
这表明我的覆盖方法有问题，或者我的理解有问题。算法的标准覆盖方法不一定是启发式找零最多的行/列，而是基于二分图匹配的算法。不过，我们可以通过试错或观察来找到最少覆盖。
重新尝试最小覆盖：
覆盖零矩阵：
(1,2), (1,3)
(2,2), (2,3), (2,4)
(3,2), (3,3), (3,4)
(4,1), (4,2), (4,3)
观察发现：
列 2, 列 3, 列 4, 行 4 似乎是一个不错的覆盖。
覆盖列 2：零 (1,2), (2,2), (3,2), (4,2) 被覆盖。
剩下零：(1,3), (2,3), (2,4), (3,3), (3,4), (4,1), (4,3)。
覆盖列 3：零 (1,3), (2,3), (3,3), (4,3) 被覆盖。
剩下零：(2,4), (3,4), (4,1)。
覆盖列 4：零 (2,4), (3,4) 被覆盖。
剩下零：(4,1)。
覆盖行 4：零 (4,1) 被覆盖。
总共 4 条垂直线 (列 2, 3, 4) 和 1 条水平线 (行 4)。总计 5 条线。仍然不对。
再试一次：
覆盖第 2 列 (4个零)。
覆盖第 3 列 (3个零未覆盖)。
覆盖第 4 行 (包含 (4,1))。
覆盖第 2 行 (包含 (2,4))。
覆盖第 3 行 (包含 (3,4))。
还是5条线。
问题可能出在对步骤4的理解或执行上。最少直线覆盖所有零是一个独立的子问题。一个标准的方法是：
1. 找到一个最大匹配的零集合。
2. 从所有未匹配的行开始，标记它们。
3. 如果一个行被标记，且它包含一个零在未标记的列中，则标记该列。
4. 如果一个列被标记，且它包含一个匹配的零在未标记的行中，则标记该行。
5. 重复步骤 3 和 4 直到没有新的标记。
6. 最小覆盖线由所有未标记的行和所有标记的列组成。
让我们用这个方法来找覆盖线：
首先，找到一个最大独立零集合。一个可能的集合是 (4,1), (1,2), (2,4), (3,3)。这是 4 个零，互相独立。最大独立零数是 4。
所以，最小覆盖线数是 4。
如何画 4 条线？
根据标准方法：
1. 独立零集合：(4,1), (1,2), (2,4), (3,3)。
2. 哪些行是未匹配的？所有行都有匹配的零。
3. 哪些列是未匹配的？所有列都有匹配的零。
这方法似乎是用来找到匹配本身，而不是覆盖线。
回到直接覆盖：
$$ \begin{pmatrix} 3 & \underline{0} & \underline{0} & 1 \ 3 & \underline{0} & \underline{0} & \underline{0} \ 2 & \underline{0} & \underline{0} & \underline{0} \ \underline{0} & \underline{0} & \underline{0} & 1 \end{pmatrix} $$
零的位置：(1,2), (1,3), (2,2), (2,3), (2,4), (3,2), (3,3), (3,4), (4,1), (4,2), (4,3)。
覆盖第 2 列 (4个零)
覆盖第 3 列 (3个零未覆盖)
覆盖第 4 行 (1个零未覆盖)
剩下的零：(2,4), (3,4)。
覆盖第 4 列 (2个零未覆盖)。
总共：列 2, 列 3, 列 4, 行 4。 这是 4 条线！
$$ \begin{pmatrix} 3 & \xcancel{0} & \xcancel{0} & 1 \ 3 & \xcancel{0} & \xcancel{0} & \xcancel{0} \ 2 & \xcancel{0} & \xcancel{0} & \xcancel{0} \ \underline{\xcancel{0}} & \underline{\xcancel{0}} & \underline{\xcancel{0}} & \underline{1} \end{pmatrix} $$
覆盖线：列 2, 列 3, 列 4, 行 4。 总计 4 条线。
线数 L = 4。矩阵阶数 n = 4。 L = n。
达到最优条件！
步骤 6：寻找最优分配
现在我们需要从覆盖后的矩阵中找到 4 个独立的零。
$$ \begin{pmatrix} 3 & \underline{0} & \underline{0} & 1 \ 3 & \underline{0} \quad & \underline{0} \quad & \underline{0}^ \ 2 & \underline{0} \quad & \underline{0}^ & \underline{0} \ \underline{0}^* & \underline{0} \quad & \underline{0} \quad & 1 \end{pmatrix} $$
（下划线表示零，星号表示选中的零）
方法：优先选择只有一个零的行或列。
* 第 1 行：有两个零 (1,2), (1,3)。先跳过。
* 第 2 行：有三个零 (2,2), (2,3), (2,4)。先跳过。
* 第 3 行：有三个零 (3,2), (3,3), (3,4)。先跳过。
* 第 4 行：有三个零 (4,1), (4,2), (4,3)。先跳过。
- 第 1 列：有一个零 (4,1)。选择 (4,1)。划掉第 4 行和第 1 列。
$$ \begin{pmatrix} 3 & 0 & 0 & 1 \ \xcancel{3} & 0 & 0 & 0 \ \xcancel{2} & 0 & 0 & 0 \ \xcancel{\underline{0}} & \xcancel{\underline{0}} & \xcancel{\underline{0}} & \xcancel{1} \end{pmatrix} $$
剩下未划掉的：
$$ \begin{pmatrix} 3 & 0 & 0 & 1 \ – & 0 & 0 & 0 \ – & 0 & 0 & 0 \ – & – & – & – \end{pmatrix} $$
新的子矩阵：
$$ \begin{pmatrix} 0 & 0 & 1 \ 0 & 0 & 0 \ 0 & 0 & 0 \end{pmatrix} $$
对应原矩阵的行：1, 2, 3；列：2, 3, 4。
零的位置：(1,2), (1,3), (2,2), (2,3), (2,4), (3,2), (3,3), (3,4)。
继续在子问题中找只有一个零的行/列：
* 第 1 行：(1,2), (1,3)。
* 第 2 行：(2,2), (2,3), (2,4)。
* 第 3 行：(3,2), (3,3), (3,4)。
* 第 2 列：(1,2), (2,2), (3,2)。
* 第 3 列：(1,3), (2,3), (3,3)。
* 第 4 列：(2,4), (3,4)。
没有只有一个零的行或列了。任选一个零。
选 (2,4)。划掉第 2 行和第 4 列。
$$ \begin{pmatrix} 0 & 0 & \xcancel{1} \ \xcancel{0} & \xcancel{0} & \xcancel{0} \ 0 & 0 & \xcancel{0} \end{pmatrix} $$
剩下未划掉的：
$$ \begin{pmatrix} 0 & 0 \ 0 & 0 \end{pmatrix} $$
对应原矩阵的行：1, 3；列：2, 3。
零的位置：(1,2), (1,3), (3,2), (3,3)。
继续在子问题中找只有一个零的行/列：
* 第 1 行：(1,2), (1,3)。
* 第 3 行：(3,2), (3,3)。
* 第 2 列：(1,2), (3,2)。
* 第 3 列：(1,3), (3,3)。
没有只有一个零的行或列。任选一个零。
选 (1,2)。划掉第 1 行和第 2 列。
$$ \begin{pmatrix} \xcancel{0} & \xcancel{0} \ 0 & 0 \end{pmatrix} $$
剩下未划掉的：
$$ \begin{pmatrix} 0 \end{pmatrix} $$
对应原矩阵的行：3；列：3。
零的位置：(3,3)。
选 (3,3)。
我们选中的零是：(4,1), (2,4), (1,2), (3,3)。
检查：
W1 -> T2 (零 (1,2))
W2 -> T4 (零 (2,4))
W3 -> T3 (零 (3,3))
W4 -> T1 (零 (4,1))
这是一个有效的分配方案，每个工人和每个任务都只被分配一次，并且都对应矩阵中的零。
步骤 7：计算最小总成本
回到原始成本矩阵 C，查找这些零对应的原始成本：
* (1,2) 对应成本 $c_{12} = 18$
* (2,4) 对应成本 $c_{24} = 35$
* (3,3) 对应成本 $c_{33} = 25$
* (4,1) 对应成本 $c_{41} = 20$
最小总成本 = $18 + 35 + 25 + 20 = 98$。
这个分配方案 (W1->T2, W2->T4, W3->T3, W4->T1) 的总成本是 98。根据匈牙利算法，这是该分配问题的最优解。
演示中如果步骤 4 的线数 L < n，如何执行步骤 5 并继续？
假设我们在第一次覆盖后只画了 3 条线。例如，我们覆盖了列 2, 列 3 和行 4。
$$ \begin{pmatrix} 3 & \xcancel{0} & \xcancel{0} & 1 \ 3 & \xcancel{0} & \xcancel{0} & 0 \ 2 & \xcancel{0} & \xcancel{0} & 0 \ \underline{0} & \underline{\xcancel{0}} & \underline{\xcancel{0}} & \underline{1} \end{pmatrix} $$
未被覆盖的元素是：(1,1)=3, (1,4)=1, (2,1)=3, (2,4)=0, (3,1)=2, (3,4)=0。
未被覆盖的元素中最小值为 0。
如果最小未覆盖元素为 0，这意味着未覆盖区域中本身就有零，但这些零无法通过当前的覆盖方式与被覆盖区域的零一起构成 n 个独立零。在这种情况下，最小值为 0 的调整（减 0，加 0）不会改变矩阵。这通常意味着你在找最小覆盖线时可能犯了错误，或者算法需要通过一个非零的最小值来进行改进。
让我们修改一下成本矩阵，使得第一次覆盖后最小未覆盖元素大于 0，以便演示步骤 5。
假设原始矩阵是：
$$ C = \begin{pmatrix} 11 & 4 & 7 & 16 \ 17 & 10 & 13 & 21 \ 14 & 8 & 11 & 19 \ 6 & 0 & 3 & 14 \end{pmatrix} $$
步骤 2：行减
minima: 4, 10, 8, 0
$$ \begin{pmatrix} 7 & 0 & 3 & 12 \ 7 & 0 & 3 & 11 \ 6 & 0 & 3 & 11 \ 6 & 0 & 3 & 14 \end{pmatrix} $$
步骤 3：列减
minima: 6, 0, 3, 11
$$ \begin{pmatrix} 1 & 0 & 0 & 1 \ 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 3 \end{pmatrix} $$
步骤 4：尝试覆盖零
零位置：(1,2), (1,3), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4), (4,1), (4,2), (4,3)。
覆盖列 2 (4个零)。
覆盖列 3 (4个零未覆盖)。
覆盖行 3 (3个零未覆盖)。
剩下零：(1,1)=1, (1,4)=1, (2,1)=1, (2,4)=0, (4,1)=0, (4,4)=3
覆盖零：(2,4), (4,1)。
覆盖行 2 (1个零未覆盖)。
覆盖行 4 (1个零未覆盖)。
总计：列 2, 列 3, 行 2, 行 3, 行 4 -> 5条线？
再试最小覆盖：
零位置：
(1,2), (1,3)
(2,2), (2,3), (2,4)
(3,1), (3,2), (3,3), (3,4)
(4,1), (4,2), (4,3)
覆盖 列 2 (4个零)。
覆盖 列 3 (4个零)。
剩下零：(2,4), (3,1), (3,4), (4,1)。
覆盖 行 3 (2个零)。
剩下零：(2,4), (4,1)。
覆盖 行 2 (1个零)。
剩下零：(4,1)。
覆盖 行 4 (1个零)。
总计：列 2, 列 3, 行 3, 行 2, 行 4 -> 5条线。
这矩阵零太多了。换一个例子。
原始矩阵：
$$ C = \begin{pmatrix} 8 & 2 & 5 & 4 \ 9 & 3 & 5 & 5 \ 7 & 4 & 2 & 3 \ 8 & 5 & 4 & 6 \end{pmatrix} $$
步骤 2：行减
minima: 2, 3, 2, 4
$$ \begin{pmatrix} 6 & 0 & 3 & 2 \ 6 & 0 & 2 & 2 \ 5 & 2 & 0 & 1 \ 4 & 1 & 0 & 2 \end{pmatrix} $$
步骤 3：列减
minima: 4, 0, 0, 1
$$ \begin{pmatrix} 2 & 0 & 3 & 1 \ 2 & 0 & 2 & 1 \ 1 & 2 & 0 & 0 \ 0 & 1 & 0 & 1 \end{pmatrix} $$
步骤 4：尝试覆盖零
零位置：(1,2), (2,2), (3,3), (3,4), (4,1), (4,3)。
试图找到最少覆盖线：
覆盖 列 2 (2个零)。
剩下零：(3,3), (3,4), (4,1), (4,3)。
覆盖 列 3 (2个零)。
剩下零：(3,4), (4,1)。
覆盖 行 3 (1个零)。
剩下零：(4,1)。
覆盖 行 4 (1个零)。
总共 4 条线。 L=4, n=4。达到最优。
这个例子也直接达到了最优。看来要演示步骤 5 需要仔细构造矩阵。
再换一个例子，确保需要步骤 5。
原始矩阵：
$$ C = \begin{pmatrix} 5 & 2 & 4 \ 6 & 3 & 5 \ 7 & 4 & 6 \end{pmatrix} $$
步骤 2：行减
minima: 2, 3, 4
$$ \begin{pmatrix} 3 & 0 & 2 \ 3 & 0 & 2 \ 3 & 0 & 2 \end{pmatrix} $$
步骤 3：列减
minima: 3, 0, 2
$$ \begin{pmatrix} 0 & 0 & 0 \ 0 & 0 & 0 \ 0 & 0 & 0 \end{pmatrix} $$
这个矩阵全是零！
步骤 4：覆盖零
用最少线覆盖所有零。只需要 3 条线：覆盖任何 3 行或任何 3 列。L=3, n=3。达到最优。
分配：例如 W1-T1, W2-T2, W3-T3。成本 5+3+6 = 14。
看来我需要一个需要矩阵改进的 4×4 例子。
原始矩阵：
$$ C = \begin{pmatrix} 1 & 2 & 3 & 4 \ 2 & 4 & 6 & 8 \ 3 & 6 & 9 & 12 \ 4 & 8 & 12 & 16 \end{pmatrix} $$
步骤 2：行减
minima: 1, 2, 3, 4
$$ \begin{pmatrix} 0 & 1 & 2 & 3 \ 0 & 2 & 4 & 6 \ 0 & 3 & 6 & 9 \ 0 & 4 & 8 & 12 \end{pmatrix} $$
步骤 3：列减
minima: 0, 1, 2, 3
$$ \begin{pmatrix} 0 & 0 & 0 & 0 \ 0 & 1 & 2 & 3 \ 0 & 2 & 4 & 6 \ 0 & 3 & 6 & 9 \end{pmatrix} $$
步骤 4：覆盖零
零位置：(1,1), (1,2), (1,3), (1,4), (2,1), (3,1), (4,1)。
最少覆盖线：覆盖第 1 行 (4个零) 和 第 1 列 (3个零)。总共 2 条线。L=2 < n=4。需要改进！
被覆盖元素：第 1 行所有元素，第 1 列所有元素。
未被覆盖元素：
$$ \begin{pmatrix} – & – & – & – \ – & 1 & 2 & 3 \ – & 2 & 4 & 6 \ – & 3 & 6 & 9 \end{pmatrix} $$
未被覆盖的元素是：1, 2, 3, 2, 4, 6, 3, 6, 9。
步骤 5：矩阵改进
未被覆盖元素中的最小值为 $\theta = 1$。
将未被覆盖的元素减去 $\theta=1$：
$$ \begin{pmatrix} – & – & – & – \ – & 1-1 & 2-1 & 3-1 \ – & 2-1 & 4-1 & 6-1 \ – & 3-1 & 6-1 & 9-1 \end{pmatrix} = \begin{pmatrix} – & – & – & – \ – & 0 & 1 & 2 \ – & 1 & 3 & 5 \ – & 2 & 5 & 8 \end{pmatrix} $$
位于两条直线交汇处的元素：(1,1)。
将交汇处元素加上 $\theta=1$：
$$ \begin{pmatrix} 0+1 & – & – & – \ – & – & – & – \ – & – & – & – \ – & – & – & – \end{pmatrix} = \begin{pmatrix} 1 & – & – & – \ – & – & – & – \ – & – & – & – \ – & – & – & – \end{pmatrix} $$
被一条线覆盖但不在交汇处的元素保持不变。
新的矩阵：
$$ \begin{pmatrix} 1 & 0 & 0 & 0 \ 0 & 0 & 1 & 2 \ 0 & 1 & 3 & 5 \ 0 & 2 & 5 & 8 \end{pmatrix} $$
返回步骤 4。
步骤 4：尝试覆盖零（第二次）
零位置：(1,2), (1,3), (1,4), (2,1), (2,2), (3,1), (4,1)。
最少覆盖线：
覆盖 列 1 (3个零)。
剩下零：(1,2), (1,3), (1,4), (2,2)。
覆盖 行 1 (3个零)。
剩下零：(2,2)。
覆盖 行 2 或 列 2 (1个零)。
总共 3 条线 (列 1, 行 1, 行 2)。L=3 < n=4。需要再次改进！
被覆盖的元素：第 1 列所有元素，第 1 行所有元素，第 2 行所有元素。
未被覆盖元素：
$$ \begin{pmatrix} – & – & – & – \ – & – & – & – \ – & 1 & 3 & 5 \ – & 2 & 5 & 8 \end{pmatrix} $$
未被覆盖的元素是：1, 3, 5, 2, 5, 8。
步骤 5：矩阵改进（第二次）
未被覆盖元素中的最小值为 $\theta = 1$。
将未被覆盖的元素减去 $\theta=1$：
$$ \begin{pmatrix} – & – & – & – \ – & – & – & – \ – & 1-1 & 3-1 & 5-1 \ – & 2-1 & 5-1 & 8-1 \end{pmatrix} = \begin{pmatrix} – & – & – & – \ – & – & – & – \ – & 0 & 2 & 4 \ – & 1 & 4 & 7 \end{pmatrix} $$
位于两条直线交汇处的元素：(1,1), (1,2), (1,3), (1,4), (2,1)。
被三条直线覆盖的元素：(1,1)。它在列 1, 行 1, 行 2 的交汇处。这里我们按照规则，位于交汇处的都加 $\theta$。
将交汇处元素加上 $\theta=1$：
(1,1): 1 + 1 = 2
(1,2), (1,3), (1,4) (行1与列1交汇): 0 + 1 = 1
(2,1) (行2与列1交汇): 0 + 1 = 1
新的矩阵：
$$ \begin{pmatrix} 2 & 1 & 1 & 1 \ 1 & 0 & 1 & 2 \ 0 & 0 & 2 & 4 \ 0 & 1 & 4 & 7 \end{pmatrix} $$
返回步骤 4。
步骤 4：尝试覆盖零（第三次）
零位置：(2,2), (3,1), (3,2), (4,1)。
最少覆盖线：
覆盖 列 1 (2个零)。
剩下零：(2,2), (3,2)。
覆盖 列 2 (2个零)。
总共 2 条线 (列 1, 列 2)。L=2 < n=4。需要再次改进！
被覆盖的元素：第 1 列所有元素，第 2 列所有元素。
未被覆盖元素：
$$ \begin{pmatrix} – & – & 1 & 1 \ – & – & 1 & 2 \ – & – & 2 & 4 \ – & – & 4 & 7 \end{pmatrix} $$
未被覆盖的元素是：1, 1, 1, 2, 2, 4, 4, 7。
步骤 5：矩阵改进（第三次）
未被覆盖元素中的最小值为 $\theta = 1$。
将未被覆盖的元素减去 $\theta=1$：
$$ \begin{pmatrix} – & – & 0 & 0 \ – & – & 0 & 1 \ – & – & 1 & 3 \ – & – & 3 & 6 \end{pmatrix} $$
位于两条直线交汇处的元素：(1,1), (1,2), (2,1), (2,2), (3,1), (3,2), (4,1), (4,2)。
将交汇处元素加上 $\theta=1$：
(1,1): 2+1=3
(1,2): 1+1=2
(2,1): 1+1=2
(2,2): 0+1=1
(3,1): 0+1=1
(3,2): 0+1=1
(4,1): 0+1=1
(4,2): 1+1=2
新的矩阵：
$$ \begin{pmatrix} 3 & 2 & 0 & 0 \ 2 & 1 & 0 & 1 \ 1 & 1 & 1 & 3 \ 1 & 2 & 3 & 6 \end{pmatrix} $$
返回步骤 4。
步骤 4：尝试覆盖零（第四次）
零位置：(1,3), (1,4), (2,3)。
最少覆盖线：
覆盖 列 3 (2个零)。
剩下零：(1,4)。
覆盖 行 1 或 列 4 (1个零)。
总共 2 条线 (列 3, 行 1)。L=2 < n=4。需要再次改进！
被覆盖的元素：第 3 列所有元素，第 1 行所有元素。
未被覆盖元素：
$$ \begin{pmatrix} – & – & – & – \ 2 & 1 & – & 1 \ 1 & 1 & – & 3 \ 1 & 2 & – & 6 \end{pmatrix} $$
未被覆盖的元素是：2, 1, 1, 1, 1, 3, 1, 2, 6。
步骤 5：矩阵改进（第四次）
未被覆盖元素中的最小值为 $\theta = 1$。
将未被覆盖的元素减去 $\theta=1$：
$$ \begin{pmatrix} – & – & – & – \ 1 & 0 & – & 0 \ 0 & 0 & – & 2 \ 0 & 1 & – & 5 \end{pmatrix} $$
位于两条直线交汇处的元素：(1,3), (2,3), (3,3), (4,3), (1,1), (1,2), (1,4)。
将交汇处元素加上 $\theta=1$：
(1,3): 0+1=1
(1,4): 0+1=1
(2,3): 0+1=1
(3,3): 1+1=2
(4,3): 3+1=4
(1,1): 3+1=4
(1,2): 2+1=3
(1,4): 0+1=1 (Oops, (1,4)是零，被覆盖)
新的矩阵：
$$ \begin{pmatrix} 4 & 3 & 1 & 1 \ 1 & 0 & 1 & 0 \ 0 & 0 & 2 & 2 \ 0 & 1 & 4 & 5 \end{pmatrix} $$
返回步骤 4。
步骤 4：尝试覆盖零（第五次）
零位置：(1,3), (1,4), (2,2), (2,4), (3,1), (3,2), (4,1)。
最少覆盖线：
覆盖 列 1 (2个零)。
剩下零：(1,3), (1,4), (2,2), (2,4), (3,2)。
覆盖 列 2 (2个零)。
剩下零：(1,3), (1,4), (2,4)。
覆盖 列 4 (2个零)。
剩下零：(1,3)。
覆盖 行 1 或 列 3 (1个零)。
总共 4 条线 (列 1, 列 2, 列 4, 行 1)。L=4 = n=4。达到最优！
步骤 6：寻找最优分配
在新矩阵中寻找独立零：
$$ \begin{pmatrix} 4 & 3 & \underline{0}^ & \underline{0} \ 1 & \underline{0} & 1 & \underline{0}^ \ \underline{0}^* & \underline{0} & 2 & 2 \ \underline{0} & 1 & 4 & 5 \end{pmatrix} $$
找只有一个零的行/列：
* 第 1 行：两个零 (1,3), (1,4)。
* 第 2 行：两个零 (2,2), (2,4)。
* 第 3 行：两个零 (3,1), (3,2)。
* 第 4 行：一个零 (4,1)。选择 (4,1)。划掉行 4, 列 1。
$$ \begin{pmatrix} 4 & 3 & 0 & 0 \ 1 & 0 & 1 & 0 \ 0 & 0 & 2 & 2 \ \xcancel{0} & \xcancel{1} & \xcancel{4} & \xcancel{5} \end{pmatrix} $$
剩下矩阵：
$$ \begin{pmatrix} 4 & 3 & 0 & 0 \ 1 & 0 & 1 & 0 \ 0 & 0 & 2 & 2 \end{pmatrix} $$
对应原矩阵的行：1, 2, 3；列：2, 3, 4。
零位置：(1,3), (1,4), (2,2), (2,4), (3,2), (3,3)? (3,3)在原始矩阵中是零，但在新矩阵中不是。零位置是 (1,3), (1,4), (2,2), (2,4), (3,2)。
$$ \begin{pmatrix} 3 & 0 & 0 \ 0 & 1 & 0 \ 0 & 2 & 2 \end{pmatrix} $$
对应原矩阵的行：1, 2, 3；列：2, 3, 4。
零位置：(1,2), (1,3), (2,2), (2,4), (3,2)。
再找只有一个零的行/列：
* 第 1 行：(1,2), (1,3)
* 第 2 行：(2,2), (2,4)
* 第 3 行：(3,2) -> 只有一个零！选择 (3,2)。划掉行 3, 列 2。
$$ \begin{pmatrix} 3 & \xcancel{0} & 0 \ 0 & \xcancel{1} & 0 \ \xcancel{0} & \xcancel{\underline{0}} & \xcancel{2} \end{pmatrix} $$
剩下矩阵：
$$ \begin{pmatrix} 3 & 0 \ 0 & 0 \end{pmatrix} $$
对应原矩阵的行：1, 2；列：3, 4。
零位置：(1,3), (2,4)。
选择 (1,3)。划掉行 1, 列 3。剩下 (2,4)。
$$ \begin{pmatrix} \xcancel{3} & \xcancel{0} \ 0 & 0 \end{pmatrix} $$
剩下 (2,4)。选择 (2,4)。
选中的零是：(4,1), (3,2), (1,3), (2,4)。
检查：
W1 -> T3 (零 (1,3))
W2 -> T4 (零 (2,4))
W3 -> T2 (零 (3,2))
W4 -> T1 (零 (4,1))
这是一个有效的分配方案。
步骤 7：计算最小总成本
回到原始成本矩阵 C，查找这些零对应的原始成本：
* (1,3) 对应成本 $c_{13} = 3$
* (2,4) 对应成本 $c_{24} = 8$
* (3,2) 对应成本 $c_{32} = 4$
* (4,1) 对应成本 $c_{41} = 4$
最小总成本 = $3 + 8 + 4 + 4 = 19$。
这个示例虽然经过多次迭代，但也完整展示了匈牙利算法如何通过矩阵改进逐步逼近最优解的过程。
六、匈牙利算法的变体：最大化问题
匈牙利算法的标准形式是解决最小化问题。如果我们要解决最大化问题（例如最大化总收益），可以很容易地将其转化为最小化问题。
方法：
1. 找到原始收益矩阵中的最大元素 $M$。
2. 构建一个新的成本矩阵 C’，其中每个元素 $c’{ij} = M – r{ij}$，这里的 $r_{ij}$ 是原始收益矩阵中的元素。
3. 对新的成本矩阵 C’ 应用匈牙利算法，找到最小成本分配。
4. 这个在 C’ 中找到的最小成本分配方案，就是原始收益矩阵中总收益最大的分配方案。最大总收益可以通过原始收益矩阵中对应元素的总和计算得到。
为什么这个方法有效？
最大化 $\sum r_{ij} x_{ij}$
等价于 最大化 $\sum (M – c’{ij}) x{ij}$
等价于 最大化 $\sum M x_{ij} – \sum c’{ij} x{ij}$
由于 $\sum x_{ij}$ 在任何有效分配方案中都是常数 n (即 $\sum_{i}\sum_{j} x_{ij} = n$)，所以 $\sum M x_{ij} = n \times M$ 也是一个常数。
因此，最大化 $\sum M x_{ij} – \sum c’{ij} x{ij}$ 等价于 最小化 $\sum c’{ij} x{ij}$ (因为 $nM$ 是常数)。
所以，在变换后的成本矩阵 C’ 中找到最小成本分配，就能解决原始收益矩阵 R 中的最大化问题。
七、总结与展望
匈牙利算法是一个优雅而强大的组合优化算法，专门用于解决完全分配问题（n个工人对n个任务的最小成本或最大收益分配）。它通过巧妙的矩阵变换，在不改变最优解的前提下，逐步在矩阵中创建零，并通过判断能否用 n 条直线覆盖所有零来检查当前解是否最优。如果不是，则通过调整未覆盖元素的最小值来改进矩阵，循环往复直到找到最优解。
算法的核心在于：
* 等价变换（行/列加减常数）不改变最优解。
* 基于零的分配如果存在 n 个独立零，则该分配为最优。
* 覆盖零操作与二分图最大匹配/最小顶点覆盖定理紧密相关。
* 矩阵改进操作能创造新的零，推动算法向最优解逼近。
尽管存在 O(n^3) 的更高效实现，匈牙利算法直观的 O(n^4) 版本也相对容易理解和实现，使其成为学习分配问题算法的绝佳起点。
需要注意的是，匈牙利算法解决的是完全分配问题。对于非完全分配问题（工人数量和任务数量不等，或者不是每个工人都能完成每个任务），以及更一般的指派问题（如每个工人可以执行多个任务等），可能需要使用其他更通用的技术，如最小费用最大流算法等。然而，匈牙利算法作为解决特定类型分配问题的经典方法，其思想和原理对于理解更复杂的组合优化问题求解技术具有重要的启发意义。
希望本文通过详细的步骤讲解、原理剖析和实例演示，帮助你全面理解了匈牙利算法。掌握了这个算法，你将能高效地解决许多实际中的分配与匹配难题。