二分圖的最優(yōu)匹配(KM算法)

1、二分圖的最優(yōu)匹配（KM算法）KM算法用來解決最大權(quán)匹配問題： 在一個二分圖內(nèi)，左頂點為X，右頂點為Y，現(xiàn)對于每組左右連接XiYj有權(quán)wij，求一種匹配使得所有wij的和最大?；驹碓撍惴ㄊ峭ㄟ^給每個頂點一個標(biāo)號（叫做頂標(biāo)）來把求最大權(quán)匹配的問題轉(zhuǎn)化為求完備匹配的問題的。設(shè)頂點Xi的頂標(biāo)為A i ，頂點Yj的頂標(biāo)為B j ，頂點Xi與Yj之間的邊權(quán)為wi,j。在算法執(zhí)行過程中的任一時刻，對于任一條邊(i,j)，A i +Bj>=wi,j始終成立。KM算法的正確性基于以下定理：若由二分圖中所有滿足A i +Bj=wi,j的邊(i,j)構(gòu)成的子圖（稱做相等子圖）有完備匹配，那么這個完備匹配就

2、是二分圖的最大權(quán)匹配。首先解釋下什么是完備匹配，所謂的完備匹配就是在二部圖中，X點集中的所有點都有對應(yīng)的匹配或者是Y點集中所有的點都有對應(yīng)的匹配，則稱該匹配為完備匹配。這個定理是顯然的。因為對于二分圖的任意一個匹配，如果它包含于相等子圖，那么它的邊權(quán)和等于所有頂點的頂標(biāo)和；如果它有的邊不包含于相等子圖，那么它的邊權(quán)和小于所有頂點的頂標(biāo)和。所以相等子圖的完備匹配一定是二分圖的最大權(quán)匹配。初始時為了使A i +Bj>=wi,j恒成立，令A(yù) i 為所有與頂點Xi關(guān)聯(lián)的邊的最大權(quán)，Bj=0。如果當(dāng)前的相等子圖沒有完備匹配，就按下面的方法修改頂標(biāo)以使擴大相等子圖，直到相等子圖具有完備匹配為止。我們

3、求當(dāng)前相等子圖的完備匹配失敗了，是因為對于某個X頂點，我們找不到一條從它出發(fā)的交錯路。這時我們獲得了一棵交錯樹，它的葉子結(jié)點全部是X頂點?，F(xiàn)在我們把交錯樹中X頂點的頂標(biāo)全都減小某個值d，Y頂點的頂標(biāo)全都增加同一個值d，那么我們會發(fā)現(xiàn)：1）兩端都在交錯樹中的邊(i,j)，A i +Bj的值沒有變化。也就是說，它原來屬于相等子圖，現(xiàn)在仍屬于相等子圖。2）兩端都不在交錯樹中的邊(i,j)，A i 和Bj都沒有變化。也就是說，它原來屬于（或不屬于）相等子圖，現(xiàn)在仍屬于（或不屬于）相等子圖。3）X端不在交錯樹中，Y端在交錯樹中的邊(i,j)，它的A i +Bj的值有所增大。它原來不屬于相等子圖，現(xiàn)在仍不

4、屬于相等子圖。4）X端在交錯樹中，Y端不在交錯樹中的邊(i,j)，它的A i +Bj的值有所減小。也就說，它原來不屬于相等子圖，現(xiàn)在可能進入了相等子圖，因而使相等子圖得到了擴大。（針對之后例子中x1->y4這條邊）現(xiàn)在的問題就是求d值了。為了使A i +Bj>=wi,j始終成立，且至少有一條邊進入相等子圖，d應(yīng)該等于：MinAi+Bj-wi,j | Xi在交錯樹中，Yi不在交錯樹中。改進以上就是KM算法的基本思路。但是樸素的實現(xiàn)方法，時間復(fù)雜度為O(n4)需要找O(n)次增廣路，每次增廣最多需要修改O(n)次頂標(biāo)，每次修改 頂標(biāo)時由于要枚舉邊來求d值，復(fù)雜度為O(n2)。實際上KM

5、算法的復(fù)雜度是可以做到O(n3)的。我們給每個Y頂點一個“松弛量”函數(shù)slack，每次 開始找增廣路時初始化為無窮大。在尋找增廣路的過程中，檢查邊(i,j)時，如果它不在相等子圖中，則讓slackj變成原值與A i +Bj-wi,j的較小值。這樣，在修改頂標(biāo)時，取所有不在交錯樹中的Y頂點的slack值中的最小值作為d值即可。但還要注意一點：修改頂標(biāo)后，要把所有的不在交錯樹中的Y頂點的slack值都減去d（因為：d的定義為 min (x,y)| Lx(x)+ Ly(y)- W(x,y), x S, y T （關(guān)鍵，關(guān)鍵），此時屬于S的X均已經(jīng)減去d了，所以不屬于T的y也要減去d，防止下次循環(huán)更改

6、出錯）。KuhnMunkras算法流程：(1)初始化可行頂標(biāo)的值(2)用匈牙利算法尋找完備匹配(3)若未找到完備匹配則修改可行頂標(biāo)的值(4)重復(fù)(2)(3)直到找到相等子圖的完備匹配為止已知K5,5的權(quán)矩陣為y1 y2 y3 y4 y5x1 3 5 5 4 1x2 2 2 0 2 2x3 2 4 4 1 0x4 0 1 1 0 0x5 1 2 1 3 3求最佳匹配，其中K5,5的頂劃分為X=xi,Y=yi,i=1,2,3,4,5.解：(1)取可行頂標(biāo)l(v)為 l(yi)=0,i=1,2,3,4,5；l(x1)=max3,5,5,4,1=5,l(x2)=max2,2,0,2,2=2,l(x3)

7、=max(2,4,4,1,0=4,l(x4)=max0,1,1,0,0=1,l(x5)=max1,2,1,3,3=3.(2) Gl及其上之匹配見圖7.12。這個圖中(G-x2)=3,由Tutte定理知無完備匹配。需要修改頂標(biāo)。(3) u=x4,得S=x4,x3,x1,T=y3,y2,N(S)=T,于是al=min(l(x)+l(y)-w(xy)=1. (xS,yT)x1,x2,x3,x4,x5的頂標(biāo)分別修改成4,2,3,0,3；y1,y2,y3,y4,y5的頂標(biāo)分別修改成0,1,1,0,0。(4) 用修改后的頂標(biāo)l得Gl及其上面的一個完備匹配如圖7.13。圖中粗實線給出了一個最佳匹配，其最大權(quán)

8、是2+4+1+4+3=14。我們看出：al>0；修改后的頂標(biāo)仍是可行頂標(biāo)；Gl中仍含Gl中的匹配M；Gl中至少會出現(xiàn)不屬于M的一條邊，所以會造成M的逐漸增廣。得到可行頂標(biāo)后求最大匹配：書上這部分沒講，實際上是這樣的，對于上面這個例子來說，通過Kuhn-Munkres得到了頂標(biāo)l(x)= 4,2,3,0,3,l(y)=0,1,1,0,0,那么，對于所有的l(xi)+l(yj) = w(i,j)，在二分圖G設(shè)置存在邊w(i,j)。再用匈牙利算法求出最大匹配，再把匹配中的每一邊的權(quán)值加起來就是最后的結(jié)果了。 | 1 2 3 | 3 2 4 | 2 3 5 |若要對這個完全二分圖求最佳匹配初始化

9、：Lx(1)= max y| w(1,y), 1<= y<= 3 = max 1, 2, 3 = 3, Ly(1)= 0Lx(2)= max 3, 2, 4 = 4, Ly(2)= 0Lx(3)= max 2, 3, 5 = 5, Ly(3)= 0;我們建立等價子圖( 滿足 Lx(x)+ Ly(y)= W(x,y) ) 如下：對于該圖，運用匈牙利算法對 X 部頂點 1 求增廣路徑，得到一個匹配，如圖( 紅色代表匹配邊 )：對 X 部頂點 2 求增廣路徑失敗，尋找增廣路徑的過程為 X 2-> Y 3-> X 1。我們把尋找增廣路徑失敗的 DFS 的交錯樹中，在 X 部頂點

10、集稱之為 S， 在 Y 部的頂點集稱之為 T。則 S= 1, 2 ，T= 3 。現(xiàn)在我們就通過修改頂標(biāo)值來擴大等價子圖，如何修改。1) 我們尋找一個 d 值，使得 d= min (x,y)| Lx(x)+ Ly(y)- W(x,y), x S, y T ，因些，這時 d= min Lx(1)+Ly(1)-W(1,1), Lx(1)+Ly(2)-W(1,2), Lx(2)+Ly(1)-W(2,1), Lx(2)+Ly(2)-W(2,2) =min 3+0- 1, 3+0-2, 4+0-3, 4+0-2 = min 2, 1, 1, 2 = 1。尋找最小的 d 是為了保證修改后仍滿足性質(zhì)對于邊 &

11、lt;x,y> 有 Lx(x)+ Ly(y)>= W(x,y)。2) 然后對于頂點 x1. 如果 x S 則 Lx(x)= Lx(x)- d。2. 如果 x T 則 Ly(x)= Ly(x)+ d。3. 其它情況保持不變。如此修改后，我們發(fā)現(xiàn)對于邊<x,y>，頂標(biāo) Lx(x)+ Ly(y) 的值為1. Lx(x)- d+ Ly(y)+ d， x S, y T。2. Lx(x)+ Ly(y)， x S, y T。3. Lx(x)- d+ Ly(y)， x S, y T。4. Lx(x)+ Ly(y)+ d， x S, y T。易知，修改后對于任何邊仍滿足 Lx(x)+ Ly(y)>= W(x,y)，并且第三種情況頂標(biāo)值減少了 d，如此定會使等價子圖擴大。 就上例而言: 修改后 Lx(1)= 2, Lx(2)= 3, Lx(3)= 5, Ly(1)= 0, Ly(1)= 0, Ly(2)= 0,