信息學(xué)競賽算法分析與設(shè)計

1、1,信息學(xué)競賽——算法分析與設(shè)計,2,本節(jié)課程內(nèi)容,二分圖、匹配(bipartite graph、matching) 匈 牙 利 算 法 Kuhn-Munkras算法,3,二分圖的概念,二分圖又稱作二部圖，是圖論中的一種特殊模型。設(shè)G=(V,{R})是一個無向圖。如頂點集V可分割為兩個互不相交的子集，并且圖中每條邊依附的兩個頂點都分屬兩個不同的子集。則稱圖G為二分圖。,4,最大匹配,給定一個二分圖G，在G的一個子圖M中，M

2、的邊集{E}中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題(maximal matching problem)如果一個匹配子圖中，圖中的每個頂點都和匹配子圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。,5,匈牙利算法,求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個算法的復(fù)雜度為邊數(shù)的指數(shù)級函數(shù)。因此，需要尋求一種更加高效的算法。增廣路的

3、定義(也稱增廣軌或交錯軌)： 若P是圖G中一條連通兩個未匹配頂點的路徑，并且屬M的邊和不屬M的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對于M的一條增廣路徑。,6,匈牙利算法,由增廣路的定義可以推出下述三個結(jié)論：1. P的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。2. P經(jīng)過取反操作可以得到一個更大的匹配M’。3. M為G的最大匹配當(dāng)且僅當(dāng)不存在相對于M的增廣路徑。,7,匈牙利算法,用增廣路

4、求最大匹配(稱作匈牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出)算法輪廓：(1)置M為空(2)找出一條增廣路徑P，通過取反操作獲得更大的匹配M’代替M(3)重復(fù)(2)操作直到找不出增廣路徑為止,8,9,設(shè)G是具有二部劃分(V1,V2)的二分圖.(1)任給初始匹配M;(2)若M飽和V1則結(jié)束.否則轉(zhuǎn)(3);(3)在V1中找一非M飽和點x,置S={x},T=?;(4)若N(S)=T,則停止,否則任選一點y?N(S)-

5、T;(5)若y為M飽和點轉(zhuǎn)(6),否則作求一條從x到y(tǒng)的M可增廣路P,置M=M?P,轉(zhuǎn)(2)(6)由于y是M飽和點,故M中有一邊{y,u},置S=S?{u},T=T?{y},轉(zhuǎn)(4).,匈牙利算法步驟,10,匈牙利算法,程序清單： #include#includebool g[201][201];int n,m,ans;bool b[201];int link[201];,11,匈牙利算法,bool init(

6、){ int _x,_y; memset(g,0,sizeof(g)); memset(link,0,sizeof(link)); ans=0; if(scanf(“%d%d”,&n,&m)==EOF) return false; for(int i=1;i<=n;i++) { scanf(“%d”,&_x); for(int j=0;

7、j<_x;j++) { scanf(“%d”,&_y); g[ i ][_y]=true; } } return true;},12,匈牙利算法,bool find(int a){ for(int i=1;i<=m;i++) { if(g[a][ i ]==1&&!b[ i ])

8、 { b[ i ]=true; if(link[ i ]==0||find(link[ i ])) { link[ i ]=a; return true; } } } return false;},13,匈牙利算法,int main(){while(

9、init()){ for(int i=1;i<=n;i++) { memset(b,0,sizeof(b)); if(find(i)) ans++; }printf("%d\n",ans);}},14,求二部圖G = ( X, Y, E )的(匈牙利算法)迭代步驟:,從G的任意匹配M開始. ① 將X中M的所有非飽和點都給以標(biāo)號

10、0和標(biāo)記*, 轉(zhuǎn)向②. M的非飽和點即非M的某條邊的頂點. ② 若X中所有有標(biāo)號的點都已去掉了標(biāo)記*, 則M是G的最大匹配. 否則任取X中一個既有標(biāo)號又有標(biāo)記*的點xi , 去掉xi的標(biāo)記*, 轉(zhuǎn)向③. ③ 找出在G中所有與xi鄰接的點yj , 若所有這樣的yj都已有標(biāo)號, 則轉(zhuǎn)向②, 否則轉(zhuǎn)向④.,15,④ 對與xi鄰接且尚未給標(biāo)號的yj都給定標(biāo)號i.,若所有的 yj 都是M的飽和點,則轉(zhuǎn)向⑤,否則逆向返回.

11、即由其中M的任一個非飽和點 yj 的標(biāo)號i 找到xi ,再由 xi 的標(biāo)號k 找到 yk ,…,最后由 yt 的標(biāo)號s找到標(biāo)號為0的xs時結(jié)束,獲得M-增廣路xs yt … xi yj , 記P ={xs yt , … , xi yj },重新記M為M⊕P,轉(zhuǎn)向①. 不必理會M-增廣路的定義. M⊕P = M∪P \ M∩P, 是對稱差. ⑤ 將yj在M中與之鄰接的點xk ,給以標(biāo)號 j 和標(biāo)記*, 轉(zhuǎn)向②.,

12、16,例 求下圖所示二部圖G的最大匹配.,解 ① 取初始匹配M0 ={x2 y2 , x3 y3 , x5 y5} (上圖粗線所示). ② 給X中M0的兩個非飽和點x1,x4都給以標(biāo)號0和標(biāo)記* (如下圖所示).,17,② 給X中M0的兩個非飽和點x1,x4都給以標(biāo)號0和標(biāo)記* (如下圖所示). ② 給X中M0的兩個非飽和點x1,x4都給以標(biāo)號0和標(biāo)記* (如下圖所示).,18,③ 去掉x1的標(biāo)記*, 將與x1鄰接的兩個點y

13、2, y3都給以標(biāo)號1. 因為y2, y3都是M0的兩個飽和點,所以將它們在M0中鄰接的兩個點x2, x3都給以相應(yīng)的標(biāo)號和標(biāo)記* (如下圖所示).,19,,④ 去掉x2的標(biāo)記*, 將與x2鄰接且尚未給標(biāo)號的三個點y1, y4, y5都給以標(biāo)號2 (如下圖所示).,20,⑤ 因為y1是M0的非飽和點, 所以順著標(biāo)號逆向返回依次得到x2, y2, 直到x1為0為止.于是得到M0的增廣路x1 y2x2 y1, 記P = {x1 y2 , y

14、2x2 , x2 y1}. 取M1 = M0⊕P = {x1 y2 , x2 y1 , x3 y3 , x5 y5}, 則M1是比M多一邊的匹配(如下圖所示).,21,⑥ 再給X中M1的非飽和點x4給以標(biāo)號0和標(biāo)記*, 然后去掉x4的標(biāo)記*, 將與x4鄰接的兩個點y2, y3都給以標(biāo)號4.,因為y2, y3都是M1的兩個飽和點, 所以將它們在M1中鄰接的兩個點x1, x3都給以相應(yīng)的標(biāo)號和標(biāo)記* (如下圖所示).,22,⑦ 去掉x1的標(biāo)

15、記*, 因為與x1鄰接的兩個點y2, y3都有標(biāo)號4, 所以去掉x3的標(biāo)記*.,而與x3鄰接的兩個點y2, y3也都有標(biāo)號4, 此時X中所有有標(biāo)號的點都已去掉了標(biāo)記*(如下圖所示), 因此M1是G的最大匹配.,G不存在飽和X的每個點的匹配, 當(dāng)然也不存在完美匹配.,23,最佳匹配,如果邊上帶權(quán)的話，找出權(quán)和最大的匹配叫做求最佳匹配。實際模型：某公司有職員x1,x2,…,xn,他們?nèi)プ龉ぷ鱵1,y2,…,yn,每個職員做各項工作的效益未

16、必一致，需要制定一個分工方案，使得人盡其才，讓公司獲得的總效益最大。數(shù)學(xué)模型：G是加權(quán)完全二分圖，求總權(quán)值最大的完備匹配。,24,KM算法,窮舉的效率－n！，需要更加優(yōu)秀的算法。定理： 設(shè)M是一個帶權(quán)完全二分圖G的一個完備匹配，給每個頂點一個可行頂標(biāo)(第i個x頂點的可行標(biāo)用lx[i]表示，第j個y頂點的可行標(biāo)用ly[j]表示)，如果對所有的邊(i,j) in G,都有l(wèi)x[i]+ly[j]>=w[i,j]

17、成立(w[i,j]表示邊的權(quán))，且對所有的邊(i,j) in M,都有l(wèi)x[i]+ly[j]=w[i,j]成立，則M是圖G的一個最佳匹配。,25,KM算法,對于任意的G和M，可行頂標(biāo)都是存在的：l(x) = maxw(x,y)l(y) = 0欲求完全二分圖的最佳匹配，只要用匈牙利算法求其相等子圖的完備匹配；問題是當(dāng)標(biāo)號之后的Gl無完備匹配時怎么辦？1957年Kuhn和Munkras 給出了一個解決該問題的有效算法，用逐次修改可行頂

18、標(biāo)l(v)的辦法使對應(yīng)的相等子圖之最大匹配逐次增廣，最后出現(xiàn)完備匹配。,26,KM算法,修改方法如下：先將一個未被匹配的頂點u(u in {x})做一次增廣路，記下哪些結(jié)點被訪問那些結(jié)點沒有被訪問。求出d=min{lx[i]+ly[j]-w[i,j]}其中i結(jié)點被訪問，j結(jié)點沒有被訪問。然后調(diào)整lx和ly：對于訪問過的x頂點，將它的可行標(biāo)減去d，對于所有訪問過的y頂點，將它的可行標(biāo)增加d。修改后的頂標(biāo)仍是可行頂標(biāo)，原來的匹配M仍然存在

19、，相等子圖中至少出現(xiàn)了一條不屬于M的邊，所以造成M的逐漸增廣。,27,KM算法,上述算法的證明也很容易Kuhn－Munkras算法流程：(1)初始化可行頂標(biāo)的值(2)用匈牙利算法尋找完備匹配(3)若未找到完備匹配則修改可行頂標(biāo)的值(4)重復(fù)(2)(3)直到找到相等子圖的完備匹配為止,28,作業(yè)：,1325 Machine Schedule 2062 Card Game Cheater 2195 Going Home 22

20、26 Muddy Fields,29,附錄：,1 Place the Robots（ZOJ） 2 救護(hù)傷員（TOJ1148）3 打獵4 最小路徑覆蓋5 一些例子6 二部圖相關(guān)的定義、定理,30,例題1 Place the Robots（ZOJ1654）,問題描述 有一個N*M(N,M<=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機(jī)器人只能放在空地上。在同一行或同一列的兩個機(jī)器

21、人，若它們之間沒有墻，則它們可以互相攻擊。問給定的棋盤，最多可以放置多少個機(jī)器人，使它們不能互相攻擊。,31,例題1 Place the Robots（ZOJ）,模型一,于是，問題轉(zhuǎn)化為求圖的最大獨立集問題。,在問題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點，有沖突的空地間連邊，我們可以得到右邊的這個圖：,32,例題1 Place the

22、Robots（ZOJ）,模型一,在問題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點，有沖突的空地間連邊，我們可以得到右邊的這個圖：,這是NP問題！,33,我們將每一行，每一列被墻隔開，且包含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個塊之中，最多只能放一個機(jī)器人。我們把這些塊編上號。,同樣，把豎直方向的塊也編上號。,例題1 Place the Rob

23、ots（ZOJ）,模型二,1,2,3,4,5,34,例題1 Place the Robots（ZOJ）,模型二,1,2,3,4,5,把每個橫向塊看作X部的點，豎向塊看作Y部的點，若兩個塊有公共的空地，則在它們之間連邊。,于是，問題轉(zhuǎn)化成這樣的一個二部圖：,35,由于每條邊表示一個空地，有沖突的空地之間必有公共頂點，所以問題轉(zhuǎn)化為二部圖的最大匹配問題。,例題1 Place the Robots（ZOJ）,模型二,1,2,3,5,4,3

24、6,比較前面的兩個模型：模型一過于簡單，沒有給問題的求解帶來任何便利；模型二則充分抓住了問題的內(nèi)在聯(lián)系，巧妙地建立了二部圖模型。為什么會產(chǎn)生這種截然不同的結(jié)果呢？其一是由于對問題分析的角度不同：模型一以空地為點，模型二以空地為邊；其二是由于對原型中要素的選取有差異：模型一對要素的選取不充分，模型二則保留了原型中“棋盤”這個重要的性質(zhì)。由此可見，對要素的選取，是圖論建模中至關(guān)重要的一步。,例題1 Place the Robots（ZOJ

25、）,小結(jié),37,例題2 救護(hù)傷員（TOJ1148）,無情的海嘯奪取了無數(shù)人的生命.很多的醫(yī)療隊被派往災(zāi)區(qū)拯救傷員.就在此時,醫(yī)療隊突然發(fā)現(xiàn)自己帶的藥品已經(jīng)不夠用了,只剩下了N種。(1 < n <= 20)，隨著病人病情的發(fā)展，每種藥在每天能獲得的效果是不一樣的。同時，每天病人只能服用一種藥。也就是說，這些藥還夠支持N天。現(xiàn)在，給出你每種藥在每天使用的效果，請你判斷當(dāng)每種藥都用完后所有藥達(dá)到的效果之和最大可以是多少。,38,

26、例題3 打獵,獵人要在n*n的格子里打鳥，他可以在某一行中打一槍，這樣此行中的所有鳥都被打掉，也可以在某一列中打，這樣此列中的所有鳥都打掉。問至少打幾槍，才能打光所有的鳥？建圖：二分圖的X部為每一行，Y部為每一列，如果(i,j)有一只鳥，那么連接X部的i與Y部的j。該二分圖的最大匹配數(shù)則是最少要打的槍數(shù)。,39,例題4 最小路徑覆蓋,一個不含圈的有向圖G中，G的一個路徑覆蓋是一個其結(jié)點不相交的路徑集合P，圖中的每一個結(jié)點僅包含于P

27、中的某一條路徑。路徑可以從任意結(jié)點開始和結(jié)束，且長度也為任意值，包括0。請你求任意一個不含圈的有向圖G的最小路徑覆蓋數(shù)。理清一個關(guān)系：最小路徑覆蓋數(shù)＝G的結(jié)點數(shù)－最小路徑覆蓋中的邊數(shù),40,例題4 最小路徑覆蓋,試想我們應(yīng)該使得最小路徑覆蓋中的邊數(shù)盡量多，但是又不能讓兩條邊在同一個頂點相交。拆點：將每一個頂點i拆成兩個頂點Xi和Yi。然后根據(jù)原圖中邊的信息，從X部往Y部引邊。所有邊的方向都是由X部到Y(jié)部。,41,例題4 最小路徑覆蓋

28、,因此，所轉(zhuǎn)化出的二分圖的最大匹配數(shù)則是原圖G中最小路徑覆蓋上的邊數(shù)。因此由最小路徑覆蓋數(shù)＝原圖G的頂點數(shù)－二分圖的最大匹配數(shù)便可以得解。,42,例1 m項工作準(zhǔn)備分給n個人去做，如圖，其中邊（xi,yj)表示xi,可以從事yj ，如果每個人最多從事其中一項，且每項工作只能由一人擔(dān)任。問怎樣才能使盡可能多的人安派上任務(wù)。,,,二分圖，如xj從事了yi就不能從事yk,同時yi也不允許其它人擔(dān)任。相當(dāng)于用一種顏色，例如紅色，對G的邊著色，

29、保證每個結(jié)點最多與一條紅色邊相聯(lián)，這種紅色邊的集合記為M它是圖G的一個匹配。計算G中邊數(shù)最多的匹配。,43,例2 二次大站期間，許多盟軍飛行員到英國參加對法西斯的空襲，當(dāng)時每架飛機(jī)需領(lǐng)航員和飛行員各一名。其中有些只能領(lǐng)航，有些只能駕駛，也有人二者均會。加之二人語言要求相通，如果以結(jié)點表示人，邊表示二人語言相通并且一人可領(lǐng)航，另一人可駕駛一可得一圖，這是一簡單圖那么最多的編隊方案就是求成過急G的一個最大匹配。,44,例.有n張紙牌,每張

30、紙牌的正反兩面都寫上1,2,…n的某一個數(shù),證明:如果每個數(shù)字恰好出現(xiàn)兩次,則這些紙牌一定可以這樣攤開,使朝上的面中1,2,…n都出現(xiàn).,45,例 某工廠生產(chǎn)由6種不同顏色的紗織成的布，由這個工廠生產(chǎn)的雙色布中每一種顏色至少和其它三種顏色搭配。證明可以挑選出三種不同的雙色布，他們含有所有的6種顏色。,46,二部圖： 一些例子,作者-文章(author-literature)演員-電影(actor-film)基因-疾病(gene

31、-disease)藥物-靶標(biāo)(drug-protein target)基礎(chǔ)醫(yī)學(xué)和臨床中的數(shù)據(jù)？。。。。。。。。,47,相關(guān)定義、定理,定理1： 簡單圖G為二部圖?G中所有基本回路的長度為偶數(shù)。定義1：設(shè)無向圖G＝，M?E，若M中任意兩條邊都不相鄰，則稱M為G的一個匹配，并把M中的邊所關(guān)聯(lián)的兩個結(jié)點稱為在M下是匹配的。若在M中再加入任何一條邊就不是匹配了，稱M為極大匹配。邊數(shù)最多的極大匹配稱為G的最大匹配。最大匹配中的邊的個數(shù)稱為

32、G的匹配數(shù)。 M是G中的一個匹配，若結(jié)點v與M中的邊關(guān)聯(lián)，稱v為M飽和點，否則稱v為M非飽和點。若G中每個結(jié)點都是M飽和點，稱M是完全匹配。,48,,定義2 ：設(shè)G＝為二部圖，M是G中一個最大匹配，若|M|＝min{|V1|，|V2|}，稱M為G中的一個完備匹配。若此時|V1|?|V2|，稱M為V1到V2的一個完備匹配。若|V1|＝|V2|，稱M為G的完全匹配。定理3(Hall定理)：設(shè)G＝，|V1|?|V2|，G中存

33、在從V1到V2的完備匹配?V1中任意k個結(jié)點(k＝1，2，…，|V1|)至少鄰接V2中的k個結(jié)點。,49,,定理4 (t條件)：設(shè)G＝，若V1中每個結(jié)點至少關(guān)聯(lián)t(t＞0)條邊，而V2中每個結(jié)點至多關(guān)聯(lián)t條邊，則G中存在V1到V2的完備匹配。推論：G＝，對任意v∈V1或V2有d(v)＝k＞0，則G有一個完全匹配。,50,例：某大學(xué)計算機(jī)系有3個課外學(xué)習(xí)小組：網(wǎng)絡(luò)組、網(wǎng)頁制作組和數(shù)據(jù)庫組。今有張、王、李、趙、陳5名同學(xué)。若已知：

34、 (1)張、王為網(wǎng)絡(luò)組成員，張、李、趙為網(wǎng)頁制作組成員，李、趙、陳為數(shù)據(jù)庫組成員； (2)張為網(wǎng)絡(luò)組成員，王、李、趙為網(wǎng)頁制作組成員，王、李、趙、陳為數(shù)據(jù)庫組成員； (3)張為網(wǎng)絡(luò)組和網(wǎng)頁制作組成員，王、李、趙、陳為數(shù)據(jù)庫組成員。 問以上3種情況下能否各選出3名不兼職的組長？,51,例 某中學(xué)有3個課外小組:物理組、化學(xué)組、生物組.今有張、王、李、趙、陳5名同學(xué).若已知: (1)

35、張、王為物理組成員,張、李、趙為化學(xué)組成員,李、趙、陳為生物組成員; (2)張為物理組成員,王、李、趙為化學(xué)組成員,王、李、趙、陳為生物組成員; (3)張為物理組和化學(xué)組成員,王、李、趙、陳為生物組成員. 問在以上3種情況下能否各選出3名不兼職的組長？,52,解：設(shè)v1，v2，v3，v4，v5分別表示張、王、李、趙、陳，u1，u2，u3分別表示網(wǎng)絡(luò)組、網(wǎng)頁制作組、數(shù)據(jù)庫組，則根據(jù)上述三種情況得到的二部圖如圖10-26所示。,53,

36、G1滿足t=2的t條件,所以,存在從V1={u1,u2,u3}到V2={v1,v2,v3,v4,v5}的完備匹配,圖中粗邊所示的匹配就是其中的一個,即選張為物理組組長、李為化學(xué)組組長、趙為生物組組長.G2不滿足t條件,但滿足相異性條件,因而也存在完備匹配,圖中粗邊所示匹配就是其中的一個完備匹配. G3不滿足t條件,也不滿足相異性條件,因而不存在完備匹配,故選不出3名不兼職的組長來.,54,因為圖(a)滿足t＝2的t條件，所以圖(a)