試論網絡流算法中模型的優化與選擇

試論網絡流算法中模型的優化與選擇

試論網絡流算法中模型的優化與選擇

福建師大附中 周 成

[內容摘要] 近年來，在國內信息學競賽（尤其是國家隊選拔賽）、國際信息學競賽中，多次出現應用網絡流算法求解的試題，網絡流算法已是信息學奧賽選手必須掌握的算法。本文主要探討不同網絡模型的構造對問題解決的效率的影響，以及如何優化網絡模型，提高算法的效率。

[關鍵詞] 網絡流，模型，優化，選擇。

一、引言

網絡流算法是一種高效實用的算法，相對于其它圖論算法來說，它的模型更加復雜，編程復雜度也更高。但是它綜合了圖論中的其它一些算法（如最短路徑、寬度搜索算法），因而適用范圍也更廣，經常能夠很好地解決一些搜索與動態規劃無法解決的非NP問題。 網絡流在具體問題中的應用，最具挑戰性的部分是模型的構造，它沒用現成的模式可以套用，需要我們對各種網絡流的性質了如指掌（比如點有容量、容量有上下限、多重邊等等），根據具體的問題發揮我們的創造性。一道問題經常可以建立多種模型，不同的模型對問題的解決效率的影響也是不同的，本文通過實例探討如何確定適當的模型，提高網絡流算法的效率。

二、網絡流算法時間效率

當我們確定問題可以使用最大流算法求解后，就根據常用的Ford-Fulkerson標號法求解；而最小（大）費用最大流問題也可用類似標號法的對偶算法解題。Ford-Fulkerson標號法的運行時間為O（VE2），對偶法求最小費用流的運行時間大約為O（V3E2）。

顯然，影響網絡流算法的時間效率的因素主要是網絡中頂點的數目與邊的數目。這二個因素之間不是相互獨立的，而是相互聯系，矛盾而統一的。在構造網絡模型中，有時，實現了某個因素的優化，另外一個因素也隨之得到了優化；有時，實現某個因素的優化卻要以增大另一因素為代價。因此，我們在具體問題的解決中，要堅持"全局觀"，實現二者的平衡。

三、模型的優化與選擇

(一)減少模型的頂點數與邊數，優化模型

如果能根據問題的一些特殊性質，減少網絡模型中的頂點的數目和邊的數目，則可以大大提高算法的效率。

例1：最少皇后控制

在國際象棋中，皇后能向八個方向攻擊（如圖1(a)所示，圖中黑點格子為皇后的位置，標有K的格子為皇后可攻擊到的格子）。現在給定一個M*N（N、M均不大于于50）的棋盤，棋盤上某些格子有障礙。每個皇后被放置在無障礙的格子中，它就控制了這個格子，除此，它可以從它能攻擊到的最多8個格子中選一個格子來控制，如圖1(b)所示，標號為1的格子被一個皇后所控制。

請你編一程序，計算出至少有多少個皇后才能完全控制整個棋盤。

  圖1(a) 圖1(b) 

輸入格式： 輸入文件的第一行有兩個整數M和N，表示棋盤的行數與列數。接下來M行N列為一個字符矩陣，用'.'號表示空白的格子，'x'表示有障礙的格子。

輸出格式： 輸出文件的第一行僅有一個數S，表示需要皇后的數目。 Sample Input 3 4 x... x.x. .x.. Sample Ouput 5

問題分析]

如果本問題用簡單的搜索來做，由于題目給的棋盤很大，搜索算法很難在短時間內出解。由于一個皇后在棋盤最多只能控制兩個格子，因此最少需要的皇后數目的下界為[N*M/2]。要使得皇后數目最少，必定是盡量多的皇后控制兩個格子。如果我們在每兩個能相互攻擊到的格子之間加上一條有向弧，則問題很類似于二分圖的最大匹配問題。

[模型一]

1． 將每個非障礙的格子按行優先編號(0~m*n-1)。 2． 將上述的每個格子i折成兩個格子i'和i''，作為網絡模型中的頂點。 3． 若格子i可以攻擊到格子j且i<j，則在模型中頂點i'到j''之間加上一條有向弧，容量為1。 4． 增加一個源點s，從s點向所有頂點i'添上一條弧；增加一個匯點t，從所有頂點j''到t添上一條弧，容量均為1。

圖1(b)所示的棋盤，對應的模型為：  圖2

顯然，任一解對應于以上模型的一個最大匹配。且最大匹配中，匹配數必定是偶數。因此至少需要的馬匹數為M＊N－障礙數－最大匹配數/2。

[模型二]

如果我們將棋盤涂成黑白相間的格子，則某皇后控制的兩個格子一定是一個是黑格，另一個是白格（如圖3），不妨設這兩個格子中皇后在白格子上。于是，我們將N*M個格子分成兩部分白格與黑格。因此我們可以將模型一優化為：

 圖3

1．將棋盤中的所有格子分成兩個部分，對所有的格子進行編號，每個白格與它能攻擊到的黑格之間（障礙除外）添上一條從白格到黑格的弧，構成一個二分圖。

2．增加一個源點s，從s點向所有非障礙的白格添上一條弧；增加一個匯點t，從所有非障礙的黑格到t添上一條弧。

3．設置所有的弧的流量為1。 圖1(b)所示的棋盤，對應的模型為：

 圖4

[兩種模型的比較]

顯然，模型二的頂點數與邊數大致是模型一的一半。下面是在BP環境下兩種模型的時間效率比較(P166/32M)：

模型一 模型二 

可擴展性 不易打印出一種解 容易打印出一種解

模型二正是根據問題的特殊性（即馬的走法），將網格中的格點分成白與黑兩類，且規定馬只能從白格跳到黑格，從而避免將每個格點折分成兩個點，減少模型的頂點數，同時也大大減少了邊的數目。達到了很好的優化效果。

(二)綜合各種模型的優點，智能選擇模型

有時，同一問題的各種模型各有特色，各有利弊。這種情況下，我們就要綜合考慮各種模型的優缺點，根據測試數據智能地選擇問題的模型。

例2火星探測器（IOI97）

有一個登陸艙（POD），里邊裝有許多障礙物探測車（MEV），將在火星表面著陸。著陸后，探測車離開登陸艙向相距不遠的先期到達的傳送器（Transmitter）移動，MEV一邊移動，一邊采集巖石（ROCK）標品，巖石由第一個訪問到它的MEV所采集，每塊巖石只能被采集一次。但是這之后，其他MEV可以從該處通過。探測車MEV不能通過有障礙的地面。 本題限定探測車MEV只能沿著格子向南或向東從登陸處向傳送器transmitter移動，允許多個探測車MEV在同一時間占據同一位置。

任務：計算出所有探測車的移動途徑，使其送到傳送器的巖石標本的數量最多，且使得所有的探測車都必須到達傳送器。

輸入：

火星表面上的登陸艙POD和傳送器之間的位置用網絡P和Q表示，登陸艙POD的位置為（1，1）點，傳送器的位置在（P，Q）點。

火星上的不同表面用三種不同的數字符號來表示：

0代表平坦無障礙 1代表障礙 2代表石塊。 輸入文件的組成如下：  NumberOfVehicles P Q (X1Y1)(X2Y1)(X3,Y1)…(XP-1Y1)(XPY1) (X1Y2)(X2Y2)(X3,Y2)…(XP-1Y1)(XPY2) (X1Y3)(X2Y3)(X3,Y3)…(XP-1Y3)(XPY3) … (X1YQ-1)(X2YQ-1)(X3,YQ-1)…(XP-1YQ-1)(XPYQ-1) (X1YQ)(X2YQ)(X3,YQ)…(XP-1YQ)(XPYQ) P和Q是網絡的大小；NumberOfVehicles是小于1000的整數，表示由登陸艙POD所開出的探測車的個數。共有Q行數據，每行表示火星表面的一組數據，P和Q都不超過128。

[模型一]

很自然我們以登陸艙的位置為源點，傳送器的位置為匯點。同時某塊巖石由第一個訪問到它的MEV所采集，每塊巖石只能被采集一次。但是這之后，其他MEV可以從該處通過，且允許多個探測車MEV在同一時間占據同一位置。因此我們將地圖中的每個點分成兩個點，即（x,y）à(x,y,0)和(x,y,1)。具體的描述一個火星地圖的網絡模型構造如下：

1． 將網格中的每個非障礙點分成(x,y)兩個點(x,y,0)和(x,y,1)，其中源點s = v(1, 1, 0),匯點t = v(MaxX, MaxY, 1)。

2． 在以上頂點中添加以下三種類型的邊e1,e2,e3，相應地容量和費用分別記為C1、C2、C3以及W1、W2、W3:

u e1 = v(x, y, 0) -> v(x, y, 1),c1 = MaxInt,w1 = 0。 u e2 = v(x, y, 0) -> v(x, y, 1)，c2 = 1，w2 = -1（這里要求(x, y)必須是礦石）  u e3 = v(x, y, 1) -> v(x', y', 0)，c3 = MaxInt,w3 = 0.

其中x'=x+1 y'=y 或x'=x y'=y+1,1 <= x' <= MaxX，1 <= y' <= MaxY，且(x' y')非障礙。

從以上模型中可以看出，在構造的過程中，將地圖上的一個點"拆"成了網絡的兩個節點。添加e1型邊使得每個點可以被多次訪問，而添加e2型邊使得某點上的礦石對于這個網絡，從s到t的一條路徑可以看作是一輛探測車的行動路線。路徑費用就是探測車搜集到的礦石的數目。對于網絡G求流量為NumberOfVehicles的固定最小費用流，可以得到問題的解。

[模型二]

事實上，如果我們只考慮這NumberOfVehicles輛車中每輛車分別依次裝上哪些礦石。則每輛車經過的礦石就是一條流，因此我們以網格中的礦石為網絡的頂點建立以下的網絡流模型。

1. 將網格中的每個起點(網格左上角)能到達，且能從它能到達終點(右下角)的礦石 (x,y)點分成左點(x,y,0)和右點(x,y,1)兩個點，并添加源點s和匯點t。 2. 在以上頂點中添加以下五種類型的邊e1,e2,e3，相應地容量和費用分別記為C1、C2、C3以及W1、W2、W3:

u e1 = v(x, y, 0) -> v(x, y, 1),c1 = 1,w1 = -1。 u e2 = v(x, y, 1) -> v(x', y', 0)，c2 = 1，w2 = 0（礦石點(x, y)可到達礦石點(x',y')）。 u e3 = s -> v(x, y, 0)，c3 = 1,w3 = 0。 u e4 = v(x, y, 1)->t，c4 = 1,w4 = 0。 u e5=S->t,c5=MaxInt,w5=0。

由于每個石塊被折成兩個點，且容量為1，就保證了每個石塊只被取走一次，同時取走一塊石塊就得到-1的費用。因此對以上模型，我們求流量為NumberOfVehicles的最小費用流，就可得到解。

[兩種模型的比較]

1.模型一以網格為頂點，模型二以礦石為頂點，因此在頂點個數上模型二明顯優于模型一，對于一些礦石比較稀疏，而網格又比較大的數據，模型二的效率要比模型一來得高。且只要礦石的個數不超過一定數目，模型二可以處理P，Q很大的數據，而模型一卻不行。

2．模型一中邊的數目最多為3*P*Q，而模型二中邊的數目最壞情況下大約為p*q*(p+1)*(q+1)/4-p*q。因此在這個問題中，若對于一些礦石比較密集且網格又比較大的數據，模型二的邊數將大大超過模型一，從而使得時間效率大大低于模型一。

下面是網格中都是礦石的情況比較（PIII700/128M ，BP7.0保護模式）： NumberOfVehicles＝10 模型一 模型二

通過以上數據，可知對于P，Q不超過60的情況，模型一都能在10秒內出解。而模型二則對于P、Q＝30的最壞情況下速度就很慢了，且P、Q超過30后就出現內存溢出情況，而無法解決。

因此，對于本題，以上兩種模型各有利弊，我們可根據測試數據中礦石稀疏程度來決定建立什么樣的模型。若礦石比較稀疏，則可以考慮用建立如模型二的網絡模型；若礦石比較密集則建立模型一所示網絡模型。然后，再應用求最小費用最大流算法求解。對于P，Q＞60，且礦石比較多情況下，兩種模型的網絡流算法都無法求解。在實際的應用中問題經常都只要求近似解，此時還可用綜合一些其它算法來求解。

四、結束語

綜上所述，網絡流算法中模型的優化是網絡流算法提高效率的根本。我們要根據實際問題，從減少頂點及邊的角度綜合考慮如何對模型進行優化，選擇適當的模型，以提高算法的效率。對于有些題目，解題的各種模型各有優劣時，還可通過程序自動分析測試數據，以決定何種情況下采用何種模型，充分發揮各種模型的優點，以達到優化程序效率的目的。

[參考文獻]

潘金貴、顧鐵成等，《現代計算機常用數據結構和算法》，南京大學出版社，1994 [1] 吳文虎王建德編著，《實用算法的分析與程序設計》，電子工業出版社，1998

[作者簡介] 本人于1970年11月生，1992年7月畢業于福建師大數學系電子計算機專業，2000年6月畢業福建師范大學數學系數學專業（本科），97年12月被確認為中學一級教師，現任計算機教研組組長。1996年參與指導學生陳磊參加國際信息學奧賽，獲金牌，1997年獲銅牌；1999、2000年參與指導學生陳宏，在國際信息學奧賽中獲金牌。 2000.6參與編寫《金牌之路--高中計算機競賽輔導》一書，由陜西師范大學出版社出版。2000.9參與編寫青少年信息學奧林匹克競賽叢書《Pascal程序設計基礎》，由福建科學技術出版社出版。2001參與編寫福建省中學《信息技術》第二冊，由福建教育出版社出版。

     

【試論網絡流算法中模型的優化與選擇】相關文章：

試論網絡漢字詞的造詞研究08-18

試論語文教學中的美育08-22

試論美術課程中的故事引入08-19

試論中等職業學校班主任工作的優化策略08-17

試論校友資源在高校發展中的作用08-27

試論城市發展中社會和諧的制約與促進08-15

聚類算法及其在護理管理中的應用研究08-18

試論多媒體技術在生物實驗課中的實踐08-25

試論在企業人事勞資管理中的思想政治素養08-24

試論高中體育課堂中的激趣教學08-24