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