愛悠閑 > KM算法的介紹

KM算法的介紹

分類: ACM  |  標簽: 算法,n2  |  作者: shiren_bod 相關  |  發布日期 : 2012-10-21  |  熱度 : 0°

 

KM算法是通過給每個頂點一個標號(叫做頂標)來把求最大權匹配的問題轉化為求完備匹配的問題的。設頂點Xi的頂標為A[ i ],頂點Yj的頂標為B[ j ],頂點Xi與Yj之間的邊權為w[i,j]。在算法執行過程中的任一時刻,對于任一條邊(i,j),A[ i ]+B[j]>=w[i,j]始終成立。KM算法的正確性基于以下定理:
若由二分圖中所有滿足A[ i ]+B[j]=w[i,j]的邊(i,j)構成的子圖(稱做相等子圖)有完備匹配,那么這個完備匹配就是二分圖的最大權匹配。
這個定理是顯然的。因為對于二分圖的任意一個匹配,如果它包含于相等子圖,那么它的邊權和等于所有頂點的頂標和;如果它有的邊不包含于相等子圖,那么它的邊權和小于所有頂點的頂標和。所以相等子圖的完備匹配一定是二分圖的最大權匹配。
初始時為了使A[ i ]+B[j]>=w[i,j]恒成立,令A[ i ]為所有與頂點Xi關聯的邊的最大權,B[j]=0。如果當前的相等子圖沒有完備匹配,就按下面的方法修改頂標以使擴大相等子圖,直到相等子圖具有完備匹配為止。
我們求當前相等子圖的完備匹配失敗了,是因為對于某個X頂點,我們找不到一條從它出發的交錯路。這時我們獲得了一棵交錯樹,它的葉子結點全部是X頂點。現在我們把交錯樹中X頂點的頂標全都減小某個值d,Y頂點的頂標全都增加同一個值d,那么我們會發現:
1)兩端都在交錯樹中的邊(i,j),A[ i ]+B[j]的值沒有變化。也就是說,它原來屬于相等子圖,現在仍屬于相等子圖。
2)兩端都不在交錯樹中的邊(i,j),A[ i ]和B[j]都沒有變化。也就是說,它原來屬于(或不屬于)相等子圖,現在仍屬于(或不屬于)相等子圖。
3)X端不在交錯樹中,Y端在交錯樹中的邊(i,j),它的A[ i ]+B[j]的值有所增大。它原來不屬于相等子圖,現在仍不屬于相等子圖。
4)X端在交錯樹中,Y端不在交錯樹中的邊(i,j),它的A[ i ]+B[j]的值有所減小。也就說,它原來不屬于相等子圖,現在可能進入了相等子圖,因而使相等子圖得到了擴大。
現在的問題就是求d值了。為了使A[ i ]+B[j]>=w[i,j]始終成立,且至少有一條邊進入相等子圖,d應該等于:
Min{A[ i ]+B[j]-w[i,j] | Xi在交錯樹中,Yi不在交錯樹中}。
以上就是KM算法的基本思路。但是樸素的實現方法,時間復雜度為O(n4)——需要找O(n) 次增廣路,每次增廣最多需要修改O(n)次頂標,每次修改頂標時由于要枚舉邊來求d值,復雜度為O(n2)。實際上KM算法的復雜度是可以做到O(n3) 的。我們給每個Y頂點一個“松弛量”函數slack,每次開始找增廣路時初始化為無窮大。在尋找增廣路的過程中,檢查邊(i,j)時,如果它不在相等子圖 中,則讓slack[j]變成原值與A[ i ]+B[j]-w[i,j]的較小值。這樣,在修改頂標時,取所有不在交錯樹中的Y頂點的slack值中的最小值作為d值即可。但還要注意一點:修改頂標 后,要把所有的slack值都減去d。
Kuhn-Munkras算法流程:
(1)初始化可行頂標的值
(2)用匈牙利算法尋找完備匹配
(3)若未找到完備匹配則修改可行頂標的值
(4)重復(2)(3)直到找到相等子圖的完備匹配為止

KM算法部分抄自http://hi.baidu.com/highkobe/blog/item/05340916f41d101e972b43f7.html



快乐彩中奖说明