查看“︁匈牙利算法”︁的源代码

{{noteTA
|G1=IT
}}
[[File:Problème d'affectation.png|thumb|以最低的总成本将任务分配给工人的图解。]]
'''匈牙利算法'''是一种在[[时间复杂度|多项式时间]]内求解[[任务分配问题]]的[[组合优化]][[算法]]，并推动了后来的{{le|原始对偶方法|primal-dual methods}}。美国数学家[[哈罗德·W·库恩]]于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前[[匈牙利]]数学家{{le|科尼格·德內什|Dénes Kőnig}}和[[艾蓋瓦里·耶內]]的工作之上创建起来的。<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> 此后该算法被称为'''库恩-芒克勒斯算法'''或'''芒克勒斯分配算法'''。原始算法的[[計算複雜性理論|时间复杂度]]为<math>O(n^4)</math>，但{{le|杰克·爱德蒙斯|Jack Edmonds}}与[[理查德·卡普]]发现可以修改算法达到<math>O(n^3)</math>运行时间。[[小萊斯特·倫道夫·福特]]和[[德爾伯特·雷·富爾克森]]将该方法推广到一般运输问题，稱作[[福特-富爾克森算法]]。2006年发现[[卡爾·雅可比]]在19世纪就解决了指派问题，该解法在他死后在1890年以拉丁文发表。<ref>{{Cite web |url=http://www.lix.polytechnique.fr/~ollivier/JACOBI/jacobiEngl.htm |title=JACOBI'S BOUND |access-date=2015-08-14 |archive-date=2020-01-29 |archive-url=https://web.archive.org/web/20200129152235/http://www.lix.polytechnique.fr/~ollivier/JACOBI/jacobiEngl.htm }}</ref>

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

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

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

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

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

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

在一般的步骤中，令 <math>R_S \subseteq S</math> 和 <math>R_T \subseteq T</math> 为 <math> M </math> 未覆盖的节点
（则 <math>R_S</math> 包含 <math> S </math> 中入度为零的节点，而 <math>R_T</math> 中包含 <math> T </math> 中出度为零的节点）。
令 <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> 中的节点将<math> y </math>增加<math>\Delta</math> 并在 <math>Z \cap S</math> 中节点将 <math> y </math>减小 <math>\Delta</math>，
得到的<math> y </math>仍然是势。图 <math>G_y</math> 改变了，但它仍包含<math> M </math>。我们把新的边从<math> S </math>指向<math> T </math>。
由 <math>\Delta</math> 的定义，<math>R_S</math> 可达的节点集 <math> Z </math> 增大（注意到紧边的数量不一定增加）。

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

===证明：改变势函数''y''不改变''M''===
证明改变<math>y</math>后<math>M</math>中每条边不发生改变，这等价于证明对于<math>M</math>中任意边，它的两个顶点要么都在<math>Z</math>中，要么都不在<math>Z</math>中。为此，定义<math>vu</math>为<math>M</math>中一条从<math>T</math>到<math>S</math>的边，则若<math>v\in Z</math>，那么有<math>u\in Z</math>。（反证）假设<math>u \in Z</math>但<math>v \notin Z</math>；由于<math>u</math>是一个匹配边的末端点，<math>u\notin R_S</math>，因此存在从<math>R_S</math>到<math>u</math>的有向路径。这条路径必不能经过<math>v</math>（根据假设），因此这条路径上紧邻<math>u</math>的点是其他点<math>v' \in T</math>。<math>v'u</math>是一条从<math>T</math>到<math>S</math>的紧边因此也是<math>M</math>中的一个元素。但因此<math>M</math>包含两条有共点的边，与<math>M</math>是匹配的定义矛盾。因此<math>M</math>中每条边的两个顶点要么都在<math>Z</math>中，要么都不在<math>Z</math>中。

===证明：''y''仍然是势函数===
证明<math>y</math>在更改之后是势函数，等价于证明不存在总势超过成本的边。这已经在之前的论述中已经为<math>M</math>中的边建立这个概念，因此我们考虑任意从<math>S</math>到<math>T</math>的边<math>uv</math>。如果<math>y(u)</math>升高了<math>\Delta</math>，那么：(1)<math>v \in Z \cap T</math>，在这种情况下，<math>y(v)</math>减小了<math>\Delta</math>，使总体的势未发生改变；(2)<math>v \in T \setminus Z</math>，这种情况下<math>\Delta</math>的定义保证了<math>y(u)+y(v)+\Delta \leq c(u,v)</math>。因此<math>y</math>仍然是势函数。

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

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

:<math>\begin{bmatrix}
a_1 & a_2 & a_3 & a_4\\
b_1 & b_2 & b_3 & b_4\\
c_1 & c_2 & c_3 & c_4\\
d_1 & d_2 & d_3 & d_4\end{bmatrix}</math>

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

'''第 1 步'''

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

{|class="wikitable" style="text-align:center"
|-
| <math> 0  </math> ||<math> a_2' </math>|| <math> a_3' </math> || <math> a_4'</math>
|-
|<math>b_1'</math>||<math>b_2'</math>||<math>b_3'</math>|| <math>0</math>
|-
|<math>c_1'</math>|| <math>0 </math>||<math>c_3'</math>||<math>c_4'</math>
|-
|<math>d_1'</math>||<math>d_2'</math>|| <math>0</math> ||<math>d_4'</math>
|}

每一行的 0 的个数可以超过 1。

若有出现行中 0 的个数超过 1，在最坏的情况下，会需要在 <math>n!</math> 的组合中找到一个成本最小的配对。

'''第 2 步'''

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

{|class="wikitable" style="text-align:center"
|-
|<math>0</math>  ||<math>a_2'</math>||<math>a_3'</math>||<math>a_4'</math>
|-
|<math>b_1'</math>||<math>b_2'</math>||<math>b_3'</math>||<math>0</math>
|-
|<math>0</math> ||<math>c_2'</math>||<math>c_3'</math>||<math>c_4'</math>
|-
|<math>d_1'</math>||<math>0</math> ||<math>d_3'</math>||<math>d_4'</math>
|}

在上述情形下，不能做出指派。注意到任务 1 由工人 <math>a</math> 和 <math>c</math> 做都很高效 (<math>a_1'</math> 和 <math>c_1'</math> 为 0 )。但两个工人无法分配到同一个任务。

还注意到，没有任何一个工人能有效地做任务 3 (<math>a_3'</math>、<math>b_3'</math>、<math>c_3'</math>、<math>d_3'</math> 皆不为 0)。
为了克服这个问题，我们对所有列重复上述流程（即每一列所有元素都减去该列最小元素）并检查是否可以完成分配。

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

'''第 3 步'''

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

首先，尽可能多地分配任务，用 0' 表示的零为已指派的任务，

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

(在此阶断任何合法的分配都可以接受，因此若一开始分配的是第 3 行的 0，就会使第 1 行的 0 被划掉。)

{|class="wikitable" style="text-align:center"
|-
| <math>0'</math>||<math>a_2'</math>||<math>a_3'</math>||<math>a_4'</math>
|-
|<math>b_1'</math>||<math>b_2'</math>||<math>b_3'</math>|| <math>0'</math>
|-
| <math>0</math> ||<math>c_2'</math>||<math>c_3'</math>||<math>c_4'</math>
|-
|<math>d_1'</math>|| <math>0'</math>|| <math>0</math> ||<math>d_4'</math>
|}

现在到了画图的部分。
* 标记所有未分配的行（第 3 行）。
* 标记所有新标记的行中 0所在（且未标记）的對應列（第 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;  || || || ||
|-
| <math>0'</math>||<math>a_2'</math>||<math>a_3'</math>||<math>a_4'</math>
|style="background: white"|&times;
|-
|<math>b_1'</math>||<math>b_2'</math>||<math>b_3'</math>||<math>0'</math>
|style="background: white"|
|-
| <math>0</math> ||<math>c_2'</math>||<math>c_3'</math>||<math>c_4'</math>
|style="background: white"|&times;
|-
|<math>d_1'</math>||<math>0'</math> ||<math>0</math>||<math>d_4'</math>
|style="background: white"|
|}

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

{|class="wikitable" style="text-align:center"
|- style="background: white"
|&times;  || || || ||
|-
|style="background:lightgrey"| <math>0'</math>||<math>a_2'</math>||<math>a_3'</math>||<math>a_4'</math>
|style="background: white"|&times;
|- style="background:lightgrey"
|<math>b_1'</math>||<math>b_2'</math>||<math>b_3'</math>||<math>0'</math>
|-
|style="background:lightgrey"| <math>0</math> ||<math>c_2'</math>||<math>c_3'</math>||<math>c_4'</math>
|style="background: white"|&times;
|- style="background:lightgrey"
|<math>d_1'</math>||<math>0'</math> ||<math>0</math>||<math>d_4'</math>
|}

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

'''第 4 步'''

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

:<math>\begin{bmatrix}
a_2 & a_3 & a_4\\
c_2 & c_3 & c_4\end{bmatrix}</math>

返回到步骤 1，然后重复这个过程，直到矩阵是空的；当矩阵为空时，意即画出的覆盖所有 0 的（直、行）线的个数等于原本矩阵的行数(或列数) <math>n</math>，在上述的例子中 <math>n = 4</math>，此时代表有一个分配的最佳解存在于这些 0 的组合之中，我们可以在步骤 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] {{Wayback|url=http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf |date=20120105112913 }}
* Mordecai J. Golin, [https://web.archive.org/web/20160303183021/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] {{Wayback|url=http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html |date=20070327101101 }}'', Course notes, [[Murray State University]].
* [[Mike Dawes]], ''[https://web.archive.org/web/20060812030313/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] {{Wayback|url=http://www.cs.elte.hu/egres/tr/egres-04-14.pdf |date=20170809005258 }}, [[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] {{Wayback|url=https://www.youtube.com/watch?v=BUGIhEecipE |date=20201227091033 }}, 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)] {{Wayback|url=http://www.roboticsproceedings.org/rss06/p16.html |date=20200715171637 }}, Liu, Shell.
* [http://www.hungarianalgorithm.com/solve.php Solve any Assignment Problem online] {{Wayback|url=http://www.hungarianalgorithm.com/solve.php |date=20210129215740 }}, 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] {{Wayback|url=https://github.com/maandree/hungarian-algorithm-n3/blob/master/hungarian.c |date=20210308195959 }}
* [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] {{Wayback|url=https://github.com/KevinStern/software-and-algorithms/blob/master/src/main/java/blogspot/software_and_algorithms/stern_library/optimization/HungarianAlgorithm.java |date=20220123132833 }}
* [http://software.clapper.org/munkres/ Python implementation] {{Wayback|url=http://software.clapper.org/munkres/ |date=20201124071413 }} (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] {{Wayback|url=https://github.com/evansenter/gene/blob/f515fd73cb9d6a22b4d4b146d70b6c2ec6a5125b/objects/extensions/hungarian.rb |date=20100330120053 }}
* [http://noldorin.com/blog/2009/09/hungarian-algorithm-in-csharp/ C# implementation] {{Wayback|url=http://noldorin.com/blog/2009/09/hungarian-algorithm-in-csharp/ |date=20131025062942 }}
* [http://www.fantascienza.net/leonardo/so/hungarian.d D implementation with unit tests (port of the Java <math>O(n^3)</math> version)] {{Wayback|url=http://www.fantascienza.net/leonardo/so/hungarian.d |date=20191230174110 }}
* [http://www.ifors.ms.unimelb.edu.au/tutorial/hungarian/welcome_frame.html Online interactive implementation] {{Wayback|url=http://www.ifors.ms.unimelb.edu.au/tutorial/hungarian/welcome_frame.html |date=20190323135256 }} Please note that this implements a variant of the algorithm as described above.
* [https://web.archive.org/web/20151228053040/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.] {{Wayback|url=http://www.netlib.org/utk/lsi/pcwLSI/text/node220.html |date=20190724152200 }}
* [http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6543 Implementation in Matlab and C] {{Wayback|url=http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6543 |date=20080503063209 }}
* [https://metacpan.org/module/Algorithm::Munkres Perl implementation]
* [https://web.archive.org/web/20070325192520/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)] {{Wayback|url=http://students.cse.tamu.edu/lantao/codes/codes.php |date=20200216131227 }}
* [https://github.com/saebyn/munkres-cpp C++ implementation] {{Wayback|url=https://github.com/saebyn/munkres-cpp |date=20201017213751 }}
* [http://dlib.net/optimization.html#max_cost_assignment C++ implementation of the <math>O(n^3)</math> algorithm] {{Wayback|url=http://dlib.net/optimization.html#max_cost_assignment |date=20201029213238 }} (BSD style open source licensed)
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm Another C++ implementation with unit tests] {{Wayback|url=http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm |date=20160407171336 }}
* [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)]{{dead link|date=2017年11月 |bot=InternetArchiveBot |fix-attempted=yes }}
* [https://web.archive.org/web/20120814231237/http://www.mathworks.com/matlabcentral/fileexchange/11609 MATLAB implementation]
* [https://launchpad.net/lib-bipartite-match C implementation] {{Wayback|url=https://launchpad.net/lib-bipartite-match |date=20180618102519 }}
* [http://twofourone.blogspot.com/2009/01/hungarian-algorithm-in-javascript.html Javascript implementation] {{Wayback|url=http://twofourone.blogspot.com/2009/01/hungarian-algorithm-in-javascript.html |date=20171016140821 }} 
* [http://cran.r-project.org/web/packages/clue/clue.pdf  The clue R package proposes an implementation, solve_LSAP] {{Wayback|url=http://cran.r-project.org/web/packages/clue/clue.pdf |date=20201027134027 }}

{{图算法}}

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