本文转自 维基百科

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes K?nig和Jen? Egerváry的工作之上创建起来的。

詹姆士·芒克勒斯在1957年回顾了该算法，并发现（强）多项式时间的。此后该算法被称为Kuhn–Munkres算法或Munkres分配算法。原始算法的时间复杂度为O(n⁴)，但Edmonds与卡普发现可以修改算法达到O(n³)运行时间，富泽也独立发现了这一点。Ford和Fulkerson将该方法推广到了一般运输问题。2006年发现卡尔·雅可比在19世纪就解决了指派问题，该解法在他死后在1890年以拉丁文发表。

 Layman对指派问题的解释

你有三个工人：吉姆，史提夫和艾伦。 你需要其中一个清洁浴室，另一个打扫地板，第三个洗窗，但他们每个人对各项任务要求不同数目数量的钱。 以最低成本的分配工作的方式是什么？ 可以用工人做工的成本矩阵来表示该问题。例如： 

当把匈牙利方法应用于上面的表格时，会给出最低成本：为6美元，让吉姆清洁浴室、史提夫打扫地板、艾伦清洗窗户就可以达到这一结果。 

设定

给定一个n*n的非负矩阵，其中第 i 行第 j 列元素表示把第 i 个工人派到第 j 个工作的成本。我们必须找到成本最低的工人工作分配。如果目标是找到最高成本的分配，该问题可以将每个成本都换为最高一个成本减去该成本以适应题目。 

如果用二分图来阐述该问题可以更容易描述这个算法。对于一个有 n 个工人节点（S）与 n 个工作节点（ T ）的完全二分图 ，每条边都有   的非负成本。我们要找到最低成本的完美匹配。 

如果函数满足对于每个都有，则把该函数叫做势。势 y 的值为。可以看出，每个完美匹配的成本最低是每个势的值。匈牙利算法找出了完美匹配及与之成本/值相等的势，这证明了两者的最优性。实际上它找到了紧边集的完美匹配：紧边 i,j 是指对于势 y 满足。我们将紧边子图表示为 。中的完美匹配的成本（如果存在）就等于 y 的值。 

用二分图描述此算法

在算法中我们维持的势 y 和方向（表示为），该方向有从 T 到 S  的边构成匹配 M  的性质。初始时，y 处处为 0， 所有边都由  S 指向 T （因此 M 为空）。每一步中，我们或者改变 y  使其值增加， 或者改变方向以得到更多的边。我们保持 M  的所有边都是紧边不发生改变。当 M  为完美匹配时结束。 

在一般的步骤中，令和为 M 未覆盖的节点 （则包含  S 中入度为零的节点，而中包含  T 中出度为零的节点）。 令   为从 只沿紧边的有向路径可到达的节点。可由广度优先搜索求得。 

若非空，则将中从到的有向路径反向。则相应匹配数增加1。 

若为空，则令。为正，因为与之间没有紧边。 在中的节点将y增加 并在中节点将 y  减小 得到 y 的仍然是势。图改变了，但它仍包含 M 。我们把新的边从 S 指向 T。 由的定义，可达的节点集 Z 增大（注意到紧边的数量不一定增加）。 

我们重复这些步骤直到M为完美匹配，该情形下给出的是最小成本（即时间消耗）的匹配。此版本的运行时间为：增广  n 次， 在 M  不改变的一个阶段中，势最多改变 n  次（因为 Z 每次都增加）。改变势所需的时间在。 

矩阵解释

给定 n 个工人和任务，以及一个包含分配给每个工人一个任务的成本的n*n矩阵，寻找成本最小化分配。 

首先把问题写成下面的矩阵形式 ：

其中a,b,c,d是执行任务 1, 2, 3, 4 的工人。a₁,a₂,a₃,a₄分别表示当工人   做任务 1, 2, 3, 4 时的时间损失（成本）。对于其他符号也同样适用。该矩阵是方阵，所以每个工人只能执行一个任务。 

第 1 步 

接下来我们对矩阵的列进行操作。将所有a_i（i 从 1 到 4）中最小的元素取走，并用将每个元素都减去刚刚取走的元素。这会让该列至少出现一个零（当一行有两个相等的最小元素时会得到多个零）。对此过程为所有行重复。我们现在得到一个每行至少有一个零的矩阵。现在我们尝试给工人指派任务，以使每个工人只做一项任务，并且每个情况的耗散都为零。说明如下。  

用 0' 表示的零为已指派的任务。 

第 2 步 

有时此阶段的该矩阵不能匹配指派的要求，例如下面所示矩阵。 

在上述情形下，不能做出指派。注意到任务 1 由工人 a 和 c 做都很高效。只是不能把两个工人分配到同一个任务中去。还注意到，没有任何一个工人能有效地任务 3。 为了克服这个问题，我们对所有列重复上述流程（即每一列所有元素都减去该列最小元素）并检查是否可以完成分配。 

大多数情况下，这都会给出结果，但如果仍然是不可行，那么我们需要继续下去。 

第 3 步 

必须用尽可能少的列或行标记来覆盖矩阵中的所有零。下面的过程是完成这个要求的一种方法： 

首先，尽可能多地分配任务。 

(1)第 1 行有一个零，所以分配了。第 3 行的 0 由于处于同一列而被划掉。 

(2)第 2 行有一个零，所以分配了。 

(3)第 3 行只有一个已经划掉的零，所以不能分配。 

(4)第 4 行有两个未划掉的零。可以分配任何一个（都是最优） ，并将另一个零划去。 

或者，分配的是第 3 行的 0，就会使第 1 行的 0 被划掉。 

现在到了画图的部分。 

(1)标记所有未分配的行（第 3 行）。 

(2)标记所有新标记的行中 0所在（且未标记）的对应列（第 1 列）。 

(3)标记所有在新标记的列中有分配的行（第 1 行）。 

(4)对所有未分配的行重复上述过程。 

现在划掉所有已标记的列和未标记的行（第 1 列和第 2, 4 行）。 

上述详细的描述只是画出覆盖所有 0 的（直、行）线的一种方法。也可以使用其他方法。 

第 4 步 

现在删除已画线的行和列。这将留下一个矩阵如下： 

返回到步骤 1，然后重复这个过程，直到矩阵是空的。 

用过就知道，很实用，推荐~~