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

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

2、467832112346578于是，問(wèn)題轉(zhuǎn)化為求圖的最大獨(dú)立集問(wèn)題。在問(wèn)題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡(jiǎn)單的模型：以空地為頂點(diǎn)，有沖突的空地間連邊，我們可以得到右邊的這個(gè)圖：例題1 Place the Robots（ZOJ）模型一5467832112346578在問(wèn)題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡(jiǎn)單的模型：以空地為頂點(diǎn)，有沖突的空地間連邊，我們可以得到右邊的這個(gè)圖：這是NP問(wèn)題！我們將每一行，每一列被墻隔開(kāi)，且包含空地的連續(xù)區(qū)域稱作

3、“塊”。顯然，在一個(gè)塊之中，最多只能放一個(gè)機(jī)器人。我們把這些塊編上號(hào)。同樣，把豎直方向的塊也編上號(hào)。例題1 Place the Robots（ZOJ）模型二123451234例題1 Place the Robots（ZOJ）模型二123451234把每個(gè)橫向塊看作X部的點(diǎn)，豎向塊看作Y部的點(diǎn)，若兩個(gè)塊有公共的空地，則在它們之間連邊。于是，問(wèn)題轉(zhuǎn)化成這樣的一個(gè)二部圖：112233445由于每條邊表示一個(gè)空地，有沖突的空地之間必有公共頂點(diǎn)，所以問(wèn)題轉(zhuǎn)化為二部圖的最大匹配問(wèn)題。例題1 Place the Robots（ZOJ）模型二123412354112233445比較前面的兩個(gè)模型：模型一過(guò)于簡(jiǎn)

4、單，沒(méi)有給問(wèn)題的求解帶來(lái)任何便利；模型二則充分抓住了問(wèn)題的內(nèi)在聯(lián)系，巧妙地建立了二部圖模型。為什么會(huì)產(chǎn)生這種截然不同的結(jié)果呢？其一是由于對(duì)問(wèn)題分析的角度不同：模型一以空地為點(diǎn)，模型二以空地為邊；其二是由于對(duì)原型中要素的選取有差異：模型一對(duì)要素的選取不充分，模型二則保留了原型中“棋盤(pán)”這個(gè)重要的性質(zhì)。由此可見(jiàn)，對(duì)要素的選取，是圖論建模中至關(guān)重要的一步。例題1 Place the Robots（ZOJ）小結(jié)例題2 出納員的雇傭（ACM Tehran 2000）問(wèn)題描述 有一家24小時(shí)營(yíng)業(yè)的超市，需要雇傭一批出納員。一天中每個(gè)小時(shí)需要出納員的最少數(shù)量為R0,R1,R2,.,R23。有N個(gè)人申請(qǐng)這項(xiàng)工

5、作，每個(gè)申請(qǐng)者，從一個(gè)特定時(shí)刻開(kāi)始連續(xù)工作恰好8個(gè)小時(shí)，設(shè)Wi（i=0.23）表示從時(shí)刻i開(kāi)始工作的申請(qǐng)者的人數(shù)（Wi=N=1000）。 你的任務(wù)是計(jì)算出需要雇傭出納員的最少數(shù)目，滿足在每一時(shí)刻i，至少有Ri名出納員在工作。例題2 出納員的雇傭（ACM Tehran 2000）分析 初看本題，很容易使人往貪心、動(dòng)態(tài)規(guī)劃或網(wǎng)絡(luò)流這些方面思考。然而，對(duì)于本題，這些算法都無(wú)能為力。 由于本題的約束條件很多，為了理清思路，我們先把題目中的約束條件用數(shù)學(xué)語(yǔ)言表達(dá)出來(lái)。設(shè)Si表示0i時(shí)刻雇傭出納員的總數(shù)，那么我們可以將題目中的約束條件轉(zhuǎn)化為下面的不等式組：0Si-Si-1Wi (0i23)Si-Si-8R

6、i (8i23)S23+Si-Si+16Ri (0i7)例題2 出納員的雇傭（ACM Tehran 2000）分析這樣的不等式組，不禁使我們想到了差分約束系統(tǒng)。對(duì)于每個(gè)不等式 Si-SjK，從頂點(diǎn)向頂點(diǎn)引一條權(quán)值為K的有向邊。我們要求S23的最小值，就是要求頂點(diǎn)0到頂點(diǎn)23的最短路。注意上面第三條不等式：它包含三個(gè)未知數(shù)，無(wú)法在圖中表示為邊的關(guān)系。0Si-Si-1Wi (0i23)Si-Si-8Ri (8i23)S23+Si-Si+16Ri (0i7)怎么辦例題2 出納員的雇傭（ACM Tehran 2000）分析退一步考慮：如果S23已經(jīng)確定了，那么上面的不等式組可以完全轉(zhuǎn)化為一個(gè)有向圖，頂

7、點(diǎn)0到頂點(diǎn)的最短路，就是Si的解。而當(dāng)圖中存在負(fù)權(quán)回路時(shí)，不等式組無(wú)解。至于S23，我們可以用二分法枚舉，逐步縮小范圍，用迭代法判斷是否存在負(fù)權(quán)回路（判定可行性），最終求得S23的最小值。時(shí)間復(fù)雜度為O(243*log2N)。0Si-Si-1Wi (0i23)Si-Si-8Ri (8i23)S23+Si-Si+16Ri (0i7)例題2 出納員的雇傭（ACM Tehran 2000）小結(jié)本題用到了差分約束系統(tǒng)的理論，在競(jìng)賽中，這樣的系統(tǒng)并不多見(jiàn)，但是卻可以巧妙的解決一些難題。這類(lèi)題目的模型都不明顯，需要一定的思考和轉(zhuǎn)化。做這類(lèi)題目，關(guān)鍵是要把題目中的約束條件表示為不等式，再把不等式轉(zhuǎn)化為圖的最

8、短路或最長(zhǎng)路模型。例題3 貪婪之島（ZOJ）問(wèn)題描述 有N（N100000）張卡片，每張卡片有三種能力，每種能力的能力值分別為Ai，Bi，Ci。每張卡片可以使用其中一種能力，且每張卡片只能使用一次?，F(xiàn)在需要A張卡片使用第一種能力，B張卡片使用第二種能力，C張卡片使用第三種能力（A+B+C100）。請(qǐng)計(jì)算使用哪些卡片，以及使用卡片的哪項(xiàng)能力，可以使相應(yīng)的能力值之和最大。例題3 貪婪之島（ZOJ）分析 最優(yōu)化問(wèn)題的解法有很多種，比如動(dòng)態(tài)規(guī)劃，網(wǎng)絡(luò)流等，而本題就是一個(gè)比較明顯的網(wǎng)絡(luò)流模型。 網(wǎng)絡(luò)流模型中，權(quán)的類(lèi)型眾多，有流量，容量，還可以有費(fèi)用。在本題中，容量可以作為選取的約束，確保解的合法性；費(fèi)用

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

10、01,0從頂點(diǎn)(1iN) 向匯點(diǎn)引一條弧，容量為1，費(fèi)用為0。例題3 貪婪之島（ZOJ）構(gòu)圖SP2P1P312345TA,0B,0C,01,01,01,01,01,0構(gòu)圖之后，求出從S到T的最大費(fèi)用最大流，再檢查流出P1，P2，P3的弧，并輸出最優(yōu)方案。時(shí)間復(fù)雜度：O(N3)例題3 貪婪之島（ZOJ）N太大了，需要進(jìn)一步優(yōu)化！優(yōu)化例題3 貪婪之島（ZOJ）本題的卡片總數(shù)有十萬(wàn)之多，而最終要選取的卡片數(shù)不超過(guò)100張。如果在構(gòu)圖之前，把沒(méi)有用的卡片先刪掉，必將大大提高效率。什么樣的卡片是沒(méi)有用的呢？先考慮第一種能力的選?。喝绻讶靠ㄆ吹谝环N能力值從大到小排序，顯然我們應(yīng)該盡量從前面選A張出來(lái)

11、，由于每張卡片只能使用一次，所以有可能會(huì)和其他的兩種能力發(fā)生沖突，而沖突的卡片數(shù)最多是B+C張，所以實(shí)際上對(duì)我們有用的卡片只是前面的A+B+C張。優(yōu)化例題3 貪婪之島（ZOJ）同理，對(duì)于第二種和第三種能力的選取，也只需保留其能力值最大的前A+B+C張卡片。這一步可以在線性時(shí)間內(nèi)解決。這是一個(gè)既簡(jiǎn)單又有效的方法，經(jīng)過(guò)這一步處理，保留下來(lái)的卡片數(shù)不會(huì)超過(guò)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)一步提高效率，可以用更有效的算法

12、刪掉多余的頂點(diǎn)。不過(guò)這樣做意義不大，而且也不是本文討論的要點(diǎn)。另外，本題還可以轉(zhuǎn)化為二部圖模型，用最佳匹配算法求解。這一步留給讀者自己思考。小結(jié)例題3 貪婪之島（ZOJ）本題建立的是網(wǎng)絡(luò)流模型。這類(lèi)模型的算法系數(shù)大，編程復(fù)雜度也大，在競(jìng)賽中往往作為走投無(wú)路時(shí)的“候補(bǔ)算法”。但是，網(wǎng)絡(luò)流模型的適用性廣，一些較復(fù)雜，或者約束較多的問(wèn)題，網(wǎng)絡(luò)流模型可以很好地解決，而基于網(wǎng)絡(luò)流模型的問(wèn)題又比較明顯，這使得網(wǎng)絡(luò)流模型有著廣泛的應(yīng)用。結(jié)語(yǔ)問(wèn)題是千變?nèi)f化的，如何建立問(wèn)題的圖論模型并沒(méi)有通用的準(zhǔn)則。前面的幾個(gè)例子都比較簡(jiǎn)單，在更復(fù)雜的問(wèn)題中，有時(shí)我們會(huì)感到難以建立適當(dāng)?shù)哪Ｐ停@時(shí)，我們需要在不改變問(wèn)題原型本身

13、的性質(zhì)的前提下，對(duì)原型進(jìn)行抽象，簡(jiǎn)化，在此基礎(chǔ)上建立合適，有效的模型。有時(shí)，我們建立了問(wèn)題的一個(gè)模型之后，可能會(huì)感到難以求解，這時(shí)，我們可能需要對(duì)模型進(jìn)行修改，轉(zhuǎn)化，或者對(duì)原型進(jìn)行更深入的分析，抽取其中較關(guān)鍵的要素，建立一個(gè)易于求解的模型。這些都需要我們有豐富的經(jīng)驗(yàn)，靈活的思維以及良好的創(chuàng)造力。謝謝！下面我們來(lái)輕松一下,欣賞一下幾個(gè)經(jīng)典的廣告詞優(yōu)秀廣告詞:早點(diǎn)下斑 不再逗留 默默無(wú)蚊 衣衣不舍 百衣百順 雞不可失 那么請(qǐng)問(wèn)你們對(duì)于這種改動(dòng)成語(yǔ)的廣告有什么看法呢?我還搜集了一些很經(jīng)典的廣告借問(wèn)酒家何處有,牧童遙指杏花村。三十功名創(chuàng)傳奇,八千里路馳江鈴。（山西杏花村酒）（江鈴摩托）禁止抽煙，連皇冠牌也不例外。車(chē)到山前必有路，有路必有豐田車(chē)。（豐田車(chē)）第三塊