匈牙利演算法

匈牙利演算法是一種佇多項式時間內求解任務分配問題的組合最佳化演算法，並推動後來的原始對尪仔方法。美國數學家哈羅德 ・ 庫恩佇一九五五年提出這个該演算法。這个演算法所以予人講號做匈牙利演算法，是因為演算法誠大一部份是以前匈牙利數學家科尼格 ・ 德內啥物和艾蓋瓦里 ・ 耶內工課之上建立起來的。

詹姆士 ・ 芒克勒斯佇一九五七年回顧矣該演算法，並且發現伊的時間複雜度做（強）多項式時間。此後這个演算法予人號做Kuhn–Munkres 演算法抑是Munkres 分配演算法。原始演算法的時間複雜度做 $ O ( n ^ { 四 } ) $，但傑克 ・ 愛德蒙斯佮卡普發現會當修改演算法達到 $ O ( n ^ { 三 } ) $ 執行時間，富澤嘛獨立發現矣這點。L ・ R ・ 阮福特佮 D ・ R ・ 福爾克森將這个方法來推廣到一般運輸問題。二空空六年發現卡爾 ・ 雅可比佇咧十九世紀就解決矣指派問題，該解法佇伊死了後佇一八九空年以拉丁文發表。

Layman 對指派問題的解說

你有三个工人：吉姆，史提夫和艾倫。 你需要其中一个清潔浴間仔，另外一个摒掃塗跤，第三个洗窗仔，毋過𪜶每一个人對各項任務要求無仝數目數量的錢。 以上低成本的彼个分配工課的方式是啥物？ 會當用工人做工的成本矩陣來表示該問題。比如講：

做共匈牙利方法應用佇頂頭的表格的時，會予出最低成本：為著六美元，予吉姆清潔浴間仔、史提夫摒掃塗跤、艾倫洗窗仔門就會當達成這結果。

設定

予定一个 $ n \ times n $ 的非負矩陣，其中第 $ i $ 行第 $ j $ 列元素表示共第 $ i $ 個工人派到第 $ j $ 個工課的成本。咱著愛揣著成本上低的工人工課分配。若目標是揣著上懸的成本的分配，該問題會當共每一个成本攏換做上懸一个成本減去該成本以適應題目。

若是用二分圖來闡述該問題會閣較容易描述這个演算法。對一个有 $ n $ 個工人節點（$ S $）佮 $ n $ 個工作較節點（$ T $）的完全二分圖 $ G=( S \ cup 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 _ { y } $。$ G _ { y } $ 中央的完美匹配的成本（若佇咧）就等於講 $ y $ 的值。

用兩分圖來講這个演算法

佇演算法內面咱維持 $ G _ { y } $ 的勢 $ y $ 佮方向（表示講 $ { \ overrightarrow { G _ { y } } } $）， 該方向有對 $ T $ 到 $ S $ 的邊構成匹配 $ M $ 的性質。初初的時陣，$ y $ 做零， 所有那攏由 $ S $ 指向 $ T $（所以 $ M $ 為空）。 每一步內底，阮抑是改變 $ y $ 使其值增加， 抑是改變方向以得著閣較濟的邊仔。阮保持 $ M $ 所有那攏是那發生改變。當 $ M $ 為完美匹配的時陣結束。

佇一般的工夫內底，令 $ R _ { S } \ subseteq S $ 和 $ R _ { T } \ subseteq T $ 為 $ M $ 未崁的節點 （ 著 $ R _ { S } $ 包含 $ S $ 做零的節點，而且 $ R _ { T } $ 中包括 $ T $ 中出度做零的節點）。 令 $ Z $ 為對 $ R _ { S } $ 干焦沿路會當到位 $ { \ overrightarrow { G _ { y } } } $ 的儉點。會當由闊度優先搜揣著。

若是 $ R _ { T } \ cap Z $ 非空，則將 $ { \ overrightarrow { G _ { y } } } $ 對中 $ R _ { S } $ 到 $ R _ { T } $ 的有向路徑顛倒向。是相應匹配數增加一。

若是 $ 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 S $ 佮 $ T \ 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 ^ { 四 } ) $：$ M $ 增廣 $ n $ 次， 佇咧 $ M $ 無改變的一个階段內底，勢上濟改變 $ n $ 次（因為乎 $ Z $ 逐改攏來增加）。 改變所需要的時間佇 $ O ( n ^ { 二 } ) $。

證明：改變勢函式 _ y _ 無改變 _ M _

證明改變 $ y $ 後 $ M $ 中逐條邊無發生改變，這等於證明對 $ M $ 中任意邊，伊的兩个頂點愛啥物攏佇咧 $ Z $ 中，愛攏無佇咧 $ Z $ 中。為此，定義 $ vu $ 為 $ M $ 中一條對 $ T $ 到 $ S $ 的邊仔，則若 $ v \ in Z $，遐爾有 $ u \ in Z $。（反證）準講 $ u \ in Z $ 猶毋過 $ v \ notin Z $；因為 $ u $ 是一个匹配邊仔的尾溜點，$ u \ notin R _ { S } $，因此存在自 $ R _ { S } $ 到 $ u $ 的有向路徑。這條路徑必須袂使經過 $ v $（根據假設）， 所以這條路途就佇邊仔 $ u $ 的點是其他點 $ v'\ in T $。$ v'u $ 是一條對 $ T $ 到 $ S $ 的絚邊因此嘛是 $ M $ 中的一个元素。但是因此 $ M $ 包含講兩條有共點的邊，佮 $ M $ 是匹配的定義矛盾。所以 $ M $ 中逐條邊的兩个頂點愛啥物攏佇咧 $ Z $ 中，愛攏無佇咧 $ Z $ 中。

證明：_ y _ 猶原是勢函式

證明 $ y $ 佇咧更改了後是勢函式，等價於證明不存在總勢超過成本的邊。這已經佇進前的論述中已經為 $ M $ 中的邊建立這个概念，所以阮考慮任意自 $ S $ 到 $ T $ 的邊仔 $ uv $。若是 $ y ( u ) $ 衝懸起來 $ \ Delta $，遐爾：( 一 ) $ v \ in Z \ cap T $，佇這个情形下，$ y ( v ) $ 減細矣 $ \ Delta $，予總體的勢未發生改變；( 二 ) $ v \ in T \ setminus Z $，這款情形下 $ \ Delta $ 的定義保證矣 $ y ( u ) + y ( v ) + \ Delta \ leq c ( u , v ) $。所以 $ y $ 猶原是勢函式。

矩陣來解說

予定 $ n $ 個工人佮任務，佮一个包含分配予每一个工人一个任務的成本的 $ n \ times n $ 矩陣，走揣成本上小化分配。

首先共問題寫做下跤的矩陣形式

$ { \ begin { bmatrix } a _ { 一 } & a _ { 二 } & a _ { 三 } & a _ { 四 } \ \ b _ { 一 } & b _ { 二 } & b _ { 三 } & b _ { 四 } \ \ c _ { 一 } & c _ { 二 } & c _ { 三 } & c _ { 四 } \ \ d _ { 一 } & d _ { 二 } & d _ { 三 } & d _ { 四 } \ end { bmatrix } } $

其中 $ a , b , c , d $ 是執行任務一 , 二 , 三 , 四个工人。$ a _ { 一 } , a _ { 二 } , a _ { 三 } , a _ { 四 } $ 分別表示講工人 $ a $ 做任務一 , 二 , 三 , 四時的時間的損失（成本）。 對其他符號嘛是仝款適用。該矩陣是方陣，所以逐个工人干焦會當執行一个任務。

第一步

紲落來咱對矩陣的行來操作。將所有 $ a _ { i } $（$ i $ 對一到四）中上細的元素取走，該當是每一个元素攏減去拄仔取走的元素。這會讓該行至少出現一個零（啊當彼一逝有兩个相等的上小元素的時會得著加一个零）。 對這个過程為所有的行重複。咱這馬得著一个每行至少有一个零的矩陣。這馬阮試予工人指派任務，以使每一个工人干焦做一項任務，而且逐个狀況的了散攏替零。說明如下。

用零'表示的零為已經指派的任務。

第二步

有時此階段的該矩陣袂當符合指派的要求，譬如講下跤所示矩陣。

欲描述的情形下，袂當做出指派。注意著任務一由工人 $ a $ 和 $ c $ 伊做攏真高效。只是袂使共兩个工人分配著仝一个任務中去。猶閣注意著，無任何一个工人會當有效地做任務三。 為著克服這个問題，咱對所有列重複上路的流程（即每一列所有的元素攏減去該列上小元素）並檢查敢有會當完成分配。

大多數的情況下，這攏會共出結果，但是猶原是不可行，若按呢阮需要閣繼續落去。

第三步

著愛用盡量少的列抑是行標記來崁矩陣內底所有的零。下跤的過程是完成這个要求的一種方法：

首先，儘可能多地分配任務。

• 第一途有一个零，所以分配著。第三行的零因為佮仝一列攏規畫掉。
• 第二行有一个零，所以分配著。
• 第三行干焦一个已經畫掉的零，所以袂當分配。
• 第四行有兩个無劃去的零。會當分配任何有一个（攏是最佳）， 並且共另外一个零划去。

抑是講，分配的是第三行的零，就會使第一途的零予人劃掉。

這馬到畫圖的部份。

• 標記所有無分配的行（第三行）。
• 標記所有新標記的行中零所在（而且無標記）的對應列（第一列）。
• 標記所有佇新標記的列內底有分配的行（第一途）。
• 對所有無分配的行重複上路過程。

這馬畫掉所有已經標記的列和未標記的行（第一列佮第二 , 四行）。

共伊講詳細畫出來講只是畫出所有零的（直、走）線的一種方法。嘛會當使用其他的方法。

第四步

這馬刪除已經畫線的行佮列。這將留下一个矩陣如下：

$ { \ begin { bmatrix } a _ { 二 } & a _ { 三 } & a _ { 四 } \ \ c _ { 二 } & c _ { 三 } & c _ { 四 } \ end { bmatrix } } $

倒轉來行順序，然後重複這个過程，直到矩陣伊是空的。

參考書目

• R . E . Burkard , M . Dell'Amico , S . Martello : _ Assignment Problems _ ( Revised reprint ) . SIAM , Philadelphia ( PA . ) 二千空一十二 . ISBN 九百七十八追一孵六孵一千一百九十七孵兩百二十二孵一
• M . Fischetti , " Lezioni di Ricerca Operativa " , Edizioni Libreria Progetto Padova , Italia , 一千九百九十五 .
• R . Ahuja , T . Magnanti , J . Orlin , " Network Flows " , Prentice Hall , 一千九百九十三 .
• S . Martello , " Jeno Egerváry : from the origins of the Hungarian algorithm to satellite communication " . Central European Journal of Operations Research 十八 , 四十七–五十八 , 二千空一十

外部連結

• Bruff , Derek , " The Assignment Problem and the Hungarian Method " , [一]
• 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 , András Frank , Egervary Research Group , Pazmany P . setany 一 / C , H 一千一百十七 , 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 ^ 四 ) time complexity ) , Liu , Shell .
• Solve any Assignment Problem online , provides a step by step explanation of the Hungarian Algorithm .

實現

（ 請注意，毋是所有的這攏滿足 $ O ( n ^ { 三 } ) $ 時間約束。）

• C implementation with $ O ( n ^ { 三 } ) $ time complexity
• Java implementation of $ O ( n ^ { 三 } ) $ 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 ^ { 三 } ) $ 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 ^ { 三 } ) $ algorithm ( BSD style open source licensed )
• Another C + + implementation with unit tests
• Another Java implementation with JUnit tests ( Apache 二孵空 )
• MATLAB implementation
• C implementation
• Javascript implementation
• The clue R package proposes an implementation , solve \ _ LSAP