算法合集之用改進(jìn)算法思想解決規(guī)模維數(shù)增大問題-免費閱讀
【正文】 按順序表示地圖中每一行的數(shù)據(jù)。圖上其它白色網(wǎng)格均攻擊不到。接下來的m行，每行n個整數(shù)，第i行第j個數(shù)表示分值V(I,j)。 當(dāng)然，有可能隊員們一個地方也不去（例如，所有區(qū)域的分值都是負(fù)數(shù)。Z鎮(zhèn)是一個很特別的城鎮(zhèn)，它有m+1條東西方向和n+1條南北方向的道路，劃分成個區(qū)域。算法改進(jìn)的思想其實是開闊進(jìn)取的思想，即不滿足于現(xiàn)狀，要開發(fā)新的算法，新的思路。對于所有數(shù)據(jù)都應(yīng)該在很短時間內(nèi)出解。顯然我們查詢[1,a]的最小value時，由檢索樹的性質(zhì)，我們可以把它分成小區(qū)間并分別查詢它。查詢：查詢key小于X的最小的value顯然，這里的key代表Dk，value代表Ek。為什么我們卻說這是改進(jìn)過后的算法呢？因為我們實際上利用問題的特殊性，改進(jìn)二是純粹的枚舉，進(jìn)行的第(1)步以后要第二第三次競賽同時比較，實現(xiàn)起來是很難優(yōu)化的。也許這里有心人會發(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]比較！〖改進(jìn)三〗（適用于兩次競賽）以上我們看到了一個特殊的例子：兩次排名完全相反，但是我們可以從中提煉出可行的改進(jìn)算法：對于兩次競賽的情況，當(dāng)X=Ai時，設(shè)，則B[Ai]只需要與besti比較即可。主要流程3： for(X從第一次競賽的第1名到第一次競賽的第N名) for(Y枚舉當(dāng)前已知的excellent) 判斷Y是否比X better這樣，我們能把時間復(fù)雜度減少到O(NK)（設(shè)K是excellent選手的個數(shù)）。主要流程1： for(X從1到N) for(Y從1到N) 判斷Y是否比X better〖改進(jìn)一〗原始算法是可以改進(jìn)的。求excellent選手的個數(shù)。這樣可以得出一個改進(jìn)：每次選取一條費用最?。ǘ曳钦┑目稍鰪V路徑，直到最終不存在費用非正的可增廣路徑。但是容易觀察到，mn，最大只有10，又因為炮兵攻擊范圍很大，實際上能放炮兵的組合數(shù)很小，可以考慮枚舉組合，從而得到改進(jìn)的動態(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。我們可以嘗試著構(gòu)造上下、左右同時進(jìn)行的動態(tài)規(guī)劃，但是也許我們無能為力。這樣，時間復(fù)雜度達(dá)到O(N4)，顯然不可以接受。我們來分析一下原方法的實質(zhì)：按照圖中的斜線來劃分階段，即階段變量k表示走過的步數(shù)，而狀態(tài)變量xk表示當(dāng)前處于這一階段上的哪一點。主要流程是：1. 找出原始解法和可能改進(jìn)的方向（即分析成A、B、C模型）；2. 分析算法的原理（由燒一根香計時半小時，引申為燒剩t的時候點兩頭就能計時）；3. 改進(jìn)算法（改進(jìn)的過程中，往往不是依靠算法改進(jìn)算法本身，反而是利用算法的內(nèi)涵、實質(zhì)，結(jié)合問題，構(gòu)造算法）；4. 解決問題（我們得出了正確的解法）。方案已經(jīng)更進(jìn)一步了。有的時候我們分析到某個問題好像可以用某種方法解決，但是這個問題卻與之前見過的問題有些不同，例如本文所討論的情況：問題的規(guī)模維數(shù)比原問題大，一維的變二維的，二維的變?nèi)S的，等等。從1到2，從2到3——用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問題 廣東省韶關(guān)一中 張偉達(dá)用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問題廣東韶關(guān)一中 張偉達(dá)【關(guān)鍵字】 增大規(guī)模 改進(jìn)算法 降維 分析 構(gòu)造【摘要】我們常常會遇到一些特殊的問題，它們把我們能夠解決的問題改了一改，增加了一維，或者增加了一個因素，從1到2或者是從2到3，本文把它們統(tǒng)稱規(guī)模維數(shù)增大的問題。我們不妨把這類問題叫做規(guī)模維數(shù)增大的問題，解決這一類問題，往往需要觀察問題的特殊性，改進(jìn)原有算法，從而解決實際問題。通過這一步，B模型只用一根香，是很容易被排除的。但是如何來改進(jìn)原有的算法呢，筆者認(rèn)為可以有以下途徑：1. 直接增加算法的規(guī)模，解決問題2. 用枚舉處理增加的規(guī)模，從而解決問題3. 用貪心解決增加的規(guī)模，從而解決問題4. 以上各個途徑的綜合運用圍繞這一主線，筆者將用例題做進(jìn)一步的闡明。這時的模型實際上已經(jīng)轉(zhuǎn)化成了一個特殊的多段圖。因為它是兩維的問題，我們可以嘗試著把維數(shù)降低。對于這道題的數(shù)據(jù)規(guī)模，似乎沒有必要構(gòu)造O(N2)時間的算法。這樣到最后的最優(yōu)解就是最終復(fù)雜度分析，時間復(fù)雜度大約O(R3n)（R是一行狀態(tài)的組合數(shù)）(3)用貪心解決增加的規(guī)模，從而解決問題【例四】求網(wǎng)絡(luò)的最小費用最大流。這樣用貪心的策略就能解決問題了。如數(shù)據(jù)：則excellent選手是1，2，3，5。不難看出，如果讓X依照第一次競賽的名次循環(huán)，枚舉Y時只需要枚舉在第一次競賽中排在X前面選手即可，因為第一次競賽排在X后的選手一定不可能比X better。由于這題K可能很大，算法效果仍然不是很理想。時間復(fù)雜度竟然達(dá)到O(N)。但是改進(jìn)四則體現(xiàn)了第二第三次競賽分步選取的思路，利用這一點能否在實現(xiàn)中改進(jìn)算法的復(fù)雜度呢？我們可以比較，改進(jìn)二和改進(jìn)四是不同的，在進(jìn)行了第(1)步以后，改進(jìn)二需要同時考慮第二第三次競賽成績，兩次成績同時考慮并不是嚴(yán)格有序的，有時候我們不能比較二元組(B[Ai],C[Ai])與(B[Aj],C[Aj])的大?。ɡ绠?dāng)B[Ai]B[Aj]，但C[Ai]C[Aj]時）。因為我們需要的操作與檢索樹擅長的操作很類似，所以對數(shù)據(jù)結(jié)構(gòu)有一定理解的選手，在這里都能夠想到我們可以構(gòu)造一個二叉檢索樹。例如當(dāng)a
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1