acm算法_淺談圖論模型的建立與應(yīng)用

1、淺談圖論模型的建立與應(yīng)用,廣東省中山市第一中學(xué) 黃源河,引言,圖論是數(shù)學(xué)的一個(gè)有趣的分支。圖論的建模，就是要抓住問題的本質(zhì)，把問題抽象為點(diǎn)、邊、權(quán)的關(guān)系。許多看似無從入手的問題，通過圖論建模，往往能轉(zhuǎn)化為我們熟悉的經(jīng)典問題。,例題1 Place the Robots（ZOJ）,問題描述 有一個(gè)N*M(N,M<=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機(jī)器人只能放在空地上。在同一行或同一列

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

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

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

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

6、的雇傭（ACM Tehran 2000）,問題描述 有一家24小時(shí)營業(yè)的超市，需要雇傭一批出納員。一天中每個(gè)小時(shí)需要出納員的最少數(shù)量為R0,R1,R2,...,R23。有N個(gè)人申請這項(xiàng)工作，每個(gè)申請者，從一個(gè)特定時(shí)刻開始連續(xù)工作恰好8個(gè)小時(shí)，設(shè)Wi（i=0...23）表示從時(shí)刻i開始工作的申請者的人數(shù)（∑Wi=N<=1000）。 你的任務(wù)是計(jì)算出需要雇傭出納員的最少數(shù)目，滿足在每一時(shí)刻i，至少有Ri名出納員

7、在工作。,例題2 出納員的雇傭（ACM Tehran 2000）,分析,初看本題，很容易使人往貪心、動(dòng)態(tài)規(guī)劃或網(wǎng)絡(luò)流這些方面思考。然而，對于本題，這些算法都無能為力。 由于本題的約束條件很多，為了理清思路，我們先把題目中的約束條件用數(shù)學(xué)語言表達(dá)出來。設(shè)S[i]表示0～i時(shí)刻雇傭出納員的總數(shù)，那么我們可以將題目中的約束條件轉(zhuǎn)化為下面的不等式組：,0≤S[i]-S[i-1]≤Wi (0≤i≤23)S[i

8、]-S[i-8]≥Ri (8≤i≤23)S[23]+S[i]-S[i+16]≥Ri (0≤i≤7),例題2 出納員的雇傭（ACM Tehran 2000）,分析,這樣的不等式組，不禁使我們想到了差分約束系統(tǒng)。對于每個(gè)不等式 S[i]-S[j]≤K，從頂點(diǎn)ｊ向頂點(diǎn)ｉ引一條權(quán)值為K的有向邊。我們要求S[23]的最小值，就是要求頂點(diǎn)0到頂點(diǎn)23的最短路。注意上面第三條不等式：它包含三個(gè)未知數(shù)

9、，無法在圖中表示為邊的關(guān)系。,0≤S[i]-S[i-1]≤Wi (0≤i≤23)S[i]-S[i-8]≥Ri (8≤i≤23),S[23]+S[i]-S[i+16]≥Ri (0≤i≤7),怎么辦,例題2 出納員的雇傭（ACM Tehran 2000）,分析,退一步考慮：如果S[23]已經(jīng)確定了，那么上面的不等式組可以完全轉(zhuǎn)化為一個(gè)有向圖，頂點(diǎn)0到頂點(diǎn)ｉ的最短路，就是S[

10、i]的解。而當(dāng)圖中存在負(fù)權(quán)回路時(shí)，不等式組無解。至于S[23]，我們可以用二分法枚舉，逐步縮小范圍，用迭代法判斷是否存在負(fù)權(quán)回路（判定可行性），最終求得S[23]的最小值。時(shí)間復(fù)雜度為O(243*log2N)。,,0≤S[i]-S[i-1]≤Wi (0≤i≤23)S[i]-S[i-8]≥Ri (8≤i≤23),S[23]+S[i]-S[i+16]≥Ri (0≤i≤7),

11、例題2 出納員的雇傭（ACM Tehran 2000）,小結(jié),本題用到了差分約束系統(tǒng)的理論，在競賽中，這樣的系統(tǒng)并不多見，但是卻可以巧妙的解決一些難題。這類題目的模型都不明顯，需要一定的思考和轉(zhuǎn)化。做這類題目，關(guān)鍵是要把題目中的約束條件表示為不等式，再把不等式轉(zhuǎn)化為圖的最短路或最長路模型。,例題3 貪婪之島（ZOJ）,,問題描述 有N（N≤100000）張卡片，每張卡片有三種能力，每種能力的能力值分別為Ai，Bi，Ci

12、。每張卡片可以使用其中一種能力，且每張卡片只能使用一次?，F(xiàn)在需要A張卡片使用第一種能力，B張卡片使用第二種能力，C張卡片使用第三種能力（A+B+C≤100）。請計(jì)算使用哪些卡片，以及使用卡片的哪項(xiàng)能力，可以使相應(yīng)的能力值之和最大。,例題3 貪婪之島（ZOJ）,,分析 最優(yōu)化問題的解法有很多種，比如動(dòng)態(tài)規(guī)劃，網(wǎng)絡(luò)流等，而本題就是一個(gè)比較明顯的網(wǎng)絡(luò)流模型。 網(wǎng)絡(luò)流模型中，權(quán)的類型眾多，有流量，容量，還可以有費(fèi)用。

13、在本題中，容量可以作為選取的約束，確保解的合法性；費(fèi)用則表示選取的價(jià)值，確保解的最優(yōu)性。因此，更確切地說，本題是一個(gè)最大費(fèi)用最大流模型。,構(gòu)圖,每張卡片ｉ用頂點(diǎn)ｉ表示，另外加三個(gè)頂點(diǎn)P1，P2，P3，表示三種能力，還有源點(diǎn)S，匯點(diǎn)T。,例題3 貪婪之島（ZOJ）,構(gòu)圖,從源點(diǎn)分別向P1，P2，P3引一條弧，容量分別為A，B，C，費(fèi)用為0。,例題3 貪婪之島（ZOJ）,構(gòu)圖,,A,0,,B,0,,C,0,從P1，P2，P3向頂點(diǎn)ｉ(1

14、≤i≤N) 分別引一條弧，容量為1，費(fèi)用分別為Ai，Bi，Ci。,例題3 貪婪之島（ZOJ）,構(gòu)圖,,A,0,,B,0,,C,0,,,,,,,,,,,,,,,,從頂點(diǎn)ｉ(1≤i≤N) 向匯點(diǎn)引一條弧，容量為1，費(fèi)用為0。,例題3 貪婪之島（ZOJ）,構(gòu)圖,構(gòu)圖之后，求出從S到T的最大費(fèi)用最大流，再檢查流出P1，P2，P3的弧，并輸出最優(yōu)方案。,時(shí)間復(fù)雜度：O(N3),例題3 貪婪之島（ZOJ）,N太大了，需要進(jìn)一步優(yōu)化！,優(yōu)化,例

15、題3 貪婪之島（ZOJ）,本題的卡片總數(shù)有十萬之多，而最終要選取的卡片數(shù)不超過100張。如果在構(gòu)圖之前，把沒有用的卡片先刪掉，必將大大提高效率。什么樣的卡片是沒有用的呢？先考慮第一種能力的選?。喝绻讶靠ㄆ吹谝环N能力值從大到小排序，顯然我們應(yīng)該盡量從前面選A張出來，由于每張卡片只能使用一次，所以有可能會和其他的兩種能力發(fā)生沖突，而沖突的卡片數(shù)最多是B+C張，所以實(shí)際上對我們有用的卡片只是前面的A+B+C張。,優(yōu)化,例題3 貪

16、婪之島（ZOJ）,同理，對于第二種和第三種能力的選取，也只需保留其能力值最大的前A+B+C張卡片。這一步可以在線性時(shí)間內(nèi)解決。這是一個(gè)既簡單又有效的方法，經(jīng)過這一步處理，保留下來的卡片數(shù)不會超過3(A+B+C)張，頂點(diǎn)數(shù)大大減少，求解最大費(fèi)用最大流的時(shí)間復(fù)雜度降為O((A+B+C)3)。至此，算法已經(jīng)優(yōu)化到了一個(gè)可以接受的地步，時(shí)間復(fù)雜度僅為O(N+(A+B+C)3)。,優(yōu)化,例題3 貪婪之島（ZOJ）,如果還要進(jìn)一步提高效率，可

17、以用更有效的算法刪掉多余的頂點(diǎn)。不過這樣做意義不大，而且也不是本文討論的要點(diǎn)。另外，本題還可以轉(zhuǎn)化為二部圖模型，用最佳匹配算法求解。這一步留給讀者自己思考。,小結(jié),例題3 貪婪之島（ZOJ）,本題建立的是網(wǎng)絡(luò)流模型。這類模型的算法系數(shù)大，編程復(fù)雜度也大，在競賽中往往作為走投無路時(shí)的“候補(bǔ)算法”。但是，網(wǎng)絡(luò)流模型的適用性廣，一些較復(fù)雜，或者約束較多的問題，網(wǎng)絡(luò)流模型可以很好地解決，而基于網(wǎng)絡(luò)流模型的問題又比較明顯，這使得網(wǎng)絡(luò)流模型有著

18、廣泛的應(yīng)用。,結(jié)語,問題是千變?nèi)f化的，如何建立問題的圖論模型并沒有通用的準(zhǔn)則。前面的幾個(gè)例子都比較簡單，在更復(fù)雜的問題中，有時(shí)我們會感到難以建立適當(dāng)?shù)哪Ｐ停@時(shí)，我們需要在不改變問題原型本身的性質(zhì)的前提下，對原型進(jìn)行抽象，簡化，在此基礎(chǔ)上建立合適，有效的模型。有時(shí)，我們建立了問題的一個(gè)模型之后，可能會感到難以求解，這時(shí)，我們可能需要對模型進(jìn)行修改，轉(zhuǎn)化，或者對原型進(jìn)行更深入的分析，抽取其中較關(guān)鍵的要素，建立一個(gè)易于求解的模型。這些都需要