算法合集之用改進算法思想解決規(guī)模維數(shù)增大問題-文庫吧
2025-05-26 01:38 本頁面
【正文】 解決，只需要加一維狀態(tài)變量就成了。即用分別表示兩條路徑走到階段k時所處的位置，相應的，決策變量也增加一維，用分別表示兩條路徑的行走方向。狀態(tài)轉移時將兩條路徑分別考慮：【小結】從這個例子可以看出，改進的時候不能只依靠原始算法，還要分析原始算法的本質。(2)用枚舉處理增加的規(guī)模，從而解決問題【例二】旅行（廣東省奧林匹克競賽2001）【題目大意】給出一個NM的數(shù)字矩陣，要求這個矩陣的一個子矩陣，并要求這個子矩陣的數(shù)字和最大?！締栴}分析】初一看題目，想到枚舉每一個子矩陣，求出子矩陣的和，比較得出最大值。這樣，時間復雜度達到O(N4)，顯然不可以接受。因為它是兩維的問題，我們可以嘗試著把維數(shù)降低。先看一維時候的情況：在數(shù)列ai中找出和最大的一段。對于一維的子問題，可以這樣來想：如果用最基本的方法，可以枚舉每個子序列。但是如果純粹三重循環(huán)，枚舉頭，枚舉尾，枚舉中間求和，顯然是太浪費了。其實我們計算Si,j ()時，可以由獲得。這樣，動態(tài)規(guī)劃的思路就明顯了，Si,j與Si1,j有直接的關系，而且我們還可以發(fā)現(xiàn)Si,*（表示從Si,1到Si,i1構成的數(shù)列）只比Si1,*多了一項。于是簡單的動態(tài)規(guī)劃就出來了，用fi表示以i為終點的數(shù)列的最大和，有：不過，我們得到的只是子問題的算法，如何改進算法能使它適用于矩陣的問題呢？我們需要找出矩陣和數(shù)列的關系：矩陣是若干條數(shù)列，但是它又不僅僅是簡單的若干條數(shù)列，不同數(shù)列中的相同位置的數(shù)也構成了聯(lián)系。我們可以嘗試著構造上下、左右同時進行的動態(tài)規(guī)劃，但是也許我們無能為力。對于這道題的數(shù)據(jù)規(guī)模，似乎沒有必要構造O(N2)時間的算法。不難想到，枚舉上下方向的數(shù)列和，在左右方向用動態(tài)規(guī)劃求解，可以得到時間復雜度在O(N3)的算法。【小結】在這個例題中，我們用了最簡單的方法——枚舉，來改進一維數(shù)列的最大子序列的解法，從而解決問題的規(guī)模的增加。但是枚舉這個簡單的方法，卻能解決很復雜的問題?！纠颗诒嚨亍＃∟OI2001）【題目大意】在圖中標為P的格子中放炮兵，如圖灰色區(qū)域放了炮兵后，黑色區(qū)域不能放炮兵，問圖中最多能放多少炮兵？【問題分析】簡化的問題：若只有一列，問最多可以放多少炮兵?？梢杂秘澬?，盡量把炮兵往上放，也可以這樣遞推：用fi表示前i行最多能放炮兵數(shù)，ai表示第i行的地形，則邊界條件：，動態(tài)規(guī)劃方程：但是當問題擴展到多列的情況，就復雜了：不僅要考慮一列是否能引用上一行的函數(shù)值，而且要多列同時考慮。但是容易觀察到，mn，最大只有10，又因為炮兵攻擊范圍很大，實際上能放炮兵的組合數(shù)很小，可以考慮枚舉組合，從而得到改進的動態(tài)規(guī)劃方法：以兩行為一個狀態(tài)，s1表示狀態(tài)中上行的炮兵布置情況，s2表示下行的布置情況，（可以預先枚舉所有可能的情況并給這些情況標號）當?shù)趇行能不能布置s1或第i+1行不能布置s2時，或者s1,s2在同一位置布置了炮兵時，都是不符合情況的，令此時；否則：，其中counts2表示s2的炮兵個數(shù)；s表示該s1,s2的前一行的炮兵布置情況，而且滿足：不存在這樣的j。這樣到最后的最優(yōu)解就是最終復雜度分析，時間復雜度大約O(R3n)（R是一行狀態(tài)的組合數(shù)）(3)用貪心解決增加的規(guī)模，從而解決問題【例四】求網絡的最小費用最大流。（經典問題）顯然，求最小費用最大流可以由求最大流的算法改進。求網絡的最大流，簡單地說來，是每次尋找一條連接源點和匯點的可增廣路徑并由之擴充網絡流，直到不存在這樣可增廣路徑，則得出最大流。那么，又如何把費用也考慮進去呢？我們先來看看網絡的費用的定義吧。網絡的費用一般是指在每一段弧上弧的費用與弧的流量的乘積的和。（弧的費用由可能為負）所以網絡的最小費用最大流是指可行流中費用最小的。不難看出，可行流每增加1，所增加的費用都應該是最小的（事實上應該是減小得最多的）。這樣可以得出一個改進：每次選取一條費用最?。ǘ曳钦┑目稍鰪V路徑，直到最終不存在費用非正的可增廣路徑。這樣用貪心的策略就能解決問題了。(4)多種途徑的綜合運用【例五】Team Selection (Balkan OI 2004 Day1)【題目大意】IOI要來了，BP隊要選擇最好的選手去參加。幸運地，教練可以從N個非常棒的選手中選擇隊員，這些選手被標上1到N(3 ≤ N ≤ 500000)。為了選出的選手是最好的，教練組織了三次競賽并給出每次競賽排名。每個選手都參加了每次競賽并且每次競賽都沒有并列的。當A在所有競賽中名次都比B前，我們就說A是比B better。如果沒有人比A better，我們就說A是excellent。求excellent選手的個數(shù)。如數(shù)據(jù)：則excellent選手是1，2，3，5?！驹妓悸贰恳荒玫竭@一題，很容易會有以下的思路?！荚妓惴ā降谝谎劭吹竭@道題往往想到枚舉。簡單地根據(jù)better和excellent的定義，現(xiàn)只需要枚舉每一個選手X，判斷X是否excellent。這可以通過另一重循環(huán)，枚舉另一選手Y，判斷Y是否比X better。判斷是容易的，我們只需要簡單地判斷X和Y的三次排名。因此這一算法的時間復雜度是O(N2)，對于這道題，不能滿足要求。主要流程1： for(X從1到N) for(Y從1到N) 判斷Y是否比X better〖改進一〗原始算法是可以改進的。不難看出，如果讓X依照第一次競賽的名次循環(huán)，枚舉Y時只需要枚舉在第一次競賽中排在X前面選手即可，因為第一次競賽排在X后的選手一定不可能比X better。不過這樣小的改進提起來只是開闊開闊思路，它對時間復雜度不會有太大影響。主要流程2： for(X從第一次競賽的第1名到第一次競賽的第N名) for(Y從第一次競賽的第1名到第一次競賽的第(X1)名) 判斷Y是否比X better〖改進
教學教案相關推薦
鄂ICP備17016276號-1