Difference between revisions 34005898 and 36826133 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:算法一种在[[时间复杂度|多项式时间]]内求解[[任务分配问题]]的[[组合优化]][[算法]]，并推动了后来的[[原始对偶方法]]。美国数学家{{le|哈罗德·库恩|Harold Kuhn}}于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前[[匈牙利]]数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。<ref name="kuhn1955">Harold W. Kuhn, "The Hungarian Method for the assignment problem", ''[[Naval Research Logistics Quarterly]]'', '''2''': 83–97, 1955.  Kuhn's original publication.</ref><ref name="kuhn1956">Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", ''Naval Research Logistics Quarterly'', '''3''': 253–258, 1956.</ref>

[[詹姆士·雷蒙·芒克勒斯|詹姆士·芒克勒斯]]在1957年回顾了该算法，并发现[[时间复杂度|（强）多项式时间]]的。<ref name="munkres">J. Munkres, "Algorithms for the Assignment and Transportation Problems", ''[[Journal of the Society for Industrial and Applied Mathematics]]'', '''5'''(1):32–38, 1957 March.</ref> 此后该算法被称为'''Kuhn–Munkres算法'''或'''Munkres分配算法'''。原始算法的[[計算複雜性理論|时间复杂度]]为<math>O(n^4)</math>，但[[Jack Edmonds|Edmonds]]与[[理查德·卡普|卡普]]发现可以修改算法达到<math>O(n^3)</math>运行时间，富泽也独立发现了这一点。[[L. R. Ford, Jr.|Ford]]和[[D. R. Fulkerson|Fulkerson]]将该方法推广到了一般运输问题。2006年发现[[卡爾·雅可比]]在19世纪就解决了指派问题，该解法在他死后1890年以拉丁文发表。<ref>http://www.lix.polytechnique.fr/~ollivier/JACOBI/jacobiEngl.htm</ref>

==Layman对指派问题的解释==
你有三个工人：吉姆，史提夫和艾伦。
你需要其中一个清洁浴室，另一个打扫地板，第三个洗窗，但他们每个人对各项任务要求不同数目数量的钱。
以最低成本的分配工作的方式是什么？
可以用工人做工的成本[[矩阵]]来表示该问题。例如：
{| class="wikitable" border="1"
|-
!
! 清洁浴室
! 打扫地板
! 洗窗
|-
! 吉姆
| $2
| $3
| $3
|-
! 史提夫
| $3
| $2
| $3
|-
! 艾伦
| $3
| $3
| $2
|}

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

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

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

如果函数 <math>y: (S \cup T) \mapsto \mathbb{R}</math> 满足对于每个 <math>i \in S, j \in T</math> 都有 <math>y(i)+y(j) \leq c(i, j)</math>，则把该函数叫做'''势'''。势 ''y'' 的值为 <math>\sum_{v\in S\cup T} y(v)</math>。可以看出，每个完美匹配的成本至少是每个势的值。匈牙利算法找出了完美匹配及与之成本/值相等的势，这证明了两者的最优性。实际上它找到了'''紧边集'''的完美匹配：紧边 ''ij'' 是指对于势 ''y'' 满足 <math>y(i)+y(j) = c(i, j)</math>。我们将紧边[[图论术语#子图|子图]]表示为 <math>G_y</math>。<math>G_y</math> 中的完美匹配的成本（如果存在）就等于 ''y'' 的值。

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

在一般的步骤中，令 <math>R_S \subseteq S</math> 和 <math>R_T \subseteq T</math> 为 ''M'' 未覆盖的节点（则 <math>R_S</math> 包含 ''S'' 中入度为零的节点，而 <math>R_T</math> 中包含 ''T'' 中出度为零的节点）。令 <math>Z</math> 为从 <math>R_S</math> 只沿紧边的有向路径可到达<math>\overrightarrow{G_y}</math> 的节点。可由[[广度优先搜索]]求得。

若 <math>R_T \cap Z</math> 非空，则将 <math>\overrightarrow{G_y}</math> 中从 <math>R_S</math> 到 <math>R_T</math> 的有向路径反向。则相应匹配数增加1。

若 <math>R_T \cap Z</math> 为空，则令 <math>\Delta := \min \{c(i,j)-y(i)-y(j): i \in Z \cap S, j \in T \setminus Z\}</math>。<math>\Delta</math> 为正，因为 <math>Z \cap S</math> 与 <math>T \setminus Z</math> 之间没有紧边。在 <math>Z \cap T</math> 中的节点将''y''增加<math>\Delta</math> 并在 <math>Z \cap S</math> 中节点将 ''y''减小 <math>\Delta</math>，得到的 ''y'' 仍然是势。图 <math>G_y</math> 改变了，但它仍包含''M''。我们把新的边从''S''指向''T''。由 <math>\Delta</math> 的定义，<math>R_S</math> 可达的节点集 ''Z'' 增大（注意到紧边的数量不一定增加）。

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

==矩阵解释==
给定 <math>n</math> 个工人和任务，以及一个包含分配给每个工人一个任务的成本的 ''n''×''n''  矩阵，寻找成本最小化分配。

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

:<math>\begin{bmatrix}
a1 & a2 & a3 & a4\\
b1 & b2 & b3 & b4\\
c1 & c2 & c3 & c4\\
d1 & d2 & d3 & d4\end{bmatrix}</math>

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

'''第1步'''

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

{|class="wikitable" style="text-align:center"
|-
| 0 ||a2'||a3' ||a4'
|-
|b1'||b2'||b3'|| 0
|-
|c1'|| 0 ||c3'||c4'
|-
|d1'||d2'|| 0 ||d4'
|}

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

'''第2步'''

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

{|class="wikitable" style="text-align:center"
|-
|0  ||a2'||a3'||a4'
|-
|b1'||b2'||b3'||0
|-
|0  ||c2'||c3'||c4'
|-
|d1'||0  ||d3'||d4'
|}

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

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

'''第3步'''

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

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

* 第1行有一个零，所以分配了。第3行的0由于处于同一列而被划掉。
* 第1行有一个零，所以分配了。
* 第3行只有一个已经划掉的零，所以不能分配。
* 第4有两个未划掉的零。可以分配任何一个（都是最优） ，并将另一个零划去。

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

{|class="wikitable" style="text-align:center"
|-
| 0'||a2'||a3'||a4'
|-
|b1'||b2'||b3'|| 0'
|-
| 0 ||c2'||c3'||c4'
|-
|d1'|| 0'|| 0 ||d4'
|}

现在到了画图的部分。
* 将所有没分配的行做标记（第3行）。
* 在新标记的行中所有（未标记）的列做标记（第1列）。
* 标记所有在新标记的列中有分配的行（第1行）。
* 对所有未分配的行重复上述过程。

<!-- this might need to make the borders go away, if the current appearance is thought to be ugly -->
{|class="wikitable" style="text-align:center"
|- style="background: white"
|&times;  || || || ||
|-
| 0'||a2'||a3'||a4'
|style="background: white"|&times;
|-
|b1'||b2'||b3'||0'
|style="background: white"|
|-
| 0 ||c2'||c3'||c4'
|style="background: white"|&times;
|-
|d1'||0' ||0||d4'
|style="background: white"|
|}

现在在所有标记了的列和'''未标记'''的行中画线。

{|class="wikitable" style="text-align:center"
|- style="background: white"
|&times;  || || || ||
|-
|style="background:lightgrey"| 0'||a2'||a3'||a4'
|style="background: white"|&times;
|- style="background:lightgrey"
|b1'||b2'||b3'||0'
|-
|style="background:lightgrey"| 0 ||c2'||c3'||c4'
|style="background: white"|&times;
|- style="background:lightgrey"
|d1'||0' ||0||d4'
|}

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

'''第4步'''

现在删除标记的行和列。这将留下一个矩阵如下：

:<math>\begin{bmatrix}
a2 & a3 & a4\\
c2 & c3 & c4\end{bmatrix}</math>

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

==参考书目==
* R.E. Burkard, M. Dell'Amico, S. Martello: ''Assignment Problems'' (Revised reprint). SIAM, Philadelphia (PA.) 2012. ISBN 978-1-61197-222-1
* M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995.
* [[Ravindra K. Ahuja|R. Ahuja]], [[Thomas L. Magnanti|T. Magnanti]], [[James B. Orlin|J. Orlin]], "Network Flows", Prentice Hall, 1993.
* S. Martello, "Jeno Egerváry: from the origins of the Hungarian algorithm to satellite communication". Central European Journal of Operations Research 18, 47–58, 2010

==参考文献==
{{Reflist}}

==外部链接==
* Bruff, Derek, "The Assignment Problem and the Hungarian Method", [http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf]
* Mordecai J. Golin, [http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf Bipartite Matching and the Hungarian Method], Course Notes, [[香港科技大學|Hong Kong University of Science and Technology]].
* [[R. A. Pilgrim]], ''[http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html Munkres' Assignment Algorithm. Modified for Rectangular Matrices]'', Course notes, [[Murray State University]].
* [[Mike Dawes]], ''[http://www.math.uwo.ca/~mdawes/courses/344/kuhn-munkres.pdf The Optimal Assignment Problem]'', Course notes, [[西安大略大学|University of Western Ontario]].
* [http://www.cs.elte.hu/egres/tr/egres-04-14.pdf On Kuhn's Hungarian Method – A tribute from Hungary], [[András Frank]], Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Hungary.
* Lecture: [https://www.youtube.com/watch?v=BUGIhEecipE Fundamentals of Operations Research - Assignment Problem - Hungarian Algorithm], Prof. G. Srinivasan, Department of Management Studies, IIT Madras.
* Extension: [http://www.roboticsproceedings.org/rss06/p16.html Assignment sensitivity analysis (with O(n^4) time complexity)], Liu, Shell.
* [http://www.hungarianalgorithm.com/solve.php Solve any Assignment Problem online], provides a step by step explanation of the Hungarian Algorithm.

===实现===
（请注意，并非所有这些都满足 <math>O(n^3)</math> 时间约束。）
* [https://github.com/maandree/hungarian-algorithm-n3/blob/master/hungarian.c C implementation with <math>O(n^3)</math> time complexity]
* [https://github.com/KevinStern/software-and-algorithms/blob/master/src/main/java/blogspot/software_and_algorithms/stern_library/optimization/HungarianAlgorithm.java Java implementation of <math>O(n^3)</math> time variant]
* [http://software.clapper.org/munkres/ Python implementation] (see also [https://github.com/xtof-durr/makeSimple/blob/master/Munkres/kuhnMunkres.py here])
* [https://github.com/evansenter/gene/blob/f515fd73cb9d6a22b4d4b146d70b6c2ec6a5125b/objects/extensions/hungarian.rb Ruby implementation with unit tests]
* [http://noldorin.com/blog/2009/09/hungarian-algorithm-in-csharp/ C# implementation]
* [http://www.fantascienza.net/leonardo/so/hungarian.d D implementation with unit tests (port of the Java <math>O(n^3)</math> version)]
* [http://www.ifors.ms.unimelb.edu.au/tutorial/hungarian/welcome_frame.html Online interactive implementation] Please note that this implements a variant of the algorithm as described above.
* [http://web.axelero.hu/szilardandras/gaps.html Graphical implementation with options] ([[Java applet]])
* [http://www.netlib.org/utk/lsi/pcwLSI/text/node220.html Serial and parallel implementations.]
* [http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6543 Implementation in Matlab and C]
* [https://metacpan.org/module/Algorithm::Munkres Perl implementation]
* [http://www.koders.com/lisp/fid7C3730AF4E356C65F93F20A6410814CBF5F40854.aspx?s=iso+3166 Lisp implementation]
* [http://students.cse.tamu.edu/lantao/codes/codes.php C++ (STL) implementation (multi-functional bipartite graph version)]
* [https://github.com/saebyn/munkres-cpp C++ implementation]
* [http://dlib.net/optimization.html#max_cost_assignment C++ implementation of the <math>O(n^3)</math> algorithm] (BSD style open source licensed)
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm Another C++ implementation with unit tests]
* [http://timefinder.svn.sourceforge.net/viewvc/timefinder/trunk/timefinder-algo/src/main/java/de/timefinder/algo/roomassignment/ Another Java implementation with JUnit tests (Apache 2.0)]
* [http://www.mathworks.com/matlabcentral/fileexchange/11609 MATLAB implementation]
* [https://launchpad.net/lib-bipartite-match C implementation]
* [http://twofourone.blogspot.com/2009/01/hungarian-algorithm-in-javascript.html Javascript implementation] 
* [http://cran.r-project.org/web/packages/clue/clue.pdf  The clue R package proposes an implementation, solve_LSAP]

{{图算法}}

{{DEFAULTSORT:匈牙利算法}}
[[Category:匹配]]
[[Category:组合优化]]