本页使用了标题或全文手工转换

匈牙利算法

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

Layman对指派问题的解释[编辑]

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

清洁浴室 打扫地板 洗窗
吉姆 $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) 的非负成本。我们要找到最低成本的完美匹配

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

用二分图描述此算法[编辑]

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

在一般的步骤中,令 R_S \subseteq SR_T \subseteq TM 未覆盖的节点(则 R_S 包含 S 中入度为零的节点,而 R_T 中包含 T 中出度为零的节点)。令 Z 为从 R_S 只沿紧边的有向路径可到达\overrightarrow{G_y} 的节点。可由广度优先搜索求得。

R_T \cap Z 非空,则将 \overrightarrow{G_y} 中从 R_SR_T 的有向路径反向。则相应匹配数增加1。

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

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

矩阵解释[编辑]

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

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

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

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

第1步

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

0 a2' a3' a4'
b1' b2' b3' 0
c1' 0 c3' c4'
d1' d2' 0 d4'

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

第2步

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

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被划掉。

0' a2' a3' a4'
b1' b2' b3' 0'
0 c2' c3' c4'
d1' 0' 0 d4'

现在到了画图的部分。

  • 将所有没分配的行做标记(第3行)。
  • 在新标记的行中所有(未标记)的列做标记(第1列)。
  • 标记所有在新标记的列中有分配的行(第1行)。
  • 对所有未分配的行重复上述过程。
×
0' a2' a3' a4' ×
b1' b2' b3' 0'
0 c2' c3' c4' ×
d1' 0' 0 d4'

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

×
0' a2' a3' a4' ×
b1' b2' b3' 0'
0 c2' c3' c4' ×
d1' 0' 0 d4'

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

第4步

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

\begin{bmatrix}
a2 & a3 & a4\\
c2 & c3 & c4\end{bmatrix}

返回到步骤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.
  • R. Ahuja, T. Magnanti, 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

参考文献[编辑]

  1. ^ Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955. Kuhn's original publication.
  2. ^ Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly, 3: 253–258, 1956.
  3. ^ J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
  4. ^ JACOBI'S BOUND

外部链接[编辑]

实现[编辑]

(请注意,并非所有这些都满足 O(n^3) 时间约束。)