- 相關(guān)推薦
試論網(wǎng)絡(luò)流算法中模型的優(yōu)化與選擇
試論網(wǎng)絡(luò)流算法中模型的優(yōu)化與選擇
福建師大附中 周 成[內(nè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ì)問題解決的效率的影響，以及如何優(yōu)化網(wǎng)絡(luò)模型，提高算法的效率。
[關(guān)鍵詞] 網(wǎng)絡(luò)流，模型，優(yōu)化，選擇。
一、引言
網(wǎng)絡(luò)流算法是一種高效實(shí)用的算法，相對(duì)于其它圖論算法來說，它的模型更加復(fù)雜，編程復(fù)雜度也更高。但是它綜合了圖論中的其它一些算法（如最短路徑、寬度搜索算法），因而適用范圍也更廣，經(jīng)常能夠很好地解決一些搜索與動(dòng)態(tài)規(guī)劃無(wú)法解決的非NP問題。
網(wǎng)絡(luò)流在具體問題中的應(yīng)用，最具挑戰(zhàn)性的部分是模型的構(gòu)造，它沒用現(xiàn)成的模式可以套用，需要我們對(duì)各種網(wǎng)絡(luò)流的性質(zhì)了如指掌（比如點(diǎn)有容量、容量有上下限、多重邊等等），根據(jù)具體的問題發(fā)揮我們的創(chuàng)造性。一道問題經(jīng)�？梢越⒍喾N模型，不同的模型對(duì)問題的解決效率的影響也是不同的，本文通過實(shí)例探討如何確定適當(dāng)?shù)哪Ｐ停岣呔W(wǎng)絡(luò)流算法的效率。
二、網(wǎng)絡(luò)流算法時(shí)間效率
當(dāng)我們確定問題可以使用最大流算法求解后，就根據(jù)常用的Ford-Fulkerson標(biāo)號(hào)法求解；而最�。ù螅┵M(fè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問題的解決中，要堅(jiān)持"全局觀"，實(shí)現(xiàn)二者的平衡。
三、模型的優(yōu)化與選擇
(一)減少模型的頂點(diǎn)數(shù)與邊數(shù)，優(yōu)化模型
如果能根據(jù)問題的一些特殊性質(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）的棋盤，棋盤上某些格子有障礙。每個(gè)皇后被放置在無(wú)障礙的格子中，它就控制了這個(gè)格子，除此，它可以從它能攻擊到的最多8個(gè)格子中選一個(gè)格子來控制，如圖1(b)所示，標(biāo)號(hào)為1的格子被一個(gè)皇后所控制。
請(qǐng)你編一程序，計(jì)算出至少有多少個(gè)皇后才能完全控制整個(gè)棋盤。
圖1(a) 圖1(b)
輸入格式：
輸入文件的第一行有兩個(gè)整數(shù)M和N，表示棋盤的行數(shù)與列數(shù)。接下來M行N列為一個(gè)字符矩陣，用'.'號(hào)表示空白的格子，'x'表示有障礙的格子。
輸出格式：
輸出文件的第一行僅有一個(gè)數(shù)S，表示需要皇后的數(shù)目。
Sample Input
3 4
x...
x.x.
.x..
Sample Ouput
5
問題分析]
如果本問題用簡(jiǎn)單的搜索來做，由于題目給的棋盤很大，搜索算法很難在短時(shí)間內(nèi)出解。由于一個(gè)皇后在棋盤最多只能控制兩個(gè)格子，因此最少需要的皇后數(shù)目的下界為[N*
[1] [2] [3] [4]
【試論網(wǎng)絡(luò)流算法中模型的優(yōu)化與選擇】相關(guān)文章：
企業(yè)分銷網(wǎng)絡(luò)的優(yōu)化模型04-30
人工神經(jīng)網(wǎng)絡(luò)優(yōu)化模型在洪水預(yù)報(bào)中的應(yīng)用05-01
軌道交通隨機(jī)均衡配流模型和算法05-02
基于粒子群優(yōu)化算法的本構(gòu)模型參數(shù)識(shí)別04-30
基于蟻群算法的鐵路空車調(diào)整優(yōu)化模型設(shè)計(jì)04-30
粒子群優(yōu)化算法及其在結(jié)構(gòu)優(yōu)化設(shè)計(jì)中的應(yīng)用04-30
RBF網(wǎng)絡(luò)用于邊界層轉(zhuǎn)捩中抽吸流優(yōu)化控制04-28
網(wǎng)絡(luò)經(jīng)濟(jì)最優(yōu)化模型研究05-02
基于B-P神經(jīng)網(wǎng)絡(luò)優(yōu)化算法的城市環(huán)境空氣中PM10濃度預(yù)測(cè)模型04-25