試論網絡流算法中模型的優化與選擇

時間：2023-04-30 22:38:19 教育論文我要投稿

相關推薦

試論網絡流算法中模型的優化與選擇

福建師大附中周成

[內容摘要] 近年來，在國內信息學競賽（尤其是國家隊選拔賽）、國際信息學競賽中，多次出現應用網絡流算法求解的試題，網絡流算法已是信息學奧賽選手必須掌握的算法。本文主要探討不同網絡模型的構造對問題解決的效率的影響，以及如何優化網絡模型，提高算法的效率。

[關鍵詞] 網絡流，模型，優化，選擇。

一、引言

網絡流算法是一種高效實用的算法，相對于其它圖論算法來說，它的模型更加復雜，編程復雜度也更高。但是它綜合了圖論中的其它一些算法（如最短路徑、寬度搜索算法），因而適用范圍也更廣，經常能夠很好地解決一些搜索與動態規劃無法解決的非NP問題。

網絡流在具體問題中的應用，最具挑戰性的部分是模型的構造，它沒用現成的模式可以套用，需要我們對各種網絡流的性質了如指掌（比如點有容量、容量有上下限、多重邊等等），根據具體的問題發揮我們的創造性。一道問題經常可以建立多種模型，不同的模型對問題的解決效率的影響也是不同的，本文通過實例探討如何確定適當的模型，提高網絡流算法的效率。

二、網絡流算法時間效率

當我們確定問題可以使用最大流算法求解后，就根據常用的Ford-Fulkerson標號法求解；而最小（大）費用最大流問題也可用類似標號法的對偶算法解題。Ford-Fulkerson標號法的運行時間為O（VE2），對偶法求最小費用流的運行時間大約為O（V3E2）。

顯然，影響網絡流算法的時間效率的因素主要是網絡中頂點的數目與邊的數目。這二個因素之間不是相互獨立的，而是相互聯系，矛盾而統一的。在構造網絡模型中，有時，實現了某個因素的優化，另外一個因素也隨之得到了優化；有時，實現某個因素的優化卻要以增大另一因素為代價。因此，我們在具體問題的解決中，要堅持"全局觀"，實現二者的平衡。

三、模型的優化與選擇

(一)減少模型的頂點數與邊數，優化模型

如果能根據問題的一些特殊性質，減少網絡模型中的頂點的數目和邊的數目，則可以大大提高算法的效率。

例1：最少皇后控制

在國際象棋中，皇后能向八個方向攻擊（如圖1(a)所示，圖中黑點格子為皇后的位置，標有K的格子為皇后可攻擊到的格子）。現在給定一個M*N（N、M均不大于于50）的棋盤，棋盤上某些格子有障礙。每個皇后被放置在無障礙的格子中，它就控制了這個格子，除此，它可以從它能攻擊到的最多8個格子中選一個格子來控制，如圖1(b)所示，標號為1的格子被一個皇后所控制。

請你編一程序，計算出至少有多少個皇后才能完全控制整個棋盤。

圖1(a) 圖1(b)

輸入格式：

輸入文件的第一行有兩個整數M和N，表示棋盤的行數與列數。接下來M行N列為一個字符矩陣，用'.'號表示空白的格子，'x'表示有障礙的格子。

輸出格式：

輸出文件的第一行僅有一個數S，表示需要皇后的數目。

Sample Input

3 4

x...

x.x.

.x..

Sample Ouput