信息學競賽算法分析與設計

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

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

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

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

5、T;(5)若y為M飽和點轉(6),否則作求一條從x到y(tǒng)的M可增廣路P,置M=M?P,轉(2)(6)由于y是M飽和點,故M中有一邊{y,u},置S=S?{u},T=T?{y},轉(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的所有非飽和點都給以標號

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

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

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

13、2, y3都給以標號1. 因為y2, y3都是M0的兩個飽和點,所以將它們在M0中鄰接的兩個點x2, x3都給以相應的標號和標記* (如下圖所示).,19,,④ 去掉x2的標記*, 將與x2鄰接且尚未給標號的三個點y1, y4, y5都給以標號2 (如下圖所示).,20,⑤ 因為y1是M0的非飽和點, 所以順著標號逆向返回依次得到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給以標號0和標記*, 然后去掉x4的標記*, 將與x4鄰接的兩個點y2, y3都給以標號4.,因為y2, y3都是M1的兩個飽和點, 所以將它們在M1中鄰接的兩個點x1, x3都給以相應的標號和標記* (如下圖所示).,22,⑦ 去掉x1的標

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

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

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

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

19、，相等子圖中至少出現(xiàn)了一條不屬于M的邊，所以造成M的逐漸增廣。,27,KM算法,上述算法的證明也很容易Kuhn－Munkras算法流程：(1)初始化可行頂標的值(2)用匈牙利算法尋找完備匹配(3)若未找到完備匹配則修改可行頂標的值(4)重復(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 救護傷員（TOJ1148）3 打獵4 最小路徑覆蓋5 一些例子6 二部圖相關的定義、定理,30,例題1 Place the Robots（ZOJ1654）,問題描述 有一個N*M(N,M<=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機器人只能放在空地上。在同一行或同一列的兩個機器

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

22、Robots（ZOJ）,模型一,在問題的原型中，草地，墻這些信息不是我們所關心的，我們關心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點，有沖突的空地間連邊，我們可以得到右邊的這個圖：,這是NP問題！,33,我們將每一行，每一列被墻隔開，且包含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個塊之中，最多只能放一個機器人。我們把這些塊編上號。,同樣，把豎直方向的塊也編上號。,例題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部的點，若兩個塊有公共的空地，則在它們之間連邊。,于是，問題轉化成這樣的一個二部圖：,35,由于每條邊表示一個空地，有沖突的空地之間必有公共頂點，所以問題轉化為二部圖的最大匹配問題。,例題1 Place the Robots（ZOJ）,模型二,1,2,3,5,4,3

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

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

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

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

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

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

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

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

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

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

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

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

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