《mafia淺析》ppt課件

1、BOI 2021 競賽題討論競賽題討論mafia義務描畫義務描畫 需找出高速路網(wǎng)上的監(jiān)控結點收費站需找出高速路網(wǎng)上的監(jiān)控結點收費站集合，這些監(jiān)控結點滿足以下條件：集合，這些監(jiān)控結點滿足以下條件： 1 1在這些結點布置警力就能保證擒住歹在這些結點布置警力就能保證擒住歹徒徒 2 2 結點的監(jiān)控費用之和最小結點的監(jiān)控費用之和最小 問題籠統(tǒng)與歸納問題籠統(tǒng)與歸納1 以收費站為頂點，高速公路路段為邊，可以收費站為頂點，高速公路路段為邊，可以構造一張頂點有權值的無向圖。以構造一張頂點有權值的無向圖。 標題的目的是找到一組頂點，其權值之和標題的目的是找到一組頂點，其權值之和最小，且某兩個確定的頂點之間的任何一

2、最小，且某兩個確定的頂點之間的任何一條途徑必需經(jīng)過這組頂點中的至少一個。條途徑必需經(jīng)過這組頂點中的至少一個。 問題類比問題類比 思索一個與之類似的問題。思索一個與之類似的問題。 假設需求監(jiān)視的不是收費站圖的頂點而假設需求監(jiān)視的不是收費站圖的頂點而是高速公路路段圖的邊是高速公路路段圖的邊 那么問題就轉化為在一張帶權的無向圖中尋那么問題就轉化為在一張帶權的無向圖中尋覓一個邊的集合，使得兩個固定頂點之間的覓一個邊的集合，使得兩個固定頂點之間的途徑必需包含這個集合中的至少一條邊，且途徑必需包含這個集合中的至少一條邊，且集合內(nèi)的邊的權值之和為最小。集合內(nèi)的邊的權值之和為最小。 這就化為了一個最小割問題。

3、這就化為了一個最小割問題。 問題轉換方法問題轉換方法 對于原圖中的每一個頂點對于原圖中的每一個頂點v v構建其對偶頂構建其對偶頂點點vv，添加從，添加從v v到到vv的有向邊，其權值的有向邊，其權值是頂點是頂點v v的權值；的權值；對于原圖中的每一條從頂點對于原圖中的每一條從頂點v v到頂點到頂點u u的有的有向邊無向邊可以看成兩條有向邊對應向邊無向邊可以看成兩條有向邊對應為從為從vv到到u u的一條邊，其權值為無窮。的一條邊，其權值為無窮。 那么問題化為這張新圖中從頂點那么問題化為這張新圖中從頂點a a到頂點到頂點bb的最小割的求解。的最小割的求解。 問題轉化問題轉化 在原圖中經(jīng)過頂點在原圖

4、中經(jīng)過頂點v v的行為在轉換后的圖中的行為在轉換后的圖中為先經(jīng)過為先經(jīng)過v v，由邊，由邊(v,v)(v,v)再經(jīng)過再經(jīng)過vv。 這樣的變換等于是構建了每個頂點的內(nèi)部這樣的變換等于是構建了每個頂點的內(nèi)部構造，入口為構造，入口為v v，出口為，出口為vv 原來是頂點原來是頂點v v的權值就變成了邊的權值就變成了邊(v,v)(v,v)的的權值，監(jiān)視頂點的行為也變成了監(jiān)視邊的權值，監(jiān)視頂點的行為也變成了監(jiān)視邊的行為。行為。 連通加權有向圖的最小割連通加權有向圖的最小割 流網(wǎng)絡簡稱網(wǎng)絡是一種帶權有向圖，流網(wǎng)絡簡稱網(wǎng)絡是一種帶權有向圖， 每條邊均有一個非負的容量每條邊均有一個非負的容量c(u,v)=0c

5、(u,v)=0。網(wǎng)絡中有兩個特殊點：源點網(wǎng)絡中有兩個特殊點：源點s s和匯點和匯點t t。 網(wǎng)絡網(wǎng)絡G G的割集：將頂點集的割集：將頂點集V V劃分為劃分為S S和和T TT=V-T=V-S S使得使得sSsS，tTtT，那么稱邊集，那么稱邊集S,TS,T為網(wǎng)為網(wǎng)絡絡G G的一個割。的一個割。 穿過割穿過割S,TS,T的凈流定義為的凈流定義為f (S,T)f (S,T)，割，割S,TS,T的容量稱為的容量稱為c(S,T)c(S,T)。一個網(wǎng)絡。一個網(wǎng)絡G G中的最小割中的最小割即為網(wǎng)絡中容量最小的割。即為網(wǎng)絡中容量最小的割。 兩終端網(wǎng)絡連通加權有向圖的最小割：兩終端網(wǎng)絡連通加權有向圖的最小割：

6、對于一個源為對于一個源為s s匯為匯為t t的網(wǎng)絡的網(wǎng)絡G G，割是邊的集，割是邊的集合合S,TS,T，滿足每條從，滿足每條從s s到到t t的途徑都至少經(jīng)的途徑都至少經(jīng)過過S,TS,T中的一條邊。中的一條邊。 換言之，假設換言之，假設S,TS,T中的邊都被刪除掉，那中的邊都被刪除掉，那么不存在從么不存在從s s到到t t的有向途徑。割的容量是指的有向途徑。割的容量是指割中一切邊的容量之和。網(wǎng)絡割中一切邊的容量之和。網(wǎng)絡G G的最小割是的最小割是指有最小容量的割。指有最小容量的割。 性質(zhì)：性質(zhì)： 兩類點在給定的流網(wǎng)絡中，恣意一個兩類點在給定的流網(wǎng)絡中，恣意一個割將點集劃分成兩部分。割為兩部分點

7、之割將點集劃分成兩部分。割為兩部分點之間的橋梁。間的橋梁。網(wǎng)絡的流和最大流網(wǎng)絡的流和最大流 對于邊集合對于邊集合E E中的每一條邊都有一個流量，中的每一條邊都有一個流量，其值非負且不大于這條邊的容量；其值非負且不大于這條邊的容量； 對于每一個非源點且非匯點的頂點來說，對于每一個非源點且非匯點的頂點來說，其輸入量等于輸出量；源點其輸入量等于輸出量；源點s s的凈流出量等的凈流出量等于匯點于匯點t t的凈流入量，稱為一個可行流的流的凈流入量，稱為一個可行流的流量。量。 最大流問題就是求一個網(wǎng)絡的流量最大的最大流問題就是求一個網(wǎng)絡的流量最大的可行流。可行流。 根據(jù)最大流最小割定理，最大流的流值等根據(jù)

8、最大流最小割定理，最大流的流值等于最小割的容量，求最小割的問題等價于于最小割的容量，求最小割的問題等價于最大流問題。最大流問題。 解此題的三個步驟：解此題的三個步驟： 轉化轉化計算最大流計算最大流求出最小割求出最小割 由最大流求最小割由最大流求最小割 由最大流求最小割的詳細方法：將每條邊由最大流求最小割的詳細方法：將每條邊的容量的容量c(u,v)減去其流量減去其流量f (u,v)得到新的容得到新的容量量cf構成殘留網(wǎng)絡構成殘留網(wǎng)絡residual networkGf cf為零那么以為這條邊在殘留網(wǎng)絡中不存在為零那么以為這條邊在殘留網(wǎng)絡中不存在。 源點源點s所在的最大連通分量可以經(jīng)過所在的最大連

9、通分量可以經(jīng)過DFS得得到，由此就可以求得最小割。到，由此就可以求得最小割。 最大流的求法最大流的求法1 * 增廣途徑方法增廣途徑方法 Augmenting Path Method (Ford-Fulkerson Method) 增廣路增廣路 殘留網(wǎng)絡上源殘留網(wǎng)絡上源s到匯到匯t的一條簡單途的一條簡單途徑徑 1.最短增廣路算法最短增廣路算法Edmonds-Karp算法算法 在殘留網(wǎng)絡中，每次找一條含結點數(shù)最少的在殘留網(wǎng)絡中，每次找一條含結點數(shù)最少的增廣路增廣，即殘留網(wǎng)絡中源到匯的增廣路增廣，即殘留網(wǎng)絡中源到匯的BFS途途徑徑 算法復雜度算法復雜度 O(nm2) ，邊稠密時不宜，邊稠密時不宜 n

10、=|V|，m=|E| 最大流的求法最大流的求法22. 延續(xù)最短增廣路算法延續(xù)最短增廣路算法在在Edmonds Karp算法的根底上改造。算法的根底上改造。在每次在每次BFS找增廣路時，記錄每個點的間隔標號。找增廣路時，記錄每個點的間隔標號。在間隔標號所構成的最短路圖上，不斷地在間隔標號所構成的最短路圖上，不斷地DFS找找增廣路。即一次標號多次增廣，以提高速度。增廣路。即一次標號多次增廣，以提高速度。算法復雜度算法復雜度 O(n2m) 最大流的求法最大流的求法3* 預流推進方法預流推進方法 Preflow-Push Method 1. 先進先出預流推進算法先進先出預流推進算法 FIFO 以先進先

11、出隊列維護活潑結點。以先進先出隊列維護活潑結點。 算法復雜度算法復雜度 O(n3) 2. 最高標號預流推進算法最高標號預流推進算法 每次檢查具有最高標號的活潑結點每次檢查具有最高標號的活潑結點。 算法復雜度算法復雜度 O(n2m1/2) 方法比較方法比較 增廣路方法的復雜度是經(jīng)過估計增廣次數(shù)增廣路方法的復雜度是經(jīng)過估計增廣次數(shù)的上界得到的。的上界得到的。 對于實踐運用中的網(wǎng)絡，增廣次數(shù)往往很對于實踐運用中的網(wǎng)絡，增廣次數(shù)往往很少，所以運用范圍很廣，適用性強。少，所以運用范圍很廣，適用性強。 預流推進方法看似比增廣路方法在復雜度預流推進方法看似比增廣路方法在復雜度上快很多，然而實踐上，預流推進方

12、法的上快很多，然而實踐上，預流推進方法的復雜度上界較緊。復雜度上界較緊。 對于一些稀疏圖，預流推進方法的實踐效對于一些稀疏圖，預流推進方法的實踐效果往往不如增廣路方法。果往往不如增廣路方法。 增廣途徑方法求最大流增廣途徑方法求最大流 偽碼表示如下摘自偽碼表示如下摘自: * FORD-FULKERSON(G, s, t) 1 for each edge (u, v) EG 2 do f(u, v) 0 3 f(v, u) 0 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p) min cf

13、(u, v) : (u, v) is in p 6 for each edge (u, v) in p 7 do f(u, v) f(u, v) + cf(p) 8 f(v, u) -f(u, v) *算法實現(xiàn)細節(jié)算法實現(xiàn)細節(jié)1. 網(wǎng)絡的轉換網(wǎng)絡的轉換網(wǎng)絡的轉換在從規(guī)范輸入讀入數(shù)據(jù)的同時進網(wǎng)絡的轉換在從規(guī)范輸入讀入數(shù)據(jù)的同時進展，展，將一個頂點拆分成兩個，頂點將一個頂點拆分成兩個，頂點i為為v，頂點，頂點i+n為為v；同時將輸入的一條無向邊分為兩條有向邊。同時將輸入的一條無向邊分為兩條有向邊。部分代碼如下：部分代碼如下：算法實現(xiàn)細節(jié)算法實現(xiàn)細節(jié)*for (i=1;icost; G.insert

14、Edge(i,i+n,cost); /從v到v的帶有該頂點權值的邊 G.insertEdge(i+n,i,0); /容量為0的逆向邊E-K算法時用for (i=1;iv1v2; /從頂點v1到頂點v2的容量為無窮的邊 G.insertEdge(v1+n,v2,-1); /從頂點v2到頂點v1的容量為無窮的邊 G.insertEdge(v2+n,v1,-1)；/容量為0的逆向邊E-K算法時用 G.insertEdge(v1,v2+n,0); G.insertEdge(v2,v1+n,0);* 算法設計算法設計2. 用前述算法將網(wǎng)絡轉換為不含增廣途徑的用前述算法將網(wǎng)絡轉換為不含增廣途徑的殘留網(wǎng)絡如

15、殘留網(wǎng)絡如Edmond-Karp算法算法 Edmond-Karp算法可用來求最大流。但該問算法可用來求最大流。但該問題中不需求求得最大流，只需求找到最小題中不需求求得最大流，只需求找到最小割。割。所以只需將該網(wǎng)絡轉換為其不含增廣途徑的所以只需將該網(wǎng)絡轉換為其不含增廣途徑的殘留網(wǎng)絡，再對這個殘留網(wǎng)絡進展連通分殘留網(wǎng)絡，再對這個殘留網(wǎng)絡進展連通分量查找后就可以得到問題所需的解。量查找后就可以得到問題所需的解。算法設計算法設計3. 尋覓最小割尋覓最小割, 即需求監(jiān)控的頂點即需求監(jiān)控的頂點這部分首先經(jīng)過一個這部分首先經(jīng)過一個BFS尋覓源點尋覓源點s轉換后轉換后的頂點的頂點a所在的連通分量，所在的連通分

16、量，然后對于每一對頂點然后對于每一對頂點(v,v)，假設，假設v在該連通在該連通分量中而分量中而v不在，那么闡明邊不在，那么闡明邊vv屬于最屬于最小割，頂點小割，頂點v是所要監(jiān)視的頂點之一。是所要監(jiān)視的頂點之一。 實現(xiàn)細節(jié)實現(xiàn)細節(jié) 利用最后一次執(zhí)行利用最后一次執(zhí)行BFSBFS此時此時BFSBFS前往值為前往值為falsefalse得到的得到的visitvisit數(shù)組。最小割一定數(shù)組。最小割一定是形如是形如v-vv-v，且流量到達容量的邊。，且流量到達容量的邊。 由于最小割一定是飽和的滿流邊且最由于最小割一定是飽和的滿流邊且最小割滿足極小條件但飽和的不一定都是小割滿足極小條件但飽和的不一定都是最

17、小割最小割 在此題構造的特殊網(wǎng)絡中，除去形如在此題構造的特殊網(wǎng)絡中，除去形如v-v-vv以外的邊的權值都是無窮大，不能夠以外的邊的權值都是無窮大，不能夠到達飽和。到達飽和。轉換前后的數(shù)據(jù)規(guī)模轉換前后的數(shù)據(jù)規(guī)模 原圖：原圖：2n200，1m20000 1cost10000000 轉化后的圖：轉化后的圖： 4N=2n400, 4M=2m+n40200 程序運轉環(huán)境與結果程序運轉環(huán)境與結果 運轉環(huán)境參數(shù)：運轉環(huán)境參數(shù)： CPU：Intel(R) Core(TM)2 Duo CPU T7250 2.00GHz 內(nèi)存：內(nèi)存：1.0GB 系統(tǒng)：系統(tǒng)： Windows XP SP3 開發(fā)環(huán)境：開發(fā)環(huán)境：Vi

18、sual Studio 2005 選取選取10組官方測試數(shù)據(jù)對程序進展測試組官方測試數(shù)據(jù)對程序進展測試 time為直接運轉為直接運轉.exe文件的結果文件的結果 部分測試數(shù)據(jù)運轉時間部分測試數(shù)據(jù)運轉時間 n m time(ms) #maf9a 87 1556 110 #maf10a 100 2698 219 #maf10b 100 171 15 #maf12a 160 4199 484 # maf13c 200 17635 2765 #maf14a 200 4315 656 #maf14c 200 15171 1250 #maf15a 200 4448 593 #maf15b 200 355

19、31 #maf15c 200 18588 2672 完全版？完全版？ 算法復雜性分析算法復雜性分析 Edmonds-Karp算法的時間復雜度為算法的時間復雜度為O(NM2) 廣度優(yōu)先搜索尋覓連通分量的時間復雜度廣度優(yōu)先搜索尋覓連通分量的時間復雜度不超越不超越O(N+M)； 時間復雜度的主要要素還是計算網(wǎng)絡流算時間復雜度的主要要素還是計算網(wǎng)絡流算法的耗時法的耗時 網(wǎng)絡流的廣泛運用網(wǎng)絡流的廣泛運用 網(wǎng)絡最大流在工程技術中的運用非常廣泛網(wǎng)絡最大流在工程技術中的運用非常廣泛 水資源調(diào)度，配電網(wǎng)計算，水資源調(diào)度，配電網(wǎng)計算， 交通網(wǎng)絡優(yōu)化設計，物流配送等交通網(wǎng)絡優(yōu)化設計，物流配送等 甚至音樂作曲上也有涉

20、及甚至音樂作曲上也有涉及 大調(diào)音階和弦進展圖大調(diào)音階和弦進展圖網(wǎng)絡流與作曲網(wǎng)絡流與作曲 確定要作的曲子的風格。確定要作的曲子的風格。 經(jīng)過各個和弦與主和弦的相關度依風格經(jīng)過各個和弦與主和弦的相關度依風格不同而各異，從庫中調(diào)用確定權重。不同而各異，從庫中調(diào)用確定權重。 確定起點，按最大流問題求解。確定起點，按最大流問題求解。 將求得的最小割包含的弧兩端的和弦按一將求得的最小割包含的弧兩端的和弦按一定規(guī)律進展組合，即可得到音樂作品。定規(guī)律進展組合，即可得到音樂作品。 可見，假設將網(wǎng)絡流模型引入樂曲創(chuàng)作，可見，假設將網(wǎng)絡流模型引入樂曲創(chuàng)作，或答應以開辟出算法作曲的另一條蹊徑?；虼饝蚤_辟出算法作曲的

21、另一條蹊徑。 網(wǎng)絡流算法是一種高效適用的算法網(wǎng)絡流算法是一種高效適用的算法 相對于其它圖論算法來說，模型更加復雜相對于其它圖論算法來說，模型更加復雜，編程復雜度也更高。，編程復雜度也更高。 但是它綜合了圖論中的其它一些算法，因但是它綜合了圖論中的其它一些算法，因此適用范圍也更廣，經(jīng)常可以很好地處理此適用范圍也更廣，經(jīng)?？梢院芎玫靥幚硪恍┧阉髋c動態(tài)規(guī)劃無法處理的，看似一些搜索與動態(tài)規(guī)劃無法處理的，看似NPNP的問題。的問題。 最小割是最大流的對偶問題。最小割是最大流的對偶問題。 但在實踐建模過程中，最小割不如最大流但在實踐建模過程中，最小割不如最大流表現(xiàn)的直觀更為籠統(tǒng)，模型也往往隱表現(xiàn)的直觀更為籠統(tǒng)，模型也往往隱蔽得很深，不容易找到構圖