二分圖匹配基于匈牙利算法和KM算法.doc

《二分圖匹配基于匈牙利算法和KM算法.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、二分圖匹配----基于匈牙利算法和KM算法2007-09-1916:54設(shè)G=(V,{R})是一個(gè)無向圖。如頂點(diǎn)集V可分割為兩個(gè)互不相交的子集，并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬兩個(gè)不同的子集。則稱圖G為二分圖。v??????給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。v??????選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題(maximalmatchingproblem)v??????如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。最大匹配在

2、實(shí)際中有廣泛的用處，求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個(gè)算法的復(fù)雜度為邊數(shù)的指數(shù)級函數(shù)。因此，需要尋求一種更加高效的算法。匈牙利算法是求解最大匹配的有效算法，該算法用到了增廣路的定義(也稱增廣軌或交錯(cuò)軌)：若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬M(fèi)的邊和不屬M(fèi)的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對于M的一條增廣路徑。由增廣路徑的定義可以推出下述三個(gè)結(jié)論：v??????1.P的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。v??????2.P經(jīng)過取反操作（即非M中的邊變?yōu)镸

3、中的邊，原來M中的邊去掉）可以得到一個(gè)更大的匹配M’。v??????3.M為G的最大匹配當(dāng)且僅當(dāng)不存在相對于M的增廣路徑。從而可以得到求解最大匹配的匈牙利算法：v??????(1)置M為空v??????(2)找出一條增廣路徑P，通過取反操作獲得更大的匹配M’代替Mv??????(3)重復(fù)(2)操作直到找不出增廣路徑為止根據(jù)該算法，我選用dfs(深度優(yōu)先搜索)實(shí)現(xiàn)。程序清單如下：intmatch[i]//存儲集合m中的節(jié)點(diǎn)i在集合n中的匹配節(jié)點(diǎn),初值為-1。intn,m,match[100];?????????????????????//二分圖的兩

4、個(gè)集合分別含有n和m個(gè)元素。boolvisit[100],map[100][100];??????????????//map存儲鄰接矩陣。booldfs(intk){intt;for(inti=0;i

5、

6、dfs(t))//尋找是否為增廣路徑??????returntrue;???

7、??match[i]=t;}????returnfalse;}intmain(){//...........????int???s=0;????memset(match,-1,sizeof(match));????for(i=0;i

8、權(quán)（非負(fù)），要求一種完備匹配方案，使得所有匹配邊的權(quán)和最大，記做最優(yōu)完備匹配。（特殊的，當(dāng)所有邊的權(quán)為1時(shí)，就是最大完備匹配問題）解二分圖最優(yōu)匹配問題可用窮舉的方法，但窮舉的效率=n！，所以我們需要更加優(yōu)秀的算法。先說一個(gè)定理：設(shè)M是一個(gè)帶權(quán)完全二分圖G的一個(gè)完備匹配，給每個(gè)頂點(diǎn)一個(gè)可行頂標(biāo)(第i個(gè)x頂點(diǎn)的可行標(biāo)用lx[i]表示，第j個(gè)y頂點(diǎn)的可行標(biāo)用ly[j]表示)，如果對所有的邊(i,j)inG,都有l(wèi)x[i]+ly[j]>=w[i,j]成立(w[i,j]表示邊的權(quán))，且對所有的邊(i,j)inM,都有l(wèi)x[i]+ly[j]=w[i,j]成立

9、，則M是圖G的一個(gè)最優(yōu)匹配。Kuhn－Munkras算法（即KM算法）流程：v??????(1)初始化可行頂標(biāo)的值v??????(2)用匈牙利算法尋找完備匹配v??????(3)若未找到完備匹配則修改可行頂標(biāo)的值v??????(4)重復(fù)(2)(3)直到找到相等子圖的完備匹配為止KM算法主要就是控制怎樣修改可行頂標(biāo)的策略使得最終可以達(dá)到一個(gè)完美匹配，首先任意設(shè)置可行頂標(biāo)（如每個(gè)X節(jié)點(diǎn)的可行頂標(biāo)設(shè)為它出發(fā)的所有弧的最大權(quán)，Y節(jié)點(diǎn)的可行頂標(biāo)設(shè)為0），然后在相等子圖中尋找增廣路，找到增廣路就沿著增廣路增廣。而如果沒有找到增廣路呢，那么就考慮所有現(xiàn)在在匈牙

10、利樹中的X節(jié)點(diǎn)（記為S集合），所有現(xiàn)在在匈牙利樹中的Y節(jié)點(diǎn)（記為T集合），考察所有一段在S集合，一段在notT集合中的弧，取??????