二分圖匹配歸納.doc

這幾天斷斷續(xù)續(xù)學(xué)了二分圖的匹配算法,學(xué)會了二分圖的最大匹配的hungary算法和求二分圖的最佳匹配的KM算法.二分圖是這樣一個圖，它的頂點可以分類兩個集合X和Y，所有的邊關(guān)聯(lián)在兩個頂點中，恰好一個屬于集合，另一個屬于集合。hungary算法就是一個不斷找增廣軌的過程.下面是網(wǎng)上找到的一個比較好的解釋,很容易理解,結(jié)合程序就能掌握算法的思想了:算法的思路是不停的找增廣軌,并增加匹配的個數(shù),增廣軌顧名思義是指一條可以使匹配數(shù)變多的路徑,在匹配問題中,增廣軌的表現(xiàn)形式是一條交錯軌,也就是說這條由圖的邊組成的路徑,它的第一條邊是目前還沒有參與匹配的,第二條邊參與了匹配,第三條邊沒有.最后一條邊沒有參與匹配,并且始點和終點還沒有被選擇過.這樣交錯進(jìn)行,顯然他有奇數(shù)條邊.那么對于這樣一條路徑,我們可以將第一條邊改為已匹配,第二條邊改為未匹配.以此類推.也就是將所有的邊進(jìn)行反色,容易發(fā)現(xiàn)這樣修改以后,匹配仍然是合法的,但是匹配數(shù)增加了一對.另外,單獨的一條連接兩個未匹配點的邊顯然也是交錯軌.可以證明,當(dāng)不能再找到增廣軌時,就得到了一個最大匹配.這也就是匈牙利算法的思路.hungary算法適合解決的問題:1.最大匹配(=,=顯然.)2.完美匹配3.點覆蓋(最小覆蓋問題)4.最小路徑覆蓋5.最大獨立集問題參考網(wǎng)上的代碼寫的一個算法,好像用的人蠻多的#define N 100int bmNN,linkN,vN;int n,m;int path(int t) int i; for(i=1;i=m;i+) if(!vi & bmti) vi=1; if(!linki | path(linki) linki=t; return 1; return 0;int maxmatch() int i,c=0; memset(link,0,sizeof(link); for(i=1;i=n;i+) memset(v,0,sizeof(v); if(path(i) c+; return c;二分圖的最佳匹配:算法是理解了,可是定理沒有證明=,=.哎,這就是工科生和理科生的區(qū)別.【最優(yōu)完備匹配】對于二分圖的每條邊都有一個權(quán)（非負(fù)），要求一種完備匹配方案，使得所有匹配邊的權(quán)和最大，記做最優(yōu)完備匹配。（特殊的，當(dāng)所有邊的權(quán)為1時，就是最大完備匹配問題）KM算法：（全稱是Kuhn-Munkras，是這兩個人在1957年提出的，有趣的是，匈牙利算法是在1965年提出的）為每個點設(shè)立一個頂標(biāo)Li，先不要去管它的意義。設(shè)vi,j為(i,j)邊的權(quán)，如果可以求得一個完備匹配，使得每條匹配邊vi,j=Li+Lj，其余邊vi,jLi+Lj。此時的解就是最優(yōu)的，因為匹配邊的權(quán)和=Li，其余任意解的權(quán)和都不可能比這個大定理：二分圖中所有vi,j=Li+Lj的邊構(gòu)成一個子圖G，用匈牙利算法求G中的最大匹配，如果該匹配是完備匹配，則是最優(yōu)完備匹配。（不知道怎么證明）問題是，現(xiàn)在連Li的意義還不清楚。其實，我們現(xiàn)在要求的就是L的值，使得在該L值下達(dá)到最優(yōu)完備匹配。L初始化：Li=maxwi,j(ix,jy)Lj=0建立子圖G，用匈牙利算法求G的最大匹配，如果在某點i (ix)找不到增廣軌，則得不到完備匹配。此時需要對L做一些調(diào)整：設(shè)S為尋找從i出發(fā)的增廣軌時訪問的x中的點的集合，T為訪問的y中的點的集合。找到一個改進(jìn)量dx，dx=minLi+Lj-wi,j(iS,j不T)Li=Li-dx (iS)Li=Li+dx (iT)重復(fù)以上過程，不斷的調(diào)整L，直到求出完備匹配為止。從調(diào)整過程中可以看出：每次調(diào)整后新子圖中在包含原子圖中所有的邊的基礎(chǔ)上添加了一些新邊。每次調(diào)整后Li會減少dx，由于每次dx取最小，所以保證了解的最優(yōu)性。復(fù)雜度分析：設(shè)n為點數(shù)，m為邊數(shù)，從每個點出發(fā)尋找增廣軌的復(fù)雜度是O(m)，如果找不到增廣軌，對L做調(diào)整的復(fù)雜度也是O(m)，而一次調(diào)整或者找到一條增廣軌，或者將兩個連通分量合成一個，而這兩種情況最多都只進(jìn)行O(n)次，所以總的復(fù)雜度是O(nm)擴展：根據(jù)KM算法的實質(zhì)，可以求出使得所有匹配邊的權(quán)和最小的匹配方案。L初始化：Li=minwi,j(ix,jy)Lj=0dx=minwi,j-Li-Lj(iS,j不T)Li=Li+dx (iS)Li=Li-dx (iT)【最優(yōu)匹配】與最優(yōu)完備匹配很相似，但不必以完備匹配為前提。只要對KM算法作一些修改就可以了：將原圖轉(zhuǎn)換成完全二分圖（m=|x|y|），添加原圖中不存在的邊，并且設(shè)該邊的權(quán)值為0。也是借用了別人的模板,我認(rèn)為時間效率還不錯自己稍加修改在用,等以后自己寫個.int path(int u)sxu=1;int v;for(v=0;vn;v+) if(!syv&lxu+lyv=wuv) syv=1; if(linkv=-1 | path(linkv) linkv=u; return 1; return 0;int maxmatch(int maxsum) int i,j,u;if(!maxsum) for(i=0;in;i+) for(j=0;jn;j+) wij=-wij;for(i=0;in;i+) lxi=-0x1fffffff; lyi=0; for(j=0;jn;j+) if(lxiwij) lxi=wij;memset(link,-1,sizeof(link);for(u=0;un;u+) while(1) memset(sx,0,sizeof(sx); memset(sy,0,sizeof(sy); if(path(u) break; int dx=0x7fffffff; for(i=0;in;i+) if(sxi) for(j=0;jn;j+) if(!syj) dx=min(lxi+lyj-wij,dx); for(i=0;in;i+) if(sxi) lxi-=dx; if(syi) lyi+=dx; int sum=0;for(i=0;in;i+) sum+=wlinkii;if(!maxsum) sum=-sum; for(i=0;in;i+) for(j=0;jn;j+) wij=-wij;return sum;至于一般圖的最優(yōu)匹配,還沒遇到過這樣的題.不是很想寫(我真阿Q.),等以后再perfect一下吧那,就這樣了.拖了幾天的集訓(xùn)明天正式開始了,說實話,有點緊張-實在是太挫了點啊.要好好奮斗了,不然什么資本都沒了.緊張之余也有期待,mmd說會安排老隊員講課,之前發(fā)在bbs上的論文我都下下