二分圖最大匹配及常用建圖方法

《二分圖最大匹配及常用建圖方法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、算法———藝術(shù)二分圖匹配剖析很多人說，算法是一種藝術(shù)。但是對(duì)于初學(xué)者的我，對(duì)算法認(rèn)識(shí)不是很深刻，但偶爾也能感受到他強(qiáng)大的魅力與活力。這讓我追求算法的腳步不能停止。下面我通過分析匈牙利算法以及常用建圖方式，與大家一起欣賞算法的美。匈牙利算法匈牙利算法是用來解決最大二分圖匹配問題的，所謂二分圖即“一組點(diǎn)集可以分為兩部分，且每部分內(nèi)各點(diǎn)互不相連，兩部分的點(diǎn)之間可以有邊”。所謂最大二分圖匹配即”對(duì)于二分圖的所有邊，尋找一個(gè)子集，這個(gè)子集滿足兩個(gè)條件，1：任意兩條邊都不依賴于同一個(gè)點(diǎn)。2：讓這個(gè)子集里的邊在滿足條件一的情況下盡量多。首先可以想到的

2、是，我們可以通過搜索，找出所有的這樣的滿足上面條件的邊集，然后從所有的邊集中選出邊數(shù)最多的那個(gè)集合，但是我們可以感覺到這個(gè)算法的時(shí)間復(fù)雜度是邊數(shù)的指數(shù)級(jí)函數(shù)，因此我們有必要尋找更加高效的方法。目前比較有效的方法有匈牙利算法和通過添加匯點(diǎn)和源點(diǎn)的網(wǎng)絡(luò)流算法，對(duì)于點(diǎn)的個(gè)數(shù)都在200到300之間的數(shù)據(jù)，我們是采取匈牙利算法的，因?yàn)樾傺览惴▽?shí)現(xiàn)起來要比網(wǎng)絡(luò)流簡(jiǎn)單些。下面具體說說匈牙利算法：介紹匈牙利之前，先說說“增廣軌”。定義：若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬最大匹配邊集M的邊和不屬M(fèi)的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)

3、，則稱P為相對(duì)于M的一條增廣軌定義總是抽象的下面通過圖來理解它。圖中的線段（2->3,3->1,1->4）便是上面所說的p路徑，我們假定邊（1,3）是以匹配的邊，（2,3）（1,4）是未匹配的邊，則邊（4,1）邊（1,3）和邊（3,2）在路徑p上交替的出現(xiàn)啦，那么p就是相對(duì)于M的一條增廣軌，這樣我們就可以用邊1,4和邊2,3來替換邊1,3那么以匹配的邊集數(shù)量就可以加1,。匈牙利算法就是同過不斷的尋找增廣軌實(shí)現(xiàn)的。很明顯如果二分圖的兩部分點(diǎn)分別為n和m，那么最大匹配的數(shù)目應(yīng)該小于等于MIN（n,m）;因此我們可以枚舉任第一部分（的二部分也

4、可以）里的每一個(gè)點(diǎn)，我們從每個(gè)點(diǎn)出發(fā)尋找增廣軌，最后吧第一部分的點(diǎn)找完以后，就找到了最大匹配的數(shù)目，當(dāng)然我們也可以通過記錄找出這些邊。下面給出關(guān)于二分圖最大匹配的兩個(gè)定理1:最大匹配數(shù)+最大獨(dú)立集=n+m2:二分圖的最小覆蓋數(shù)=最大匹配數(shù)3:最小路徑覆蓋=最大獨(dú)立集最大獨(dú)立集是指求一個(gè)二分圖中最大的一個(gè)點(diǎn)集，該點(diǎn)集內(nèi)的點(diǎn)互不相連。最小頂點(diǎn)覆蓋是指在二分圖中，用最少的點(diǎn)，讓所有的邊至少和一個(gè)點(diǎn)有關(guān)聯(lián)。最小路徑覆蓋是指一個(gè)不含圈的有向圖G中，G的一個(gè)路徑覆蓋是一個(gè)其結(jié)點(diǎn)不相交的路徑集合P，圖中的每一個(gè)結(jié)點(diǎn)僅包含于P中的某一條路徑。路徑可以從

5、任意結(jié)點(diǎn)開始和結(jié)束，且長(zhǎng)度也為任意值，包括0下面給出二分圖最大匹配的偽代碼：/*use[i]數(shù)組時(shí)標(biāo)記第二部分點(diǎn)中的第j個(gè)點(diǎn)是否使用過。match[i]與第二部分中的點(diǎn)i匹配的點(diǎn)是match[i]*/IntGetAugmentPath(number)//通過number這個(gè)點(diǎn)尋找增廣軌，找到返回1找不到返回0；P?related[number].next;//與number相連的點(diǎn)；While（p!=NULL）{Ifnotused[p]then//p點(diǎn)沒有被使用過Ifmatch[p]==0orGetAugmentPath(match[p

6、])//p點(diǎn)沒有和另一部分的點(diǎn)配對(duì)//或和p配對(duì)的那個(gè)點(diǎn)可以找到其它點(diǎn)和他配對(duì)（找到增廣軌）Return1;p?p.next//與number相連的下幾個(gè)點(diǎn)}Return0;}endGetAugmentPath;我們只需要在主程序中對(duì)某一部分點(diǎn)集的每個(gè)點(diǎn)進(jìn)行增廣軌的尋找；Intmain{ans?0ForI=1àn//枚舉第一部分的n個(gè)點(diǎn)；Forj=1àmuse[j]?false//把第二部分的m個(gè)點(diǎn)表示為沒有使用過。ifGetAugmentPath(i)thenans?ans+1//找到增廣軌就給邊數(shù)加一；}程序非常好寫，也非常好懂。1

7、23456712345678每次我們從上面的第i個(gè)點(diǎn)出發(fā)盡量去找一個(gè)能唯一和它匹配的點(diǎn)p，策略有兩種，一是直接在下面的點(diǎn)中找到一個(gè)點(diǎn)p，他沒有和上面的點(diǎn)匹配過（即match[p]=0）。二是當(dāng)p和上面的某個(gè)點(diǎn)匹配過，即（match[p]）那么我們就從match[p]出發(fā)，去給他找下面另外的點(diǎn)和他匹配，把p點(diǎn)留給點(diǎn)i。這樣我們不就多找到了一條？然而對(duì)于匈牙利算法來說，難點(diǎn)并不在與程序本身，而是在如何把實(shí)際問題轉(zhuǎn)化為最大二分圖匹配的模型，然后再利用匈牙利算法解決。下面我們說幾種常見的建圖模型。常見建圖模型法一行列匹配法101010100上圖

8、是一個(gè)3*3的矩陣，方格內(nèi)的1表示這個(gè)地方有敵人，0表示沒有敵人，現(xiàn)在我們有很多箭，每根箭可以殺死一行或者一列的敵人，問題是，我們要?dú)⑺浪械臄橙酥烈玫綆赘砍蹩此坪鹾妥畲蠖謭D沒有什么相關(guān)聯(lián)的，然而如