匈牙利算法示例ppt

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

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

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

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

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

6、即n (1) 從（從（cij）的）的每行元素都減去該行的最小每行元素都減去該行的最小元素；元素；n (2) 再從所得新系數(shù)矩陣的再從所得新系數(shù)矩陣的每列元素中減去每列元素中減去該列的最小元素。該列的最小元素。()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 第二步：進(jìn)行試指派，以尋求最優(yōu)解。第二步：進(jìn)行試指派，以尋求最優(yōu)解。 在在(bij)中找盡可能多的

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

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

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

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

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