Revision 34005898 of "匈牙利算法" on zhwiki

{{noteTA
|G1=IT
}}
'''匈牙利算法'''是众多用于解决线性任务分配问题的算法之一，是用来解决[[二分图]]最大[[匹配]]问题的经典[[算法]]，可以在多项式时间内解决问题，由美国[[数学家]]Harold Kuhn于1955年提出。此算法之所以被称作'''匈牙利算法'''是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上建立起来的。

== 问题简介 ==

设G=(V,E)是一个[[无向图]]。如顶点集V可分割为两个互不相交的[[子集]]V1,V2之并，并且图中每条边依附的两个[[顶点]]都分属于这两个不同的子集。则称图G为'''二分图'''。二分图也可记为G=(V1,V2,E)。

给定一个[[二分图]]G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的子集中边数最大的子集称为图的'''最大匹配问题'''（maximal matching problem）

如果图的所有[[顶点]]都与某匹配中的一条边相关联，则称此匹配为'''完全匹配'''，也'''称作完备'''，'''完美匹配'''。

== 算法描述 ==

　　求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的时间复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。下面介绍用[[增广路]]求最大匹配的方法（称作'''匈牙利算法'''，由数学家Harold Kuhn于1955年提出）。

　　[[增广路]]的定义（也称[[增广轨]]或[[交错轨]]）：

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

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

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

　　2－将M和P进行异或操作（去同存异）可以得到一个更大的匹配M’。

　　3－M为G的最大匹配当且仅当不存在M的增广路径。

　　算法轮廓：

　　（1）置M为空

　　（2）找出一条增广路径P，通过异或操作获得更大的匹配M’代替M

　　（3）重复（2）操作直到找不出增广路径为止

== 时间空间复杂度 ==

　　时间复杂度邻接矩阵：最坏为O(n^3)邻接表：O(mn)
　　空间复杂度邻接矩阵：O(n^2)邻接表：O(m+n)

== 相关代码 ==
* [http://www.frc.ri.cmu.edu/~lantao/code.html C++（STL）implementation (bipartite graph version)]
* [http://noldorin.com/blog/2009/09/hungarian-algorithm-in-csharp/ C# implementation]
* [http://konstantinosnedas.com/dev/soft/munkres.htm Java implementation]
* [http://www.mathworks.com/matlabcentral/fileexchange/11609 Matlab implementation]
* [http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6543 Implementation in Matlab and C]

{{图算法}}

[[Category:软件]]
[[Category:算法]]