匈牙利算法示例ppt

1、匈牙利算法經典問題工作分配n一個公司有n個工作崗位空缺，每個崗位空缺需要有一定資格的人來填補?，F在有m個人申請這n個工作。由于每個人工作能力不同，所以不同的人能勝任不同的工作。n現在已知每個人所能勝任的若干工作，求這m個人最多可以填補幾個工作崗位。n每個人只能做一份工作，每個工作崗位也只需要一個人二分圖n設G=(V,R)是一個無向圖。圖的頂點集V可分割為兩個互不相交的子集X和Y（子集內部沒有邊） ，圖任何一條邊的兩個端點都分屬不同的子集。則稱圖G為二分圖。n用n個頂點X=1,2,3,4,5表示n個工作，用m個頂點Y=A,B,C,D,E,F表示m個工人。12345ABCDEF1,2,3,4,5A

2、,B,C,D,E,F二分圖匹配n給定一個二分圖G，在G的一個子圖M中，M的邊集E中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。在工作分配的問題中，我們給出一個可行的分配方案，就是一個匹配。n選擇這樣的邊數最大的子集稱為圖的最大匹配問題最大匹配問題如果這個匹配是最優(yōu)的（可以填補的工作崗位最多），就是最大匹配。12345ABCDEF12345ABCDEF12345ABCDEF12345ABCDEF2345ABDE12345ABDE12345ABCDE匈牙利算法n增廣路的定義(也稱增廣軌或交錯軌)：若P是圖G中一條連通兩個未匹配頂點的路徑，并且屬M的邊和不屬M的邊(即已匹配和待匹配的邊)在P

3、上交替出現，則稱P為相對于M的一條增廣路徑。n由增廣路的定義可以推出下述三個結論：n1）P的路徑長度必定為奇數，第一條邊和最后一條邊都不屬于M。n2）P經過取反操作可以得到一個更大的匹配M。n3）M為G的最大匹配當且僅當不存在相對于M的增廣路徑。ABCD5EFABCD5EF匈牙利算法ABCD5EFABCD5EF(1)找到某一匹配M(2)找出一條增廣路徑P，通過取反操作獲得更大的匹配M代替M(3)重復(2)操作直到找不出增廣路徑為止 設有n個工作，要由 n個人來承擔，每個工作只能由一個人承擔，且每個人只能承擔一個工作。cij表示第i個人做第j件事的費用,求總費用最低的指派方案。 jiijijxc

4、Zmin1.21inijiixxxxt si=1,2, ,n121njijjjxxxxj=1,2, ,nnjnixij, 2 , 1;, 2 , 11 , 0分配問題及其分配問題及其數學模型數學模型 有甲、乙、丙、丁、戊五有甲、乙、丙、丁、戊五位工人被指派去完成位工人被指派去完成A、B 、 C 、 D 、 E五項任務，每五項任務，每個人完成任務所需的工時個人完成任務所需的工時各不相同，見表。求應如各不相同，見表。求應如何指派人員才能使得所用何指派人員才能使得所用工時最少？工時最少？ABCDE甲127979乙89666丙71712149丁15146610戊4107109任務時間人員8n 9n匈牙

5、利算法的基本原理是基于以下兩個定理匈牙利算法的基本原理是基于以下兩個定理. n定理定理1 設C=(Cij)nn是指派問題的效益矩陣，若將C中的任一行（或任一列）減去該行（或該列）中的最小元素，得到新的效率矩陣C，則C對應的新的指派問題與原指派問題有相同的最優(yōu)解. n定理定理2 效率矩陣C中獨立的0元素的最多個數等于覆蓋所有0元素的最少直線數. 當獨立零元素的個數等于矩陣的階數時就得到最優(yōu)解.匈牙利法的解題步驟：匈牙利法的解題步驟：n 第一步：變換指派問題的系數矩陣（第一步：變換指派問題的系數矩陣（cij）為）為(bij)，使在，使在(bij)的各行各列中都出現的各行各列中都出現0元素，元素，即

6、即n (1) 從（從（cij）的）的每行元素都減去該行的最小每行元素都減去該行的最小元素；元素；n (2) 再從所得新系數矩陣的再從所得新系數矩陣的每列元素中減去每列元素中減去該列的最小元素。該列的最小元素。()ijc12 7979896667 17 12 14 915 14 66 104 10 7 10 9502 0 2230 0 00 10 5 72980 0 4063 6 5-7-6-7-6-4-0-0502 0 2230 0 00 10 5 72980 0 4063 6 5-0 -0-0 第二步：進行試指派，以尋求最優(yōu)解。第二步：進行試指派，以尋求最優(yōu)解。 在在(bij)中找盡可能多的

7、中找盡可能多的獨立獨立0元素元素，若能找出，若能找出n個個獨立獨立0元素，就以這元素，就以這n個獨立個獨立0元素對應解矩陣元素對應解矩陣(xij)中的中的元素為元素為1，其余為，其余為0，這就得到最優(yōu)解。，這就得到最優(yōu)解。找獨立找獨立0元素，元素，常用的步驟為常用的步驟為： (1)從從只有一個只有一個0元素的元素的行行(列列)開始，給這個開始，給這個0元素加圈，記作元素加圈，記作 。然后劃。然后劃去去 所在所在列列(行行)的其它的其它0元素，記作元素，記作 ；這表示這列所代表的任務已指派完，；這表示這列所代表的任務已指派完，不必再考慮別人了。不必再考慮別人了。 (2)給只有一個給只有一個0元素

8、的元素的列列(行行)中的中的0元素加圈，記作元素加圈，記作；然后劃去；然后劃去 所在所在行的行的0元素，記作元素，記作 (3)反復進行反復進行(1)，(2)兩步，直到盡可能多的兩步，直到盡可能多的0元素都被圈出和劃掉為止。元素都被圈出和劃掉為止。50202230000 1057298004063655636489275103222550202230000 105729800406365 第三步；作最少的直線覆蓋所有第三步；作最少的直線覆蓋所有0元素，以確元素，以確定該系數矩陣中能找到最多的獨立元素數。定該系數矩陣中能找到最多的獨立元素數。（1）對沒有）對沒有的行打的行打（2）在已經打）在已經打

9、的行中所含有的的行中所含有的0元素打元素打號號（3）在已經打）在已經打號的列中含號的列中含元元素的行打素的行打；（4）重復（）重復（2）（）（3）直到得不出）直到得不出打打的行列為止的行列為止（5）對沒有打）對沒有打的行畫一橫線，的行畫一橫線，有打有打的列畫一縱線，這就覆蓋所的列畫一縱線，這就覆蓋所有有0元素的最少直線數。令這一直元素的最少直線數。令這一直線數為線數為l。若。若ln,說明必須再換當說明必須再換當前的系數矩陣，才能找到前的系數矩陣，才能找到n個獨立個獨立的的0元素，為此轉到第四步；若元素，為此轉到第四步；若l=n，而，而mn，應回到（，應回到（2）（）（4）另行試探。另行試探。5

10、0202230000105729800406365 第四步；在沒有被直線覆蓋的部分中找出最小元素。第四步；在沒有被直線覆蓋的部分中找出最小元素。然后在行打然后在行打行每個元素減去這一最小元素，而在打行每個元素減去這一最小元素，而在打列的每個元素都加上這一最小元素，以保證原來列的每個元素都加上這一最小元素，以保證原來0元元素不變。這樣得到新系數矩陣。若得到素不變。這樣得到新系數矩陣。若得到n個獨立的個獨立的0元素，則已得到最優(yōu)解，否則回到第三步。元素，則已得到最優(yōu)解，否則回到第三步。34144811538342273414481153834227上面矩陣有上面矩陣有5個獨立個獨立0元素，這就得到

11、相應的最優(yōu)解。元素，這就得到相應的最優(yōu)解。50202230000105729800406365 -2-2+200001010001000000100000100000100100100000100000010或解矩陣得到解矩陣得到2個最優(yōu)指派方案；（個最優(yōu)指派方案；（1）甲）甲-B，乙，乙-C，丙丙-E，丁，丁-D,戊戊-A；（；（2）甲）甲-B，乙，乙-D，丙，丙-E,丁丁-C，戊戊-A。所需時間為。所需時間為minz=7+6+9+6+4=3215非標準型的指派問題：匈牙利法的條件是：模型求最小值、效率匈牙利法的條件是：模型求最小值、效率cij0。當遇到各種非標準形式的指派問題時，處理方法是先將當遇到各種非標準形式的指派問題時，處理方法是先將其轉化為標準形式，其轉化為標準形式，1、人數和事數不相等的指派問題：人少事情多，虛擬、人數和事數不相等的指派問題：人少事情多，虛擬“人人”，做各事的費用系數為，做各事的費用系數為0；人多事情少，虛擬；人多事情少，虛擬“事事”，各人做的費用系數為，各人做的費用系數為0。2、對于求極大化的問題，只要系數矩陣變換為、對于求極大化的問題，只要系數矩陣變換為B（m-cij）nn，仍可利用匈牙利算法進行求