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