算法合集之用改進算法思想解決規(guī)模維數(shù)增大問題-預(yù)覽頁
【正文】 大的問題。（經(jīng)典問題） 3(2)用枚舉處理增加的規(guī)模，從而解決問題 4【例二】旅行（廣東省奧林匹克競賽2001） 4【例三】炮兵陣地。有的時候我們分析到某個問題好像可以用某種方法解決，但是這個問題卻與之前見過的問題有些不同，例如本文所討論的情況：問題的規(guī)模維數(shù)比原問題大，一維的變二維的，二維的變?nèi)S的，等等。A模型顯然是不可能成立的；B、C模型的共同點是：我們必須使一根香的計時減小。方案已經(jīng)更進一步了。特別地，當(dāng)t=60min時，t/2=30min。主要流程是：1. 找出原始解法和可能改進的方向（即分析成A、B、C模型）；2. 分析算法的原理（由燒一根香計時半小時，引申為燒剩t的時候點兩頭就能計時）；3. 改進算法（改進的過程中，往往不是依靠算法改進算法本身，反而是利用算法的內(nèi)涵、實質(zhì)，結(jié)合問題，構(gòu)造算法）；4. 解決問題（我們得出了正確的解法）。（經(jīng)典問題）【題目大意】〖原題〗在右圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走。我們來分析一下原方法的實質(zhì)：按照圖中的斜線來劃分階段，即階段變量k表示走過的步數(shù)，而狀態(tài)變量xk表示當(dāng)前處于這一階段上的哪一點。即用分別表示兩條路徑走到階段k時所處的位置，相應(yīng)的，決策變量也增加一維，用分別表示兩條路徑的行走方向。這樣，時間復(fù)雜度達到O(N4)，顯然不可以接受。但是如果純粹三重循環(huán)，枚舉頭，枚舉尾，枚舉中間求和，顯然是太浪費了。我們可以嘗試著構(gòu)造上下、左右同時進行的動態(tài)規(guī)劃，但是也許我們無能為力。但是枚舉這個簡單的方法，卻能解決很復(fù)雜的問題。但是容易觀察到，mn，最大只有10，又因為炮兵攻擊范圍很大，實際上能放炮兵的組合數(shù)很小，可以考慮枚舉組合，從而得到改進的動態(tài)規(guī)劃方法：以兩行為一個狀態(tài)，s1表示狀態(tài)中上行的炮兵布置情況，s2表示下行的布置情況，（可以預(yù)先枚舉所有可能的情況并給這些情況標(biāo)號）當(dāng)?shù)趇行能不能布置s1或第i+1行不能布置s2時，或者s1,s2在同一位置布置了炮兵時，都是不符合情況的，令此時；否則：，其中counts2表示s2的炮兵個數(shù)；s表示該s1,s2的前一行的炮兵布置情況，而且滿足：不存在這樣的j。那么，又如何把費用也考慮進去呢？我們先來看看網(wǎng)絡(luò)的費用的定義吧。這樣可以得出一個改進：每次選取一條費用最?。ǘ曳钦┑目稍鰪V路徑，直到最終不存在費用非正的可增廣路徑。為了選出的選手是最好的，教練組織了三次競賽并給出每次競賽排名。求excellent選手的個數(shù)。簡單地根據(jù)better和excellent的定義，現(xiàn)只需要枚舉每一個選手X，判斷X是否excellent。主要流程1： for(X從1到N) for(Y從1到N) 判斷Y是否比X better〖改進一〗原始算法是可以改進的。我們發(fā)現(xiàn)：如果Y不是excellent（因為有Z比Y better），當(dāng)我們檢查X是否excellent時，我們檢查了Z是否比X better的話，可以不檢查Y。主要流程3： for(X從第一次競賽的第1名到第一次競賽的第N名) for(Y枚舉當(dāng)前已知的excellent) 判斷Y是否比X better這樣，我們能把時間復(fù)雜度減少到O(NK)（設(shè)K是excellent選手的個數(shù)）。所以還是先用降維的思想，我們先解決選手之間只進行兩次競賽的問題。也許這里有心人會發(fā)現(xiàn)什么，對了，比較B[A1]與B[X]，B[A2]與B[X]，B[A3]與B[Ai]……的時候，只要有任何一個B[Aj]B[Ai](ji)，Ai就不是excellent的，那么，我們只需要用min(B[Aj])與B[Ai]比較！〖改進三〗（適用于兩次競賽）以上我們看到了一個特殊的例子：兩次排名完全相反，但是我們可以從中提煉出可行的改進算法：對于兩次競賽的情況，當(dāng)X=Ai時，設(shè)，則B[Ai]只需要與besti比較即可?！几倪M四〗能否把改進三擴展到三次競賽上面去呢？為了方便說明，我們還需要設(shè)第三次競賽中Ai選手名次為C[Ai]。為什么我們卻說這是改進過后的算法呢？因為我們實際上利用問題的特殊性，改進二是純粹的枚舉，進行的第(1)步以后要第二第三次競賽同時比較，實現(xiàn)起來是很難優(yōu)化的。為了讓第(3)步與第(2)步結(jié)合，我們再設(shè)另一個數(shù)列Ek，使它和Dk一一對應(yīng)，即Dk與Ek分別代表同一選手在第二第三次競賽的名次。查詢：查詢key小于X的最小的value顯然，這里的key代表Dk，value代表Ek。我們定義每個節(jié)點表示的區(qū)間是key的區(qū)間，而節(jié)點值則記錄該區(qū)間中的最小value。顯然我們查詢[1,a]的最小value時，由檢索樹的性質(zhì)，我們可以把它分成小區(qū)間并分別查詢它。這種數(shù)據(jù)結(jié)構(gòu)能使查詢和插入操作都能在O(LogN)的復(fù)雜度下完成，〖最終算法〗這樣我們就能很清晰地得出優(yōu)化的解法：以第一次競賽的名次從高到低枚舉X，以第二次競賽名次為key，第三次競賽名次為value。對于所有數(shù)據(jù)都應(yīng)該在很短時間內(nèi)出解。筆者之所以選取了Team這題作重點分析，不僅是因為Team一題需要靈敏的頭腦，全面地觀察，還因為它需要對數(shù)據(jù)結(jié)構(gòu)有一定的認識，筆者當(dāng)初做這道題的時候就在這里栽了跟頭。算法改進的思想其實是開闊進取的思想，即不滿足于現(xiàn)狀，要開發(fā)新的算法，新的思路。事實上，任何經(jīng)典的算法都是由創(chuàng)新的思想總結(jié)出來的。Z鎮(zhèn)是一個很特別的城鎮(zhèn)，它有m+1條東西方向和n+1條南北方向的道路，劃分成個區(qū)域。分數(shù)越高表示他們越想到那個地方，越低表示他們越不想去。 當(dāng)然，有可能隊員們一個地方也不去（例如，所有區(qū)域的分值都是負數(shù)?！驾斎敫袷健捷斎霐?shù)據(jù)存放在當(dāng)前目錄下的文本文件中。接下來的m行，每行n個整數(shù)，第i行第j個數(shù)表示分值V(I,j)。注意：不要有多余空行，行首行尾不要有多余空格。圖上其它白色網(wǎng)格均攻擊不到。P39。按順序表示地圖中每一行的數(shù)據(jù)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1