資源描述：
《ku二分圖最大權(quán)匹配(km算法)hn》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、Kuhn-Munkres算法來(lái)自"NOCOW"跳轉(zhuǎn)到:導(dǎo)航,搜索Maigo的KM算法講解（的確精彩）KM算法是通過(guò)給每個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)（叫做頂標(biāo)）來(lái)把求最大權(quán)匹配的問(wèn)題轉(zhuǎn)化為求完備匹配的問(wèn)題的。設(shè)頂點(diǎn)Xi的頂標(biāo)為A[i]，頂點(diǎn)Yi的頂標(biāo)為B[i]，頂點(diǎn)Xi與Yj之間的邊權(quán)為w[i,j]。在算法執(zhí)行過(guò)程中的任一時(shí)刻，對(duì)于任一條邊(i,j)，A[i]+B[j]>=w[i,j]始終成立。KM算法的正確性基于以下定理： *若由二分圖中所有滿足A[i]+B[j]=w[i,j]的邊(i,j)構(gòu)成的子圖（稱做相等子圖）有完備匹配，那么這個(gè)完備匹配就是二分圖的最大權(quán)匹配?！ ∵@個(gè)定理是顯然的。
2、因?yàn)閷?duì)于二分圖的任意一個(gè)匹配，如果它包含于相等子圖，那么它的邊權(quán)和等于所有頂點(diǎn)的頂標(biāo)和；如果它有的邊不包含于相等子圖，那么它的邊權(quán)和小于所有頂點(diǎn)的頂標(biāo)和。所以相等子圖的完備匹配一定是二分圖的最大權(quán)匹配?！ 〕跏紩r(shí)為了使A[i]+B[j]>=w[i,j]恒成立，令A(yù)[i]為所有與頂點(diǎn)Xi關(guān)聯(lián)的邊的最大權(quán)，B[j]=0。如果當(dāng)前的相等子圖沒(méi)有完備匹配，就按下面的方法修改頂標(biāo)以使擴(kuò)大相等子圖，直到相等子圖具有完備匹配為止?！ ∥覀兦螽?dāng)前相等子圖的完備匹配失敗了，是因?yàn)閷?duì)于某個(gè)X頂點(diǎn)，我們找不到一條從它出發(fā)的交錯(cuò)路。這時(shí)我們獲得了一棵交錯(cuò)樹，它的葉子結(jié)點(diǎn)全部是X頂點(diǎn)?，F(xiàn)在我們把交錯(cuò)樹中
3、X頂點(diǎn)的頂標(biāo)全都減小某個(gè)值d，Y頂點(diǎn)的頂標(biāo)全都增加同一個(gè)值d，那么我們會(huì)發(fā)現(xiàn)：兩端都在交錯(cuò)樹中的邊(i,j)，A[i]+B[j]的值沒(méi)有變化。也就是說(shuō)，它原來(lái)屬于相等子圖，現(xiàn)在仍屬于相等子圖。兩端都不在交錯(cuò)樹中的邊(i,j)，A[i]和B[j]都沒(méi)有變化。也就是說(shuō)，它原來(lái)屬于（或不屬于）相等子圖，現(xiàn)在仍屬于（或不屬于）相等子圖。X端不在交錯(cuò)樹中，Y端在交錯(cuò)樹中的邊(i,j)，它的A[i]+B[j]的值有所增大。它原來(lái)不屬于相等子圖，現(xiàn)在仍不屬于相等子圖。X端在交錯(cuò)樹中，Y端不在交錯(cuò)樹中的邊(i,j)，它的A[i]+B[j]的值有所減小。也就說(shuō)，它原來(lái)不屬于相等子圖，現(xiàn)在可能進(jìn)入
4、了相等子圖，因而使相等子圖得到了擴(kuò)大?！ ‖F(xiàn)在的問(wèn)題就是求d值了。為了使A[i]+B[j]>=w[i,j]始終成立，且至少有一條邊進(jìn)入相等子圖，d應(yīng)該等于min{A[i]+B[j]-w[i,j]
5、Xi在交錯(cuò)樹中，Yi不在交錯(cuò)樹中}。 以上就是KM算法的基本思路。但是樸素的實(shí)現(xiàn)方法，時(shí)間復(fù)雜度為O(n4)——需要找O(n)次增廣路，每次增廣最多需要修改O(n)次頂標(biāo)，每次修改頂標(biāo)時(shí)由于要枚舉邊來(lái)求d值，復(fù)雜度為O(n2)。實(shí)際上KM算法的復(fù)雜度是可以做到O(n3)的。我們給每個(gè)Y頂點(diǎn)一個(gè)“松弛量”函數(shù)slack，每次開始找增廣路時(shí)初始化為無(wú)窮大。在尋找增廣路的過(guò)程中，檢查邊(i
6、,j)時(shí)，如果它不在相等子圖中，則讓slack[j]變成原值與A[i]+B[j]-w[i,j]的較小值。這樣，在修改頂標(biāo)時(shí)，取所有不在交錯(cuò)樹中的Y頂點(diǎn)的slack值中的最小值作為d值即可。但還要注意一點(diǎn)：修改頂標(biāo)后，要把所有的slack值都減去d。二分圖最大權(quán)完美匹配KM算法 好吧，這弄點(diǎn)正經(jīng)的。這次就寫寫大家肯定很久以前就搞出來(lái)的KM。我寫這個(gè)是因?yàn)榍皫滋煺砟０宓臅r(shí)候居然發(fā)現(xiàn)我的KM還是O(n^4)的，雖然實(shí)際運(yùn)行效果大部分和O(n^3)差不多，但是理論的上界仍然讓我不爽，就像networksimplexalgorithm一樣。 先說(shuō)一下KM的適用范圍。據(jù)我分析KM實(shí)際
7、上可以對(duì)任意帶權(quán)（無(wú)論正負(fù)權(quán)）二分圖求最大/最小權(quán)完美匹配，唯一的一個(gè)，也是最重要的一個(gè)要求就是這個(gè)匹配必須是完美匹配，否則KM的正確性將無(wú)法得到保證。這個(gè)當(dāng)了解了KM的正確性證明之后自然就會(huì)知道。非完美的匹配的似乎必須祭出mincostmaxflow了?！ ∪缓缶褪荎M的時(shí)間界。這里略去KM的步驟不談。眾所周知，KM弄不好就會(huì)寫出O(n^4)的算法，而實(shí)際上是存在O(n^3)的實(shí)現(xiàn)的。那么O(n^4)究竟是慢在什么地方呢？這個(gè)就需要搞清楚O(n^4)的4究竟是怎么來(lái)的。 每個(gè)點(diǎn)都需要作一次增廣，所以有一個(gè)n的循環(huán)。每個(gè)循環(huán)內(nèi)部，每次可能無(wú)法得到一條增廣路，需要新加入一個(gè)y頂
8、點(diǎn)，然后重新尋找增廣路。一次最少加進(jìn)1個(gè)點(diǎn)，所以最多加入n次。每次重新找一遍增廣路n^2，更新距離標(biāo)號(hào)需要掃描每一條邊n^2，所以迭加起來(lái)O(n)*O(n)*O(n^2)，結(jié)果自然就是O(n^4)?！ 〉谝粚雍偷诙友h(huán)似乎沒(méi)有很好的方法可以把它搞掉，所以我們只能從第三層，也就是每次的O(n^2)入手。這一層包括兩個(gè)部分，一個(gè)是增廣路的n^2，一個(gè)是更新標(biāo)號(hào)的n^2，需要將二者同時(shí)搞掉才能降低總共的復(fù)雜度。注意更新標(biāo)號(hào)之后有一個(gè)最重要的性質(zhì)，那就是原來(lái)存在的合法邊仍然合法，更新只是將不合法的
