- 相關(guān)推薦
試論網(wǎng)絡(luò)流算法中模型的優(yōu)化與選擇
試論網(wǎng)絡(luò)流算法中模型的優(yōu)化與選擇
福建師大附中 周 成[內(nèi)容摘要] 近年來，在國內(nèi)信息學競賽（尤其是國家隊選拔賽）、國際信息學競賽中，多次出現(xiàn)應用網(wǎng)絡(luò)流算法求解的試題，網(wǎng)絡(luò)流算法已是信息學奧賽選手必須掌握的算法。本文主要探討不同網(wǎng)絡(luò)模型的構(gòu)造對問題解決的效率的影響，以及如何優(yōu)化網(wǎng)絡(luò)模型，提高算法的效率。
[關(guān)鍵詞] 網(wǎng)絡(luò)流，模型，優(yōu)化，選擇。
一、引言
網(wǎng)絡(luò)流算法是一種高效實用的算法，相對于其它圖論算法來說，它的模型更加復雜，編程復雜度也更高。但是它綜合了圖論中的其它一些算法（如最短路徑、寬度搜索算法），因而適用范圍也更廣，經(jīng)常能夠很好地解決一些搜索與動態(tài)規(guī)劃無法解決的非NP問題。 網(wǎng)絡(luò)流在具體問題中的應用，最具挑戰(zhàn)性的部分是模型的構(gòu)造，它沒用現(xiàn)成的模式可以套用，需要我們對各種網(wǎng)絡(luò)流的性質(zhì)了如指掌（比如點有容量、容量有上下限、多重邊等等），根據(jù)具體的問題發(fā)揮我們的創(chuàng)造性。一道問題經(jīng)常可以建立多種模型，不同的模型對問題的解決效率的影響也是不同的，本文通過實例探討如何確定適當?shù)哪Ｐ停岣呔W(wǎng)絡(luò)流算法的效率。
二、網(wǎng)絡(luò)流算法時間效率
當我們確定問題可以使用最大流算法求解后，就根據(jù)常用的Ford-Fulkerson標號法求解；而最�。ù螅┵M用最大流問題也可用類似標號法的對偶算法解題。Ford-Fulkerson標號法的運行時間為O（VE2），對偶法求最小費用流的運行時間大約為O（V3E2）。
顯然，影響網(wǎng)絡(luò)流算法的時間效率的因素主要是網(wǎng)絡(luò)中頂點的數(shù)目與邊的數(shù)目。這二個因素之間不是相互獨立的，而是相互聯(lián)系，矛盾而統(tǒng)一的。在構(gòu)造網(wǎng)絡(luò)模型中，有時，實現(xiàn)了某個因素的優(yōu)化，另外一個因素也隨之得到了優(yōu)化；有時，實現(xiàn)某個因素的優(yōu)化卻要以增大另一因素為代價。因此，我們在具體問題的解決中，要堅持"全局觀"，實現(xiàn)二者的平衡。
三、模型的優(yōu)化與選擇
(一)減少模型的頂點數(shù)與邊數(shù)，優(yōu)化模型
如果能根據(jù)問題的一些特殊性質(zhì)，減少網(wǎng)絡(luò)模型中的頂點的數(shù)目和邊的數(shù)目，則可以大大提高算法的效率。
例1：最少皇后控制
在國際象棋中，皇后能向八個方向攻擊（如圖1(a)所示，圖中黑點格子為皇后的位置，標有K的格子為皇后可攻擊到的格子）。現(xiàn)在給定一個M*N（N、M均不大于于50）的棋盤，棋盤上某些格子有障礙。每個皇后被放置在無障礙的格子中，它就控制了這個格子，除此，它可以從它能攻擊到的最多8個格子中選一個格子來控制，如圖1(b)所示，標號為1的格子被一個皇后所控制。
請你編一程序，計算出至少有多少個皇后才能完全控制整個棋盤。
圖1(a) 圖1(b)輸入格式： 輸入文件的第一行有兩個整數(shù)M和N，表示棋盤的行數(shù)與列數(shù)。接下來M行N列為一個字符矩陣，用'.'號表示空白的格子，'x'表示有障礙的格子。
輸出格式： 輸出文件的第一行僅有一個數(shù)S，表示需要皇后的數(shù)目。 Sample Input 3 4 x... x.x. .x.. Sample Ouput 5
問題分析]
如果本問題用簡單的搜索來做，由于題目給的棋盤很大，搜索算法很難在短時間內(nèi)出解。由于一個皇后在棋盤最多只能控制兩個格子，因此最少需要的皇后數(shù)目的下界為[N*M/2]。要使得皇后數(shù)目最少，必定是盡量多的皇后控制兩個格子。如果我們在每兩個能相互攻擊到的格子之間加上一條有向弧，則問題很類似于二分圖的最大匹配問題。
[模型一]
1． 將每個非障礙的格子按行優(yōu)先編號(0~m*n-1)。 2． 將上述的每個格子i折成兩個格子i'和i''，作為網(wǎng)絡(luò)模型中的頂點。 3． 若格子i可以攻擊到格子j且i<j，則在模型中頂點i'到j(luò)''之間加上一條有向弧，容量為1。 4． 增加一個源點s，從s點向所有頂點i'添上一條�。辉黾右粋�匯點t，從所有頂點j''到t添上一條弧，容量均為1。
圖1(b)所示的棋盤，對應的模型為： 圖2顯然，任一解對應于以上模型的一個最大匹配。且最大匹配中，匹配數(shù)必定是偶數(shù)。因此至少需要的馬匹數(shù)為M＊N－障礙數(shù)－最大匹配數(shù)/2。
[模型二]
如果我們將棋盤涂成黑白相間的格子，則某皇后控制的兩個格子一定是一個是黑格，另一個是白格（如圖3），不妨設(shè)這兩個格子中皇后在白格子上。于是，我們將N*M個格子分成兩部分白格與黑格。因此我們可以將模型一優(yōu)化為：
圖31．將棋盤中的所有格子分成兩個部分，對所有的格子進行編號，每個白格與它能攻擊到的黑格之間（障礙除外）添上一條從白格到黑格的弧，構(gòu)成一個二分圖。
2．增加一個源點s，從s點向所有非障礙的白格添上一條�。辉黾右粋�匯點t，從所有非障礙的黑格到t添上一條弧。
3．設(shè)置所有的弧的流量為1。 圖1(b)所示的棋盤，對應的模型為：
圖4[兩種模型的比較]
顯然，模型二的頂點數(shù)與邊數(shù)大致是模型一的一半。下面是在BP環(huán)境下兩種模型的時間效率比較(P166/32M)：
模型一 模型二
可擴展性 不易打印出一種解 容易打印出一種解
模型二正是根據(jù)問題的特殊性（即馬的走法），將網(wǎng)格中的格點分成白與黑兩類，且規(guī)定馬只能從白格跳到黑格，從而避免將每個格點折分成兩個點，減少模型的頂點數(shù)，同時也大大減少了邊的數(shù)目。達到了很好的優(yōu)化效果。
(二)綜合各種模型的優(yōu)點，智能選擇模型
有時，同一問題的各種模型各有特色，各有利弊。這種情況下，我們就要綜合考慮各種模型的優(yōu)缺點，根據(jù)測試數(shù)據(jù)智能地選擇問題的模型。
例2火星探測器（IOI97）
有一個登陸艙（POD），里邊裝有許多障礙物探測車（MEV），將在火星表面著陸。著陸后，探測車離開登陸艙向相距不遠的先期到達的傳送器（Transmitter）移動，MEV一邊移動，一邊采集巖石（ROCK）標品，巖石由第一個訪問到它的MEV所采集，每塊巖石只能被采集一次。但是這之后，其他MEV可以從該處通過。探測車MEV不能通過有障礙的地面。 本題限定探測車MEV只能沿著格子向南或向東從登陸處向傳送器transmitter移動，允許多個探測車MEV在同一時間占據(jù)同一位置。
任務：計算出所有探測車的移動途徑，使其送到傳送器的巖石標本的數(shù)量最多，且使得所有的探測車都必須到達傳送器。
輸入：
火星表面上的登陸艙POD和傳送器之間的位置用網(wǎng)絡(luò)P和Q表示，登陸艙POD的位置為（1，1）點，傳送器的位置在（P，Q）點。
火星上的不同表面用三種不同的數(shù)字符號來表示：
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是網(wǎng)絡(luò)的大��；NumberOfVehicles是小于1000的整數(shù)，表示由登陸艙POD所開出的探測車的個數(shù)。共有Q行數(shù)據(jù)，每行表示火星表面的一組數(shù)據(jù)，P和Q都不超過128。
[模型一]
很自然我們以登陸艙的位置為源點，傳送器的位置為匯點。同時某塊巖石由第一個訪問到它的MEV所采集，每塊巖石只能被采集一次。但是這之后，其他MEV可以從該處通過，且允許多個探測車MEV在同一時間占據(jù)同一位置。因此我們將地圖中的每個點分成兩個點，即（x,y）à(x,y,0)和(x,y,1)。具體的描述一個火星地圖的網(wǎng)絡(luò)模型構(gòu)造如下：
1． 將網(wǎng)格中的每個非障礙點分成(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')非障礙。
從以上模型中可以看出，在構(gòu)造的過程中，將地圖上的一個點"拆"成了網(wǎng)絡(luò)的兩個節(jié)點。添加e1型邊使得每個點可以被多次訪問，而添加e2型邊使得某點上的礦石對于這個網(wǎng)絡(luò)，從s到t的一條路徑可以看作是一輛探測車的行動路線。路徑費用就是探測車搜集到的礦石的數(shù)目。對于網(wǎng)絡(luò)G求流量為NumberOfVehicles的固定最小費用流，可以得到問題的解。
[模型二]
事實上，如果我們只考慮這NumberOfVehicles輛車中每輛車分別依次裝上哪些礦石。則每輛車經(jīng)過的礦石就是一條流，因此我們以網(wǎng)格中的礦石為網(wǎng)絡(luò)的頂點建立以下的網(wǎng)絡(luò)流模型。
1. 將網(wǎng)格中的每個起點(網(wǎng)格左上角)能到達，且能從它能到達終點(右下角)的礦石 (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.模型一以網(wǎng)格為頂點，模型二以礦石為頂點，因此在頂點個數(shù)上模型二明顯優(yōu)于模型一，對于一些礦石比較稀疏，而網(wǎng)格又比較大的數(shù)據(jù)，模型二的效率要比模型一來得高。且只要礦石的個數(shù)不超過一定數(shù)目，模型二可以處理P，Q很大的數(shù)據(jù)，而模型一卻不行。
2．模型一中邊的數(shù)目最多為3*P*Q，而模型二中邊的數(shù)目最壞情況下大約為p*q*(p+1)*(q+1)/4-p*q。因此在這個問題中，若對于一些礦石比較密集且網(wǎng)格又比較大的數(shù)據(jù)，模型二的邊數(shù)將大大超過模型一，從而使得時間效率大大低于模型一。
下面是網(wǎng)格中都是礦石的情況比較（PIII700/128M ，BP7.0保護模式）： NumberOfVehicles＝10 模型一 模型二
通過以上數(shù)據(jù)，可知對于P，Q不超過60的情況，模型一都能在10秒內(nèi)出解。而模型二則對于P、Q＝30的最壞情況下速度就很慢了，且P、Q超過30后就出現(xiàn)內(nèi)存溢出情況，而無法解決。
因此，對于本題，以上兩種模型各有利弊，我們可根據(jù)測試數(shù)據(jù)中礦石稀疏程度來決定建立什么樣的模型。若礦石比較稀疏，則可以考慮用建立如模型二的網(wǎng)絡(luò)模型；若礦石比較密集則建立模型一所示網(wǎng)絡(luò)模型。然后，再應用求最小費用最大流算法求解。對于P，Q＞60，且礦石比較多情況下，兩種模型的網(wǎng)絡(luò)流算法都無法求解。在實際的應用中問題經(jīng)常都只要求近似解，此時還可用綜合一些其它算法來求解。
四、結(jié)束語
綜上所述，網(wǎng)絡(luò)流算法中模型的優(yōu)化是網(wǎng)絡(luò)流算法提高效率的根本。我們要根據(jù)實際問題，從減少頂點及邊的角度綜合考慮如何對模型進行優(yōu)化，選擇適當?shù)哪Ｐ停蕴岣咚惴ǖ男�。對于有些題目，解題的各種模型各有優(yōu)劣時，還可通過程序自動分析測試數(shù)據(jù)，以決定何種情況下采用何種模型，充分發(fā)揮各種模型的優(yōu)點，以達到優(yōu)化程序效率的目的。
[參考文獻]
潘金貴、顧鐵成等，《現(xiàn)代計算機常用數(shù)據(jù)結(jié)構(gòu)和算法》，南京大學出版社，1994 [1] 吳文虎王建德編著，《實用算法的分析與程序設(shè)計》，電子工業(yè)出版社，1998
[作者簡介] 本人于1970年11月生，1992年7月畢業(yè)于福建師大數(shù)學系電子計算機專業(yè)，2000年6月畢業(yè)福建師范大學數(shù)學系數(shù)學專業(yè)（本科），97年12月被確認為中學一級教師，現(xiàn)任計算機教研組組長。1996年參與指導學生陳磊參加國際信息學奧賽，獲金牌，1997年獲銅牌；1999、2000年參與指導學生陳宏，在國際信息學奧賽中獲金牌。 2000.6參與編寫《金牌之路--高中計算機競賽輔導》一書，由陜西師范大學出版社出版。2000.9參與編寫青少年信息學奧林匹克競賽叢書《Pascal程序設(shè)計基礎(chǔ)》，由福建科學技術(shù)出版社出版。2001參與編寫福建省中學《信息技術(shù)》第二冊，由福建教育出版社出版。
【試論網(wǎng)絡(luò)流算法中模型的優(yōu)化與選擇】相關(guān)文章：
試論語文教學中的美育08-22
試論美術(shù)課程中的故事引入08-19
試論中等職業(yè)學校班主任工作的優(yōu)化策略08-17
試論校友資源在高校發(fā)展中的作用08-27
聚類算法及其在護理管理中的應用研究08-18
試論在企業(yè)人事勞資管理中的思想政治素養(yǎng)08-24
試論高中體育課堂中的激趣教學08-24