淺談論模型的建立與應用ppt課件

1、淺談圖論模型的淺談圖論模型的建立與運用建立與運用 引言v圖論是數(shù)學的一個有趣的分支。v圖論的建模，就是要抓住問題的本質，把問題籠統(tǒng)為點、邊、權的關系。v許多看似無從入手的問題，經(jīng)過圖論建模，往往能轉化為我們熟習的經(jīng)典問題。例題1 Place the RobotsZOJ問題描畫 有一個N*M(N,M=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機器人只能放在空地上。在同一行或同一列的兩個機器人，假設它們之間沒有墻，那么它們可以相互攻擊。問給定的棋盤，最多可以放置多少個機器人，使它們不能相互攻擊。 Wall Grass Empty例題1 Place the RobotsZOJ模型一5

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

3、。顯然，在一個塊之中，最多只能放一個機器人。我們把這些塊編上號。同樣，把豎直方向的塊也編上號。例題1 Place the RobotsZOJ模型二123451234例題1 Place the RobotsZOJ模型二123451234把每個橫向塊看作X部的點，豎向塊看作Y部的點，假設兩個塊有公共的空地，那么在它們之間連邊。于是，問題轉化成這樣的一個二部圖：112233445由于每條邊表示一個空地，有沖突的空地之間必有公共頂點，所以問題轉化為二部圖的最大匹配問題。例題1 Place the RobotsZOJ模型二123412354112233445比較前面的兩個模型：模型一過于簡單，沒有給問題

4、的求解帶來任何便利；模型二那么充分抓住了問題的內(nèi)在聯(lián)絡，巧妙地建立了二部圖模型。為什么會產(chǎn)生這種截然不同的結果呢？其一是由于對問題分析的角度不同：模型一以空地為點，模型二以空地為邊；其二是由于對原型中要素的選取有差別：模型一對要素的選取不充分，模型二那么保管了原型中“棋盤這個重要的性質。由此可見，對要素的選取，是圖論建模中至關重要的一步。例題1 Place the RobotsZOJ小結例題2 出納員的雇傭ACM Tehran 2000問題描畫 有一家24小時營業(yè)的超市，需求雇傭一批出納員。一天中每個小時需求出納員的最少數(shù)量為R0,R1,R2,.,R23。有N個人懇求這項任務，每個懇求者，從一

5、個特定時辰開場延續(xù)任務恰好8個小時，設Wii=0.23表示從時辰i開場任務的懇求者的人數(shù)Wi=N=1000。 他的義務是計算出需求雇傭出納員的最少數(shù)目，滿足在每一時辰i，至少有Ri名出納員在任務。例題2 出納員的雇傭ACM Tehran 2000分析 初看此題，很容易使人往貪婪、動態(tài)規(guī)劃或網(wǎng)絡流這些方面思索。然而，對于此題，這些算法都無能為力。 由于此題的約束條件很多，為了理清思緒，我們先把標題中的約束條件用數(shù)學言語表達出來。設Si表示0i時辰雇傭出納員的總數(shù)，那么我們可以將標題中的約束條件轉化為下面的不等式組：0Si-Si-1Wi (0i23)Si-Si-8Ri (8i23)S23+Si-S

6、i+16Ri (0i7)例題2 出納員的雇傭ACM Tehran 2000分析這樣的不等式組，不由使我們想到了差分約束系統(tǒng)。對于每個不等式 Si-SjK，從頂點向頂點引一條權值為K的有向邊。我們要求S23的最小值，就是要求頂點0到頂點23的最短路。留意上面第三條不等式：它包含三個未知數(shù)，無法在圖中表示為邊的關系。0Si-Si-1Wi (0i23)Si-Si-8Ri (8i23)S23+Si-Si+16Ri (0i7)怎樣怎樣辦辦例題2 出納員的雇傭ACM Tehran 2000分析退一步思索：假設S23曾經(jīng)確定了，那么上面的不等式組可以完全轉化為一個有向圖，頂點0到頂點的最短路，就是Si的解。

7、而當圖中存在負權回路時，不等式組無解。至于S23，我們可以用二分法枚舉，逐漸減少范圍，用迭代法判別能否存在負權回路斷定可行性，最終求得S23的最小值。時間復雜度為O(243*log2N)。0Si-Si-1Wi (0i23)Si-Si-8Ri (8i23)S23+Si-Si+16Ri (0i7)例題2 出納員的雇傭ACM Tehran 2000小結此題用到了差分約束系統(tǒng)的實際，在競賽中，這樣的系統(tǒng)并不多見，但是卻可以巧妙的處理一些難題。這類標題的模型都不明顯，需求一定的思索和轉化。做這類標題，關鍵是要把標題中的約束條件表示為不等式，再把不等式轉化為圖的最短路或最長路模型。例題3 貪婪之島ZOJ問

8、題描畫 有NN100000張卡片，每張卡片有三種才干，每種才干的才干值分別為Ai，Bi，Ci。每張卡片可以運用其中一種才干，且每張卡片只能運用一次。如今需求A張卡片運用第一種才干，B張卡片運用第二種才干，C張卡片運用第三種才干A+B+C100。請計算運用哪些卡片，以及運用卡片的哪項才干，可以使相應的才干值之和最大。例題3 貪婪之島ZOJ分析 最優(yōu)化問題的解法有很多種，比如動態(tài)規(guī)劃，網(wǎng)絡流等，而此題就是一個比較明顯的網(wǎng)絡流模型。 網(wǎng)絡流模型中，權的類型眾多，有流量，容量，還可以有費用。在此題中，容量可以作為選取的約束，確保解的合法性；費用那么表示選取的價值，確保解的最優(yōu)性。因此，更確切地說，此題

9、是一個最大費用最大流模型。構圖SP2P1P312345T每張卡片用頂點表示，另外加三個頂點P1，P2，P3，表示三種才干，還有源點S，匯點T。例題3 貪婪之島ZOJ構圖SP2P1P312345TA,0B,0C,0從源點分別向P1，P2，P3引一條弧，容量分別為A，B，C，費用為0。例題3 貪婪之島ZOJ構圖SP2P1P312345TA,0B,0C,0從P1，P2，P3向頂點(1iN) 分別引一條弧，容量為1，費用分別為Ai，Bi，Ci。例題3 貪婪之島ZOJ構圖SP2P1P312345TA,0B,0C,01,01,01,01,01,0從頂點(1iN) 向匯點引一條弧，容量為1，費用為0。例題3

10、 貪婪之島ZOJ構圖SP2P1P312345TA,0B,0C,01,01,01,01,01,0構圖之后，求出從S到T的最大費用最大流，再檢查流出P1，P2，P3的弧，并輸出最優(yōu)方案。時間復雜度：O(N3)例題3 貪婪之島ZOJN N太大了，需求進一步優(yōu)化！太大了，需求進一步優(yōu)化！優(yōu)化例題3 貪婪之島ZOJ此題的卡片總數(shù)有十萬之多，而最終要選取的卡片數(shù)不超越100張。假設在構圖之前，把沒有用的卡片先刪掉，必將大大提高效率。什么樣的卡片是沒有用的呢？先思索第一種才干的選?。杭僭O把全部卡片按第一種才干值從大到小排序，顯然我們應該盡量從前面選A張出來，由于每張卡片只能運用一次，所以有能夠會和其他的兩種

11、才干發(fā)生沖突，而沖突的卡片數(shù)最多是B+C張，所以實踐上對我們有用的卡片只是前面的A+B+C張。優(yōu)化例題3 貪婪之島ZOJ同理，對于第二種和第三種才干的選取，也只需保管其才干值最大的前A+B+C張卡片。這一步可以在線性時間內(nèi)處理。這是一個既簡單又有效的方法，經(jīng)過這一步處置，保管下來的卡片數(shù)不會超越3(A+B+C)張，頂點數(shù)大大減少，求解最大費用最大流的時間復雜度降為O(A+B+C)3)。至此，算法曾經(jīng)優(yōu)化到了一個可以接受的地步，時間復雜度僅為O(N+(A+B+C)3)。優(yōu)化例題3 貪婪之島ZOJ假設還要進一步提高效率，可以用更有效的算法刪掉多余的頂點。不過這樣做意義不大，而且也不是本文討論的要點。另外，此題還可以轉化為二部圖模型，用最正確匹配算法求解。這一步留給讀者本人思索。小結例題3 貪婪之島ZOJ此題建立的是網(wǎng)絡流模型。這類模型的算法系數(shù)大，編程復雜度也大，在競賽中往往作為走投無路時的“候補算法。但是，網(wǎng)絡流模型的適用性廣，一些較復雜，或者約束較多的問題，網(wǎng)絡流模型可以很好地處理，而基于網(wǎng)絡流模型的問題又比較明顯，這使得網(wǎng)絡流模型有著廣泛的運用。結語問題是千變?nèi)f化的，如何建立問題的圖論模型并沒有通用的準那么。前面的幾個例子都比較簡單，在更復雜的問