1、前言
學(xué)習(xí)是一個(gè)痛苦的過程氓鄙，讓我們養(yǎng)成了不求甚解的習(xí)慣馆揉。
2、匈牙利算法
嗯抖拦，首先網(wǎng)上已經(jīng)有很多啦升酣。但是我覺得很多還是摳不清楚細(xì)節(jié)，于是就有了這篇文章态罪。 匹配就是一種兩兩不相接的邊的集合噩茄，二分匹配就是二分圖的匹配，匈牙利的基礎(chǔ)可以隨便看一篇复颈。
bool find(int x){
int i,j;
for (j=1;j<=m;j++){ //掃描每個(gè)妹子
if (line[x][j]==true && used[j]==false)
//如果有曖昧并且還沒有標(biāo)記過(這里標(biāo)記的意思是這次查找曾試圖改變過該妹子的歸屬問題绩聘，但是沒有成功，所以就不用瞎費(fèi)工夫了）
{
used[j]=1;
if (girl[j]==0 || find(girl[j])) {
//名花無(wú)主或者能騰出個(gè)位置來(lái)耗啦，這里使用遞歸
girl[j]=x;
return true;
}
}
}
return false;
}
int match ()
{
int all = 0;
for (i=1;i<=n;i++)
{
memset(used,0,sizeof(used)); //這個(gè)在每一步中清空
if find(i) all+=1;
}
return all;
}
以上代碼是我從一篇的鏈接中拿過來(lái)的凿菩，line數(shù)組存的是二分圖<X,Y>的邊權(quán)，不難證明從X中一個(gè)點(diǎn)x出發(fā)若匹配的數(shù)量增加帜讲，等價(jià)于存在一條從x出發(fā)的增廣路衅谷。算法的思想就是對(duì)X中每個(gè)點(diǎn)通過find來(lái)深搜增廣路。由于每次只會(huì)遞歸used為0的點(diǎn)似将。所以遞歸深度為O(n)获黔，find的復(fù)雜度是O(n2)蚀苛，整個(gè)算法的復(fù)雜度是O(n3)。
嗯肢执，到這里沒什么問題枉阵，一般的blog討論到這里也結(jié)束了。但是當(dāng)你仔細(xì)看find预茄，會(huì)發(fā)現(xiàn)這個(gè)函數(shù)好像跟我們平時(shí)的搜索不太一樣兴溜。
bool find(int x){
int i,j;
for (j=1;j<=m;j++){
if (line[x][j]==true && used[j]==false)
{
used[j]=1;
if (girl[j]==0 || find(girl[j])) {
girl[j]=x;
return true;
}
//used[j]=0; 平時(shí)這里要將賦值過得used還原。
}
}
return false;
}
平時(shí)搜索失敗的時(shí)候是需要把上下文還原的耻陕，也就是去掉注釋拙徽。然而一旦去掉注釋，這將是一個(gè)指數(shù)復(fù)雜度的搜索算法诗宣。于是我們有理由相信膘怕，不需要還原used恰恰是匈牙利算法對(duì)搜索的一種優(yōu)化，而為什么可以這樣優(yōu)化召庞，這種正確性則是我們需要證明的事岛心，也是該算法的精髓。
我們考慮一個(gè)去掉上述注釋的find函數(shù)篮灼，此時(shí)就是普通的搜索忘古，這樣算法肯定是對(duì)的，接下來(lái)我們要證明這樣搜索的結(jié)果與注釋時(shí)是一樣的诅诱。
我們要解決的問題是<X,Y>的二分圖中髓堪，已經(jīng)used的部分組成的集合稱作前綴。初始時(shí)前綴為空集娘荡。從X中一個(gè)點(diǎn)x0出發(fā)在圖中找增廣路徑干旁，查找所有邊，若對(duì)應(yīng)的y之前未匹配則直接返回找到解炮沐。否則將y加入前綴争群，并從y之前匹配的點(diǎn)開始繼續(xù)搜索，搜索成功則直接返回答案大年，否則將該點(diǎn)剔除前綴换薄。
不難發(fā)現(xiàn)以下結(jié)論。
- 在搜索過程中鲜戒，除了找到增廣路結(jié)束搜索专控。否則每個(gè)匹配的Y中的點(diǎn)都對(duì)應(yīng)同一個(gè)X中的點(diǎn)。
- 若從一個(gè)前綴為S時(shí)從x出發(fā)搜索失敗遏餐，則前綴為S超集時(shí)從x出發(fā)也搜索失敗伦腐。
以上發(fā)現(xiàn)比較顯然，就不證明啦失都。
定理1 若從一個(gè)前綴為S時(shí)搜索到y(tǒng)時(shí)繼續(xù)搜索失敗柏蘑，則前綴為S超集時(shí)搜索到y(tǒng)繼續(xù)搜索也失敗幸冻。
證明：由搜索失敗知y肯定有匹配的點(diǎn)。由結(jié)論1知道在搜索成功前y匹配的點(diǎn)始終不會(huì)變化咳焚。再根據(jù)結(jié)論2可證明洽损。
定義1 在前綴S時(shí)從x出發(fā)搜索和前綴T時(shí)從x出發(fā)搜索時(shí)都有解或者都無(wú)解，則稱S和T在x處前綴等價(jià)革半。
定理2 前綴S和前綴T在x處等價(jià)碑定，前綴T和前綴P在x處等價(jià)，則前綴S和前綴P在x處等價(jià)又官。
證明：由 定義1知延刘，顯然。
定理3 前綴S和前綴T在x處等價(jià)六敬，若P是前綴S的超集碘赖，T是P的超集。則前綴S和前綴P在x處等價(jià)外构，前綴T和前綴P在x處等價(jià)普泡。
證明：
前綴S與前綴T在x處等價(jià)，知前綴S和前綴T在x處搜索都有解或者都無(wú)解审编。
若前綴T和前綴S在x處有解撼班，則由結(jié)論2的逆否命題及前綴T在x處有解知前綴P在x處有解。
若前綴T和前綴S在x處無(wú)解割笙，則由結(jié)論2及前綴S在x處無(wú)解知前綴P在x處無(wú)解权烧。
綜上所述眯亦，則前綴S和前綴P在x處等價(jià)伤溉，前綴T和前綴P在x處等價(jià)。
定理4 在前綴集合S時(shí)從y的匹配搜索時(shí)妻率，設(shè)所有前綴S從y的匹配出發(fā)訪問過的搜索失敗的點(diǎn)為Q乱顾，則S和S并Q在y的匹配處前綴等價(jià)。
證明：由于還在搜索宫静，所以目前的匹配都是失敗的走净。設(shè)從前綴S開始從y的匹配訪問過的點(diǎn)Q中，設(shè)至少一次在第k次遞歸中出現(xiàn)時(shí)的點(diǎn)的集合為C(k)孤里。
Q = C(0) 并 C(1) 并 C(2) ...
下面用數(shù)學(xué)歸納法證明S和S并C(0)并C(1)...并C(n)在y處前綴等價(jià)伏伯。
對(duì)于C(0)中任意一個(gè)點(diǎn)y0，由于S并{y0}在y0處無(wú)解捌袜，則S并{y0}的超集在y0處也無(wú)解说搅。所以y0出現(xiàn)在之后搜索的任何位置，從那里搜索必然無(wú)解虏等。這相當(dāng)于C(0)中任意一個(gè)點(diǎn)在之后被搜索到都將得不到解弄唧，則S并C(0)和S在y處前綴等價(jià)适肠。
設(shè)n=k時(shí)，S和S并C(0)并C(1)...并C(k)在y處等價(jià)候引。
n=k+1是侯养，設(shè)D=S并C(0)并C(1)...并C(k)。以前綴D從y的匹配開始搜索澄干。由于C(k+1)中的點(diǎn)都可以從C(k)中走過來(lái)且都失敗了逛揩，因此若是從其他地方搜索到C(k+1)必然是D的超集由結(jié)論2也會(huì)失敗。故前綴D和D并C(k+1)在y匹配處前綴等價(jià)麸俘，又S和D在y匹配處前綴等價(jià)息尺。由定理2知S和D并C(k+1)在y匹配處前綴等價(jià)，即S和S并C(0)并C(1)...并C(k)并C(k+1)在y匹配處前綴等價(jià)疾掰。
由于搜索是有限的搂誉，我們知道存在m使得k>m時(shí)C(k)為空集。
Q = C(0) 并 C(1) 并 C(2) ... 并C(m)静檬。
S并C(0)并C(1)...并C(m)和S在y處等價(jià)炭懊，有S并Q和S在y處前綴等價(jià)。
定理5 在前綴集合S時(shí)從y的匹配搜索時(shí)拂檩，設(shè)所有由深搜訪問過的搜索失敗的點(diǎn)的集合為Q侮腹，則S和S并Q在y的匹配處前綴等價(jià)。
證明：顯然稻励，任何一個(gè)訪問過的點(diǎn)父阻，一定是由到y(tǒng)的過程中某個(gè)階段失敗的。由定理4望抽，可以把當(dāng)時(shí)的前綴替換為前綴并上該前綴起搜索失敗點(diǎn)的集合加矛。這些所有階段的并集是Q。則到y(tǒng)時(shí)前綴可以替換為S并Q煤篙。得證斟览。
由定理5知可以把之前訪問過的點(diǎn)并入前綴，即used辑奈。所以加不加注釋苛茂，搜索出來(lái)的結(jié)果是一樣的。
3鸠窗、KM算法
KM算法的話妓羊，就是二分圖的匹配帶權(quán)，特別注意不是求數(shù)量最多的匹配稍计，而是求匹配中權(quán)和最大的匹配躁绸。網(wǎng)上很多O(n^4)實(shí)現(xiàn)。這里有一個(gè)比較好的O(n^3)實(shí)現(xiàn)。
KM算法的圖使用鄰接矩陣來(lái)表示涨颜，沒有邊的點(diǎn)之間加一個(gè)權(quán)值為0的邊费韭。這樣可以保證無(wú)論怎么連都存在完美匹配。然后通過給二分圖的兩邊的點(diǎn)頂標(biāo)庭瑰，維護(hù)每條邊的權(quán)值都小于兩邊的頂標(biāo)和星持，對(duì)于一個(gè)完備匹配，若每條邊的權(quán)值等于兩個(gè)點(diǎn)的頂標(biāo)和弹灭，則一定是最大權(quán)匹配督暂。因?yàn)樵摍?quán)和等于所有頂標(biāo)和，若存在更大的權(quán)匹配穷吮，則與每條邊的權(quán)值都小于兩邊的頂標(biāo)和矛盾逻翁。算法的具體細(xì)節(jié)在鏈接里已經(jīng)講得比較清楚啦。
下面講一些KM的討論捡鱼，若邊有負(fù)權(quán)八回，算法仍然成立。情況與加好零邊后給所有的邊加上最小負(fù)數(shù)的絕對(duì)值再跑算法一直驾诈。因?yàn)橐欢ㄓ型昝榔ヅ洳纾喑鰜?lái)的值是固定的。
若二分圖兩邊點(diǎn)的個(gè)數(shù)不相等乍迄，這樣匹配就不能覆蓋所有頂標(biāo)管引，二分圖的正確性不能保證，因此KM算法只能解決二分圖兩邊點(diǎn)數(shù)相等的情況闯两。
