- 相關(guān)推薦
試論網(wǎng)絡(luò)流算法中模型的優(yōu)化與選擇
試論網(wǎng)絡(luò)流算法中模型的優(yōu)化與選擇
福建師大附中 周 成[內(nèi)容摘要] 近年來，在國內(nèi)信息學(xué)競賽（尤其是國家隊選拔賽）、國際信息學(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ò)流算法是一種高效實用的算法，相對于其它圖論算法來說，它的模型更加復(fù)雜，編程復(fù)雜度也更高。但是它綜合了圖論中的其它一些算法（如最短路徑、寬度搜索算法），因而適用范圍也更廣，經(jīng)常能夠很好地解決一些搜索與動態(tài)規(guī)劃無法解決的非NP問題。
網(wǎng)絡(luò)流在具體問題中的應(yīng)用，最具挑戰(zhàn)性的部分是模型的構(gòu)造，它沒用現(xiàn)成的模式可以套用，需要我們對各種網(wǎng)絡(luò)流的性質(zhì)了如指掌（比如點有容量、容量有上下限、多重邊等等），根據(jù)具體的問題發(fā)揮我們的創(chuàng)造性。一道問題經(jīng)常可以建立多種模型，不同的模型對問題的解決效率的影響也是不同的，本文通過實例探討如何確定適當(dāng)?shù)哪Ｐ�，提高網(wǎng)絡(luò)流算法的效率。
二、網(wǎng)絡(luò)流算法時間效率
當(dāng)我們確定問題可以使用最大流算法求解后，就根據(jù)常用的Ford-Fulkerson標(biāo)號法求解；而最�。ù螅┵M用最大流問題也可用類似標(biāo)號法的對偶算法解題。Ford-Fulkerson標(biāo)號法的運行時間為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)所示，圖中黑點格子為皇后的位置，標(biāo)有K的格子為皇后可攻擊到的格子）�，F(xiàn)在給定一個M*N（N、M均不大于于50）的棋盤，棋盤上某些格子有障礙。每個皇后被放置在無障礙的格子中，它就控制了這個格子，除此，它可以從它能攻擊到的最多8個格子中選一個格子來控制，如圖1(b)所示，標(biāo)號為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*
[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ù)報中的應(yīng)用05-01
軌道交通隨機(jī)均衡配流模型和算法05-02
基于粒子群優(yōu)化算法的本構(gòu)模型參數(shù)識別04-30
基于蟻群算法的鐵路空車調(diào)整優(yōu)化模型設(shè)計04-30
粒子群優(yōu)化算法及其在結(jié)構(gòu)優(yōu)化設(shè)計中的應(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ù)測模型04-25