詹姆士·芒克勒斯在1957年回顾了该算法,并发现它的时间复杂度为(强)多项式时间。[3] 此后该算法被称为Kuhn–Munkres算法或Munkres分配算法。原始算法的时间复杂度为,但杰克·爱德蒙斯(英语:Jack Edmonds)与卡普发现可以修改算法达到运行时间,富泽也独立发现了这一点。L·R·福特(英语:L. R. Ford, Jr.)和D·R·福尔克森(英语:D. R. Fulkerson)将该方法推广到了一般运输问题。2006年发现卡爾·雅可比在19世纪就解决了指派问题,该解法在他死后在1890年以拉丁文发表。[4]
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
参考文献
^Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955. Kuhn's original publication.
^Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly, 3: 253–258, 1956.
^J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
On Kuhn's Hungarian Method – A tribute from Hungary (页面存档备份,存于互联网档案馆), András Frank, Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Hungary.
Lecture: Fundamentals of Operations Research - Assignment Problem - Hungarian Algorithm (页面存档备份,存于互联网档案馆), Prof. G. Srinivasan, Department of Management Studies, IIT Madras.
The clue R package proposes an implementation, solve_LSAP (页面存档备份,存于互联网档案馆)
一月 28, 2023
匈牙利算法, 是一种在多项式时间内求解任务分配问题的组合优化算法, 并推动了后来的原始对偶方法, 英语, primal, dual, methods, 美国数学家哈罗德, 库恩, 英语, harold, kuhn, 于1955年提出该算法, 此算法之所以被称作, 是因为算法很大一部分是基于以前匈牙利数学家科尼格, 德內什, 英语, dénes, kőnig, 和艾蓋瓦里, 耶內, 英语, jenő, egerváry, 的工作之上创建起来的, 詹姆士, 芒克勒斯在1957年回顾了该算法, 并发现它的时间复杂度为, . 匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法 并推动了后来的原始对偶方法 英语 primal dual methods 美国数学家哈罗德 库恩 英语 Harold Kuhn 于1955年提出该算法 此算法之所以被称作匈牙利算法 是因为算法很大一部分是基于以前匈牙利数学家科尼格 德內什 英语 Denes Konig 和艾蓋瓦里 耶內 英语 Jeno Egervary 的工作之上创建起来的 1 2 詹姆士 芒克勒斯在1957年回顾了该算法 并发现它的时间复杂度为 强 多项式时间 3 此后该算法被称为Kuhn Munkres算法或Munkres分配算法 原始算法的时间复杂度为O n 4 displaystyle O n 4 但杰克 爱德蒙斯 英语 Jack Edmonds 与卡普发现可以修改算法达到O n 3 displaystyle O n 3 运行时间 富泽也独立发现了这一点 L R 福特 英语 L R Ford Jr 和D R 福尔克森 英语 D R Fulkerson 将该方法推广到了一般运输问题 2006年发现卡爾 雅可比在19世纪就解决了指派问题 该解法在他死后在1890年以拉丁文发表 4 目录 1 Layman对指派问题的解释 2 设定 3 用二分图描述此算法 3 1 证明 改变势函数y不改变M 3 2 证明 y仍然是势函数 4 矩阵解释 5 参考书目 6 参考文献 7 外部链接 7 1 实现Layman对指派问题的解释 编辑你有三个工人 吉姆 史提夫和艾伦 你需要其中一个清洁浴室 另一个打扫地板 第三个洗窗 但他们每个人对各项任务要求不同数目数量的钱 以最低成本的分配工作的方式是什么 可以用工人做工的成本矩阵来表示该问题 例如 清洁浴室 打扫地板 洗窗吉姆 2 3 3史提夫 3 2 3艾伦 3 3 2当把匈牙利方法应用于上面的表格时 会给出最低成本 为6美元 让吉姆清洁浴室 史提夫打扫地板 艾伦清洗窗户就可以达到这一结果 设定 编辑给定一个 n n displaystyle n times n 的非负矩阵 其中第 i displaystyle i 行第 j displaystyle j 列元素表示把第 i displaystyle i 个工人派到第 j displaystyle j 个工作的成本 我们必须找到成本最低的工人工作分配 如果目标是找到最高成本的分配 该问题可以将每个成本都换为最高一个成本减去该成本以适应题目 如果用二分图来阐述该问题可以更容易描述这个算法 对于一个有 n displaystyle n 个工人节点 S displaystyle S 与 n displaystyle n 个工作节点 T displaystyle T 的完全二分图 G S T E displaystyle G S cup T E 每条边都有 c i j displaystyle c i j 的非负成本 我们要找到最低成本的完美匹配 如果函数 y S T R displaystyle y S cup T mapsto mathbb R 满足对于每个 i S j T displaystyle i in S j in T 都有 y i y j c i j displaystyle y i y j leq c i j 则把该函数叫做势 势 y displaystyle y 的值为 v S T y v displaystyle sum v in S cup T y v 可以看出 每个完美匹配的成本最低是每个势的值 匈牙利算法找出了完美匹配及与之成本 值相等的势 这证明了两者的最优性 实际上它找到了紧边集的完美匹配 紧边 i j displaystyle ij 是指对于势 y displaystyle y 满足 y i y j c i j displaystyle y i y j c i j 我们将紧边子图表示为 G y displaystyle G y G y displaystyle G y 中的完美匹配的成本 如果存在 就等于 y displaystyle y 的值 用二分图描述此算法 编辑在算法中我们維持 G y displaystyle G y 的势y displaystyle y 和方向 表示为 G y displaystyle overrightarrow G y 该方向有从 T displaystyle T 到 S displaystyle S 的边构成匹配 M displaystyle M 的性质 初始时 y displaystyle y 处处为 0 所有边都由 S displaystyle S 指向 T displaystyle T 因此 M displaystyle M 为空 每一步中 我们或者改变 y displaystyle y 使其值增加 或者改变方向以得到更多的边 我们保持 M displaystyle M 的所有边都是紧边不发生改变 当 M displaystyle M 为完美匹配时结束 在一般的步骤中 令 R S S displaystyle R S subseteq S 和 R T T displaystyle R T subseteq T 为 M displaystyle M 未覆盖的节点 则 R S displaystyle R S 包含 S displaystyle S 中入度为零的节点 而 R T displaystyle R T 中包含 T displaystyle T 中出度为零的节点 令 Z displaystyle Z 为从 R S displaystyle R S 只沿紧边的有向路径可到达 G y displaystyle overrightarrow G y 的节点 可由广度优先搜索求得 若 R T Z displaystyle R T cap Z 非空 则将 G y displaystyle overrightarrow G y 中从 R S displaystyle R S 到 R T displaystyle R T 的有向路径反向 则相应匹配数增加1 若 R T Z displaystyle R T cap Z 为空 则令 D min c i j y i y j i Z S j T Z displaystyle Delta min c i j y i y j i in Z cap S j in T setminus Z D displaystyle Delta 为正 因为 Z S displaystyle Z cap S 与 T Z displaystyle T setminus Z 之间没有紧边 在 Z T displaystyle Z cap T 中的节点将y displaystyle y 增加D displaystyle Delta 并在 Z S displaystyle Z cap S 中节点将 y displaystyle y 减小 D displaystyle Delta 得到的y displaystyle y 仍然是势 图 G y displaystyle G y 改变了 但它仍包含M displaystyle M 我们把新的边从S displaystyle S 指向T displaystyle T 由 D displaystyle Delta 的定义 R S displaystyle R S 可达的节点集 Z displaystyle Z 增大 注意到紧边的数量不一定增加 我们重复这些步骤直到M displaystyle M 为完美匹配 该情形下给出的是最小成本 即时间消耗 的匹配 此版本的运行时间为 O n 4 displaystyle O n 4 M displaystyle M 增广 n displaystyle n 次 在 M displaystyle M 不改变的一个阶段中 势最多改变 n displaystyle n 次 因为 Z displaystyle Z 每次都增加 改变势所需的时间在 O n 2 displaystyle O n 2 证明 改变势函数y不改变M 编辑 证明改变y displaystyle y 后M displaystyle M 中每条边不发生改变 这等价于证明对于M displaystyle M 中任意边 它的两个顶点要么都在Z displaystyle Z 中 要么都不在Z displaystyle Z 中 为此 定义v u displaystyle vu 为M displaystyle M 中一条从T displaystyle T 到S displaystyle S 的边 则若v Z displaystyle v in Z 那么有u Z displaystyle u in Z 反证 假设u Z displaystyle u in Z 但v Z displaystyle v notin Z 由于u displaystyle u 是一个匹配边的末端点 u R S displaystyle u notin R S 因此存在从R S displaystyle R S 到u displaystyle u 的有向路径 这条路径必不能经过v displaystyle v 根据假设 因此这条路径上紧邻u displaystyle u 的点是其他点v T displaystyle v in T v u displaystyle v u 是一条从T displaystyle T 到S displaystyle S 的紧边因此也是M displaystyle M 中的一个元素 但因此M displaystyle M 包含两条有共点的边 与M displaystyle M 是匹配的定义矛盾 因此M displaystyle M 中每条边的两个顶点要么都在Z displaystyle Z 中 要么都不在Z displaystyle Z 中 证明 y仍然是势函数 编辑 证明y displaystyle y 在更改之后是势函数 等价于证明不存在总势超过成本的边 这已经在之前的论述中已经为M displaystyle M 中的边建立这个概念 因此我们考虑任意从S displaystyle S 到T displaystyle T 的边u v displaystyle uv 如果y u displaystyle y u 升高了D displaystyle Delta 那么 1 v Z T displaystyle v in Z cap T 在这种情况下 y v displaystyle y v 减小了D displaystyle Delta 使总体的势未发生改变 2 v T Z displaystyle v in T setminus Z 这种情况下D displaystyle Delta 的定义保证了y u y v D c u v displaystyle y u y v Delta leq c u v 因此y displaystyle y 仍然是势函数 矩阵解释 编辑给定 n displaystyle n 个工人和任务 以及一个包含分配给每个工人一个任务的成本的 n n displaystyle n times n 矩阵 寻找成本最小化分配 首先把问题写成下面的矩阵形式 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 displaystyle begin bmatrix a 1 amp a 2 amp a 3 amp a 4 b 1 amp b 2 amp b 3 amp b 4 c 1 amp c 2 amp c 3 amp c 4 d 1 amp d 2 amp d 3 amp d 4 end bmatrix 其中 a b c d displaystyle a b c d 是执行任务 1 2 3 4 的工人 a 1 a 2 a 3 a 4 displaystyle a 1 a 2 a 3 a 4 分别表示当工人 a displaystyle a 做任务 1 2 3 4 时的时间损失 成本 对于其他符号也同样适用 该矩阵是方阵 所以每个工人只能执行一个任务 第 1 步接下来我们对矩阵的行进行操作 将所有 a i displaystyle a i i displaystyle i 从 1 到 4 中最小的元素取走 并将该行每个元素都减去刚刚取走的元素 这会让该行至少出现一个零 当一行有两个相等的最小元素时会得到多个零 对此过程为所有行重复 我们现在得到一个每行至少有一个零的矩阵 现在我们尝试给工人指派任务 以使每个工人只做一项任务 并且每个情况的耗散都为零 说明如下 0 displaystyle 0 a 2 displaystyle a 2 a 3 displaystyle a 3 a 4 displaystyle a 4 b 1 displaystyle b 1 b 2 displaystyle b 2 b 3 displaystyle b 3 0 displaystyle 0 c 1 displaystyle c 1 0 displaystyle 0 c 3 displaystyle c 3 c 4 displaystyle c 4 d 1 displaystyle d 1 d 2 displaystyle d 2 0 displaystyle 0 d 4 displaystyle d 4 用 0 表示的零为已指派的任务 第 2 步有时此阶段的该矩阵不能符合指派的要求 例如下面所示矩阵 0 displaystyle 0 a 2 displaystyle a 2 a 3 displaystyle a 3 a 4 displaystyle a 4 b 1 displaystyle b 1 b 2 displaystyle b 2 b 3 displaystyle b 3 0 displaystyle 0 0 displaystyle 0 c 2 displaystyle c 2 c 3 displaystyle c 3 c 4 displaystyle c 4 d 1 displaystyle d 1 0 displaystyle 0 d 3 displaystyle d 3 d 4 displaystyle d 4 在上述情形下 不能做出指派 注意到任务 1 由工人 a displaystyle a 和 c displaystyle c 做都很高效 只是不能把两个工人分配到同一个任务中去 还注意到 没有任何一个工人能有效地做任务 3 为了克服这个问题 我们对所有列重复上述流程 即每一列所有元素都减去该列最小元素 并检查是否可以完成分配 大多数情况下 这都会给出结果 但如果仍然是不可行 那么我们需要继续下去 第 3 步必须用尽可能少的列或行标记来覆盖矩阵中的所有零 下面的过程是完成这个要求的一种方法 首先 尽可能多地分配任务 第 1 行有一个零 所以分配了 第 3 行的 0 由于处于同一列而被划掉 第 2 行有一个零 所以分配了 第 3 行只有一个已经划掉的零 所以不能分配 第 4 行有两个未划掉的零 可以分配任何一个 都是最优 并将另一个零划去 或者 分配的是第 3 行的 0 就会使第 1 行的 0 被划掉 0 displaystyle 0 a 2 displaystyle a 2 a 3 displaystyle a 3 a 4 displaystyle a 4 b 1 displaystyle b 1 b 2 displaystyle b 2 b 3 displaystyle b 3 0 displaystyle 0 0 displaystyle 0 c 2 displaystyle c 2 c 3 displaystyle c 3 c 4 displaystyle c 4 d 1 displaystyle d 1 0 displaystyle 0 0 displaystyle 0 d 4 displaystyle d 4 现在到了画图的部分 标记所有未分配的行 第 3 行 标记所有新标记的行中 0所在 且未标记 的對應列 第 1 列 标记所有在新标记的列中有分配的行 第 1 行 对所有未分配的行重复上述过程 0 displaystyle 0 a 2 displaystyle a 2 a 3 displaystyle a 3 a 4 displaystyle a 4 b 1 displaystyle b 1 b 2 displaystyle b 2 b 3 displaystyle b 3 0 displaystyle 0 0 displaystyle 0 c 2 displaystyle c 2 c 3 displaystyle c 3 c 4 displaystyle c 4 d 1 displaystyle d 1 0 displaystyle 0 0 displaystyle 0 d 4 displaystyle d 4 现在劃掉所有已标记的列和未标记的行 第 1 列和第 2 4 行 0 displaystyle 0 a 2 displaystyle a 2 a 3 displaystyle a 3 a 4 displaystyle a 4 b 1 displaystyle b 1 b 2 displaystyle b 2 b 3 displaystyle b 3 0 displaystyle 0 0 displaystyle 0 c 2 displaystyle c 2 c 3 displaystyle c 3 c 4 displaystyle c 4 d 1 displaystyle d 1 0 displaystyle 0 0 displaystyle 0 d 4 displaystyle d 4 上述详细的描述只是画出覆盖所有 0 的 直 行 线的一种方法 也可以使用其他方法 第 4 步现在删除已畫線的行和列 这将留下一个矩阵如下 a 2 a 3 a 4 c 2 c 3 c 4 displaystyle begin bmatrix a 2 amp a 3 amp a 4 c 2 amp c 3 amp c 4 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 Egervary from the origins of the Hungarian algorithm to satellite communication Central European Journal of Operations Research 18 47 58 2010参考文献 编辑 Harold W Kuhn The Hungarian Method for the assignment problem Naval Research Logistics Quarterly 2 83 97 1955 Kuhn s original publication Harold W Kuhn Variants of the Hungarian method for assignment problems Naval Research Logistics Quarterly 3 253 258 1956 J Munkres Algorithms for the Assignment and Transportation Problems Journal of the Society for Industrial and Applied Mathematics 5 1 32 38 1957 March JACOBI S BOUND 2015 08 14 原始内容存档于2020 01 29 外部链接 编辑Bruff Derek The Assignment Problem and the Hungarian Method 1 页面存档备份 存于互联网档案馆 Mordecai J Golin Bipartite Matching and the Hungarian Method Course Notes Hong Kong University of Science and Technology R A Pilgrim Munkres Assignment Algorithm Modified for Rectangular Matrices 页面存档备份 存于互联网档案馆 Course notes Murray State University Mike Dawes The Optimal Assignment Problem Course notes University of Western Ontario On Kuhn s Hungarian Method A tribute from Hungary 页面存档备份 存于互联网档案馆 Andras Frank Egervary Research Group Pazmany P setany 1 C H1117 Budapest Hungary Lecture Fundamentals of Operations Research Assignment Problem Hungarian Algorithm 页面存档备份 存于互联网档案馆 Prof G Srinivasan Department of Management Studies IIT Madras Extension Assignment sensitivity analysis with O n 4 time complexity 页面存档备份 存于互联网档案馆 Liu Shell Solve any Assignment Problem online 页面存档备份 存于互联网档案馆 provides a step by step explanation of the Hungarian Algorithm 实现 编辑 请注意 并非所有这些都满足 O n 3 displaystyle O n 3 时间约束 C implementation with O n 3 displaystyle O n 3 time complexity 页面存档备份 存于互联网档案馆 Java implementation of O n 3 displaystyle O n 3 time variant 页面存档备份 存于互联网档案馆 Python implementation 页面存档备份 存于互联网档案馆 see also here Ruby implementation with unit tests 页面存档备份 存于互联网档案馆 C implementation 页面存档备份 存于互联网档案馆 D implementation with unit tests port of the Java O n 3 displaystyle O n 3 version 页面存档备份 存于互联网档案馆 Online interactive implementation 页面存档备份 存于互联网档案馆 Please note that this implements a variant of the algorithm as described above Graphical implementation with options Java applet Serial and parallel implementations 页面存档备份 存于互联网档案馆 Implementation in Matlab and C 页面存档备份 存于互联网档案馆 Perl implementation Lisp implementation C STL implementation multi functional bipartite graph version 页面存档备份 存于互联网档案馆 C implementation 页面存档备份 存于互联网档案馆 C implementation of the O n 3 displaystyle O n 3 algorithm 页面存档备份 存于互联网档案馆 BSD style open source licensed Another C implementation with unit tests 页面存档备份 存于互联网档案馆 Another Java implementation with JUnit tests Apache 2 0 永久失效連結 MATLAB implementation C implementation 页面存档备份 存于互联网档案馆 Javascript implementation 页面存档备份 存于互联网档案馆 The clue R package proposes an implementation solve LSAP 页面存档备份 存于互联网档案馆 取自 https zh wikipedia org w index php title 匈牙利算法 amp oldid 74890972, 维基百科,wiki,书籍,书籍,图书馆,