二分圖匹配歸納.doc

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