匈牙利演算法

匈牙利演算法是一種在多項式時間內求解任務分配問題的組合最佳化演算法，並推動了後來的。美國數學家哈羅德·W·庫恩於1955年提出該演算法。此演算法之所以被稱作匈牙利演算法，是因為演算法很大一部分是基於以前匈牙利數學家和艾蓋瓦里·耶內的工作之上建立起來的。詹姆士·芒克勒斯在1957年回顧了該演算法，並發現它的時間複雜度為多項式時間。 此後該演算法被稱為庫恩-芒克勒斯演算法或芒克勒斯分配演算法。原始演算法的時間複雜度為formula_1，但與理查德·卡普發現可以修改演算法達到formula_2執行時間。小萊斯特·倫道夫·福特和德爾伯特·雷·富爾克森將該方法推廣到一般運輸問題，稱作福特-富爾克森演算法。2006年發現卡爾·雅可比在19世紀就解決了指派問題，該解法在他死後在1890年以拉丁文發表。問題.你有三個工人：吉姆，史提夫和艾倫。你需要其中一個清潔浴室，另一個打掃地板，第三個洗窗，但他們每個人對各項任務要求不同數目數量的錢。以最低成本的分配工作的方式是什麼？可以用工人做工的成本矩陣來表示該問題。例如：當把匈牙利方法應用於上面的表格時，會給出最低成本：為6美元，讓吉姆清潔浴室、史提夫打掃地板、艾倫清洗窗戶就可以達到這一結果。設定.給定一個 formula_3 的非負矩陣，其中第 formula_4 行第 formula_5 列元素表示把第 formula_4 個工人派到第 formula_5個工作的成本。我們必須找到成本最低的工人工作分配。如果目標是找到最高成本的分配，該問題可以將每個成本都換為最高一個成本減去該成本以適應題目。如果用二分圖來闡述該問題可以更容易描述這個演算法。對於一個有 formula_8個工人節點的完全二分圖 formula_12，每條邊都有 formula_13 的非負成本。我們要找到最低成本的完美匹配。如果函式 formula_14 滿足對於每個 formula_15 都有 formula_16，則把該函式叫做勢。勢 formula_17 的值為 formula_18。可以看出，每個完美匹配的成本最低是每個勢的值。匈牙利演算法找出了完美匹配及與之成本/值相等的勢，這證明了兩者的最優性。實際上它找到了緊邊集的完美匹配：緊邊 formula_19 是指對於勢 formula_17 滿足 formula_21。我們將緊邊子圖表示為 formula_22。formula_22 中的完美匹配的成本就等於 formula_17的值。用二分圖描述此演算法.在演算法中我們維持 formula_22 的勢formula_17和方向，該方向有從 formula_11到 formula_9 的邊構成匹配 formula_30 的性質。初始時，formula_17 處處為 0，所有邊都由 formula_9 指向 formula_11。每一步中，我們或者改變 formula_17 使其值增加，或者改變方向以得到更多的邊。我們保持 formula_30 的所有邊都是緊邊不發生改變。當 formula_30 為完美匹配時結束。在一般的步驟中，令 formula_38 和 formula_39 為 formula_30 未覆蓋的節點。令 formula_45 為從 formula_41 只沿緊邊的有向路徑可到達 formula_27 的節點。可由廣度優先搜尋求得。若 formula_48 非空，則將 formula_27 中從 formula_41 到 formula_43 的有向路徑反向。則相應匹配數增加1。若 formula_48 為空，則令 formula_53。formula_54 為正，因為 formula_55 與 formula_56 之間沒有緊邊。在 formula_57 中的節點將formula_17增加formula_54 並在 formula_55 中節點將 formula_17減小 formula_54，得到的formula_17仍然是勢。圖 formula_22 改變了，但它仍包含formula_30。我們把新的邊從formula_9指向formula_11。由 formula_54 的定義，formula_41 可達的節點集 formula_70 增大。我們重複這些步驟直到formula_30為完美匹配，該情形下給出的是最小成本的匹配。此版本的執行時間為 formula_1：formula_30 增廣 formula_8次，在 formula_30 不改變的一個階段中，勢最多改變 formula_8 次。改變勢所需的時間在 formula_78。證明：改變勢函式"y"不改變"M".證明改變formula_79後formula_80中每條邊不發生改變，這等價於證明對於formula_80中任意邊，它的兩個頂點要麼都在formula_45中，要麼都不在formula_45中。為此，定義formula_84為formula_80中一條從formula_86到formula_87的邊，則若formula_88，那麼有formula_89。，因此這條路徑上緊鄰formula_92的點是其他點formula_98。formula_99是一條從formula_86到formula_87的緊邊因此也是formula_80中的一個元素。但因此formula_80包含兩條有共點的邊，與formula_80是匹配的定義矛盾。因此formula_80中每條邊的兩個頂點要麼都在formula_45中，要麼都不在formula_45中。證明："y"仍然是勢函式.證明formula_79在更改之後是勢函式，等價於證明不存在總勢超過成本的邊。這已經在之前的論述中已經為formula_80中的邊建立這個概念，因此我們考慮任意從formula_87到formula_86的邊formula_112。如果formula_113升高了formula_54，那麼：(1)formula_115，在這種情況下，formula_116減小了formula_54，使總體的勢未發生改變；(2)formula_118，這種情況下formula_54的定義保證了formula_120。因此formula_79仍然是勢函式。矩陣解釋.給定 formula_122 個工人和任務，以及一個包含分配給每個工人一個任務的成本的 formula_123矩陣，尋找成本最小化分配。首先把問題寫成下面的矩陣形式formula_124其中 formula_125是執行任務 1, 2, 3, 4 的工人。formula_126 分別表示當工人 formula_127 做任務 1, 2, 3, 4 時的時間損失。對於其他符號也同樣適用。該矩陣是方陣，所以每個工人只能執行一個任務。第 1 步接下來我們對矩陣的行進行操作。將所有 formula_128 。對此過程為所有行重複。我們現在得到一個每行至少有一個零的矩陣。現在我們嘗試給工人指派任務，以使每個工人只做一項任務，並且每個情況的耗散都為零。說明如下。每一行的 0 的個數可以超過 1。若有出現行中 0 的個數超過 1，在最壞的情況下，會需要在 formula_130 的組合中找到一個成本最小的配對。第 2 步有時此階段的該矩陣不能符合指派的要求，例如下面所示矩陣。在上述情形下，不能做出指派。注意到任務 1 由工人 formula_131 和 formula_132 做都很高效 (formula_133 和 formula_134 為 0 )。但兩個工人無法分配到同一個任務。還注意到，沒有任何一個工人能有效地做任務 3 (formula_135、formula_136、formula_137、formula_138 皆不為 0)。為了克服這個問題，我們對所有列重複上述流程並檢查是否可以完成分配。大多數情況下，這都會給出結果，但如果仍然是不可行，那麼我們需要繼續下去。第 3 步必須用盡可能少的列或行標記來覆蓋矩陣中的所有零。下面的過程是完成這個要求的一種方法：首先，儘可能多地分配任務，用 0' 表示的零為已指派的任務，現在到了畫圖的部分。現在劃掉所有已標記的列和未標記的行。上述詳細的描述只是畫出覆蓋所有 0 的線的一種方法。也可以使用其他方法。第 4 步現在刪除已畫線的行和列。這將留下一個矩陣如下：formula_139返回到步驟 1，然後重複這個過程，直到矩陣是空的；當矩陣為空時，意即畫出的覆蓋所有 0 的線的個數等於原本矩陣的行數(或列數) formula_122，在上述的例子中 formula_141，此時代表有一個分配的最佳解存在於這些 0 的組合之中，我們可以在步驟 1 中從所有分配的組合中找到成本最小的解。實現.