匈牙利算法

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

以最低的总成本将任务分配给工人的图解。

詹姆士·芒克勒斯在1957年回顾了该算法,并发现它的时间复杂度为(强)多项式时间[3] 此后该算法被称为库恩-芒克勒斯算法芒克勒斯分配算法。原始算法的时间复杂度,但杰克·爱德蒙斯英语Jack Edmonds理查德·卡普发现可以修改算法达到运行时间。小莱斯特·伦道夫·福特德尔伯特·雷·富尔克森将该方法推广到一般运输问题,称作福特-富尔克森算法。2006年发现卡尔·雅可比在19世纪就解决了指派问题,该解法在他死后在1890年以拉丁文发表。[4]

问题

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

清洁浴室 打扫地板 洗窗
吉姆 $2 $3 $3
史提夫 $3 $2 $3
艾伦 $3 $3 $2

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

设定

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

如果用二分图来阐述该问题可以更容易描述这个算法。对于一个有  个工人节点( )与  个工作节点( )的完全二分图  ,每条边都有   的非负成本。我们要找到最低成本的完美匹配

如果函数   满足对于每个   都有  ,则把该函数叫做。势   的值为  。可以看出,每个完美匹配的成本最低是每个势的值。匈牙利算法找出了完美匹配及与之成本/值相等的势,这证明了两者的最优性。实际上它找到了紧边集的完美匹配:紧边   是指对于势   满足  。我们将紧边子图表示为    中的完美匹配的成本(如果存在)就等于  的值。

用二分图描述此算法

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

在一般的步骤中,令     未覆盖的节点 (则   包含   中入度为零的节点,而   中包含   中出度为零的节点)。 令   为从   只沿紧边的有向路径可到达   的节点。可由广度优先搜索求得。

  非空,则将   中从    的有向路径反向。则相应匹配数增加1。

  为空,则令    为正,因为    之间没有紧边。 在   中的节点将 增加  并在   中节点将  减小  , 得到的 仍然是势。图   改变了,但它仍包含 。我们把新的边从 指向 。 由   的定义,  可达的节点集   增大(注意到紧边的数量不一定增加)。

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

证明:改变势函数y不改变M

证明改变  中每条边不发生改变,这等价于证明对于 中任意边,它的两个顶点要么都在 中,要么都不在 中。为此,定义  中一条从  的边,则若 ,那么有 。(反证)假设  ;由于 是一个匹配边的末端点, ,因此存在从  的有向路径。这条路径必不能经过 (根据假设),因此这条路径上紧邻 的点是其他点  是一条从  的紧边因此也是 中的一个元素。但因此 包含两条有共点的边,与 是匹配的定义矛盾。因此 中每条边的两个顶点要么都在 中,要么都不在 中。

证明:y仍然是势函数

证明 在更改之后是势函数,等价于证明不存在总势超过成本的边。这已经在之前的论述中已经为 中的边建立这个概念,因此我们考虑任意从  的边 。如果 升高了 ,那么:(1) ,在这种情况下, 减小了 ,使总体的势未发生改变;(2) ,这种情况下 的定义保证了 。因此 仍然是势函数。

矩阵解释

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

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

 

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

第 1 步

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

       
       
       
       

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

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

第 2 步

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

       
       
       
       

在上述情形下,不能做出指派。注意到任务 1 由工人    做都很高效 (   为 0 )。但两个工人无法分配到同一个任务。

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

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

第 3 步

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

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

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

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

       
       
       
       

现在到了画图的部分。

  • 标记所有未分配的行(第 3 行)。
  • 标记所有新标记的行中 0所在(且未标记)的对应列(第 1 列)。
  • 标记所有在新标记的列中有分配的行(第 1 行)。
  • 对所有未分配的行重复上述过程。
×
        ×
       
        ×
       

现在划掉所有已标记的列和未标记的行(第 1 列和第 2, 4 行)。

×
        ×
       
        ×
       

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

第 4 步

现在删除已画线的行和列。这将留下一个矩阵如下:

 

返回到步骤 1,然后重复这个过程,直到矩阵是空的;当矩阵为空时,意即画出的覆盖所有 0 的(直、行)线的个数等于原本矩阵的行数(或列数)  ,在上述的例子中  ,此时代表有一个分配的最佳解存在于这些 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.
  • 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. [2015-08-14]. (原始内容存档于2020-01-29). 

外部链接

实现

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