匈牙利算法的优缺点 匈牙利法的由来？

匈牙利法的由来？

匈牙利算法，是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，由匈牙利数学家Edmonds于1965年提出，因而得名。

匈牙利算法的优缺点？

匈牙利算法，是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，由匈牙利数学家Edmonds于1965年提出，因而得名。

拓展资料

一、定义

匈牙利算法（Hungarian algorithm），其核心就是寻找增广路径，是一种用增广路径求二分图最大匹配的算法。

匈牙利算法是一种在P问题内（多项式时间内）求解任务分配问题的组合优化算法。它推动了后来的原始对偶方法。

匈牙利算法是美国数学家哈罗德·库恩于1955年提出的。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。

二、名词解释

1、二分图与匹配

二分图（Bipartite graph）又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，A、B内部的点不相交，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i∈A, j∈B)，则称图G为一个二分图。

如图2-1左边图转换成一个二分图。

图2-1

一个图为二分图的充分必要条件是至少有两个点，并且如果存在回路的话，那么回路的长度(长度指的是该回路连接的点的数目)必须为偶数。

二分图的匹配：

给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

极大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。

最大匹配是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。匈牙利算法就是找出这样一个最大匹配的边数。对于图来说，最大匹配不是唯一的，但是最大匹配的大小是唯一的。

如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完美匹配。图2-2中图d就是二分图的一个完全匹配（同时也是最大匹配），但是最大匹配不总是完全匹配。

例子1 如图2-2所示

图2-2

图a，图b，图c，图d中任意两条边的连接的顶点都没有相同的(换句话说，n条边必须连接2 * n个不相同的顶点)。所以他们都是图G的匹配。

例子2 如图2-3所示

图2-3

红线部分代表匹配或完美匹配。

2、增广路径

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路径：若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。

换一个说法，从一个未匹配点出发，走交替路，如果途径另一个未匹配点，则这条交替路称为增广路。如图2-4所示，红色结点代表匹配结点， 红色边代表匹配边，黑色边代表非匹配边。

图2-4

增广路径：1 -> 2->3->4->5->6。1、6非匹配点，中间结点2、3、4、5是匹配点。黑色标记 1—>2、3—>4、5—>6是非匹配边，红色标记2-3、4-5是匹配边。

增广路径的首尾是非匹配点。因此，增广路径的第一条和最后一条边，必然是非匹配边；同时它的第二条边（如果有）和倒数第二条边（如果有），必然是匹配边；以及第三条边（如果有）和倒数第三条边（如果有），一定是非匹配边。

增广路径从非匹配边开始，匹配边和非匹配边依次交替，最后由非匹配边结束。这样一来，增广路径中非匹配边的数目会比匹配边大 1。

如果我们置换增广路径中的匹配边和非匹配边，由于增广路径的首尾是非匹配点，其余则是匹配点，这样的置换不会影响原匹配中的匹配点，匹配中不包含在该路径中的其他匹配边也不受到影响，因而不会破坏匹配；增广路径的置换，可以得到比原有匹配更大的匹配（具体来说，匹配的边数增加了 1）。

增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，匹配边数目比原来多了 1 条。

由于二分图的最大匹配必然存在（比如，上限是包含所有顶点的完全匹配），所以，在任意匹配的基础上，如果我们有办法不断地搜寻出增广路径，直到最终我们找不到新的增广路径为止，我们就有可能得到二分图的一个最大匹配。这就是匈牙利算法的核心思想。

唯一的问题在于，在这种贪心的思路下，我们如何保证不存在例外的情况，即：当前匹配不是二分图的最大匹配，但已找不到一条新的增广路径。

我们从反证法考虑，即假设存在这样的情况。因为当前匹配不是二分图的最大匹配，那么在两个集合中，分别至少存在一个非匹配点。那么情况分为两种：

1)、这两个点之间存在一条边——那么我们找到了一条新的增广路径，产生矛盾；

2)、这两个点之间不存在直接的边，即这两个点分别都只与匹配点相连——那么：

a、如果这两个点可以用已有的匹配点相连，那么我们找到了一条新的增广路径，产生矛盾；

b、如果这两个点无法用已有的匹配点相连，那么这两个点也就无法增加匹配中边的数量，也就是我们已经找到了二分图的最大匹配，产生矛盾。

在所有可能的情况，上述假设都会产生矛盾。因此假设不成立，亦即贪心算法必然能求得最大匹配的解。

由增广路径的定义可以推出的三个结论：

①P的路径长度必定为奇数，第一条边和最后一条边都不属于M；

②P经过置换(取反)操作可以得到一个更大的匹配M；

③M为G的最大匹配当且仅当不存在相对于M的增广路径。

增广路的应用

• 增广路用于证明最大匹配问题。
• 增广路主要应用于匈牙利算法中，用于求二分图最大匹配。

3、匈牙利树

匈牙利树一般由 BFS 构造（类似于 BFS 树）。从一个未匹配点出发运行 BFS（唯一的限制是，必须走交替路），直到不能再扩展为止。如图2-5，由Fig.7，可以得到Fig.8的一棵 BFS 树。

图2-5

这棵树存在一个叶子结点为非匹配点（7号），但是匈牙利树要求所有叶子结点均为匹配点，因此这不是一棵匈牙利树（顺便说一句，Fig.8 中非匹配根节点2到非匹配叶结点7显然是一条增广路，沿这条增广路扩充后将得到一个完美匹配）。在Fig.9中，从2号结点出发就会得到一棵匈牙利树。

匈牙利树要求所有叶子结点均为匹配点，它就是把存在的可连接的匹配点都列出来。

4、二分图最大匹配数=最小点覆盖率

二分图的最小点覆盖的理解：找到最少的一些点，使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是，删除包含这些点的边，可以删掉所有边。

三、匈牙利算法复杂度

设V为二分图左边的顶点数，E为二分图中边的数目。匈牙利算法的实现以与点集合 V 为基础，每次在集合V中选一个顶点 Vi 做增广路径的起点搜索增广路径。搜索增广路径需要遍历边及E内的所有边，遍历方法可以采用深度优先遍历（DFS），也可以采用广度优先遍历（BFS），无论什么方法，其时间复杂度都是 O(E)。匈牙利算法每个顶点 Vi 只能选择一次，因此算法的整体时间复杂度是 O(V*E)，总的来说，是一个相当高效的算法。