第10章算法優(yōu)化策略ppt課件

1、給定由n個整數(shù)(可能為負整數(shù))組成的序列a1,a2,an,求該序列形如 的子段和的最大值。當(dāng)所有整數(shù)均為負整數(shù)時定義其最大子段和為。依此定義，所求的最優(yōu)值為:例如: A=(-2，11，-4，13，-5，-2)最大子段和為jikkajikknjia1max, 0max2042kkapublic static int maxSum() int n=a.length-1; int sum=0; for (int i=1;i=n;i+) int thissum=0; for (int j=i;j=n;j+) for (int k=i;ksum) sum=thissum; besti=i; bestj=

2、j; return sum; thissum+=aj; 注意到 ，則可將算法中的最后一個for循環(huán)省去，避免重復(fù)計算只需要O(n2)的計算時間。1jikkjikjkaaa如果將所給的序列a1:n分為長度相等的2段a1:n/2和an/2+1:n，分別求出這2段的最大子段和，則a1:n的最大子段和有3種情況。(1)a1:n的最大子段和與a1:n/2最大子段和相同；(2)a1:n的最大子段和與an/2+1:n最大子段和相同；(3)a1:n的最大子段和為 ，且1in/2，n/2+1jn。對于情形(3)。容易看出，an/2與an/2+1在最優(yōu)子序列中。因此，可以在a1:n/2中計算出 ，并在an/2+1

3、:n中計算出 。則s1s2即為出現(xiàn)情形(3)時的最優(yōu)值。據(jù)此可設(shè)計出求最大子段和的分治算法。jikka2/2/1max1niknikasinkninkas12/12/max2復(fù)雜度分析復(fù)雜度分析T(n)=O(nlogn)cncnnOnTOnT)()2/(2) 1 ()(記 ，1 j n，則所求的最大子段和為當(dāng)bj-10時bj=bj-1+aj，否則bj=aj。由此可得計算bj的動態(tài)規(guī)劃遞歸式 max1jikjikajbmaxmaxmaxmax1111jbkakanjjikjinjjiknjibj=maxbj-1+aj，aj， 1 j n算法顯然需要O(n)計算時間和O(n)空間。public s

4、tatic int maxSum() int n=a.length-1; int sum=0, b=0; for (int i=1;i0) b+=ai; else b=ai; if (bsum)sum=b; return sum; 記 最大子矩陣和問題的最優(yōu)值為由于其中， 設(shè) ，那么給定一個m行n列的整數(shù)矩陣a，試求矩陣a的一個子矩陣，使其各元素之和為最大。 2121)2, 1, 2, 1(iiijjjjiajjiis)2, 1, 2, 1(max211211jjiisnjjmii)2, 1(max)2, 1, 2, 1(maxmax)2, 1, 2, 1(max211211211211211

5、iitjjiisjjiismiinjjmiinjjmii2121211211max)2, 1, 2, 1(max)2, 1(jjjiiinjjnjjjiajjiisiit21iiijiajb21211max)2, 1(jjjnjjjbiit由于解最大子段和問題的動態(tài)規(guī)劃算法需要時間O(n)，故算法的雙重for循環(huán)需要計算時間O(m2n)。給定由n個整數(shù)(可能為負整數(shù))組成的序列a1,a2,an,以及一個正整數(shù)m，要求確定序列的m個不相交子段，使這m個子段的總和達到最大。設(shè)b(i，j)表示數(shù)組a的前j項中i個子段和的最大值，且第i個子段含aj(1 i m，i j n)。則所求的最優(yōu)值顯然為與最大

6、子段和問題類似地，計算b(i，j)的遞歸式為初始時，b(0，j)=0，(1 j n);b(i，0)=0，(1 i m)。 ),(maxjmbnjm),1 (), 1(max,) 1,(max),(1njimijatibjajibjibjti優(yōu)化：注意到在上述算法中，計算bij時只用到數(shù)組b的第i-1行和第i行的值。因而算法中只要存儲數(shù)組b的當(dāng)前行，不必存儲整個數(shù)組。另一方面，b(i-1，t)的值可以在計算第i-1行時預(yù)先計算并保存起來。計算第i行的值時不必重新計算，節(jié)省了計算時間和空間。 在一個鐵路沿線順序存放著n堆裝滿貨物的集裝箱。貨物儲運公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰

7、的2堆集裝箱合并成新的一堆，所需的運輸費用與新的一堆中集裝箱數(shù)成正比。 給定各堆的集裝箱數(shù)，試制定一個運輸方案，使總運輸費用最少。設(shè)合并ai:j，1ijn，所需的最少費用為mi,j，則原問題的最優(yōu)值為m1，n。由最優(yōu)子結(jié)構(gòu)性質(zhì)可知，jijitajkmkimjimjitjki, 1,min0,根據(jù)遞歸式，按通常方法可設(shè)計計算m(i,j)的O(n3)動態(tài)規(guī)劃算法jijijkmkimjiwjimjki, 1,min),(0,貨物儲運問題的動態(tài)規(guī)劃遞歸式是下面更一般的遞歸計算式的特殊情形。對于 ,當(dāng)函數(shù)w(i,j)滿足時稱w滿足四邊形不等式。當(dāng)函數(shù)w(i,j)滿足 時稱W關(guān)于區(qū)間包含關(guān)系單調(diào) 對于滿足

8、四邊形不等式的單調(diào)函數(shù)w，可推知由遞歸式定義的函數(shù)m(i,j)也滿足四邊形不等式，即) ,(), () , (),(jiwjiwjiwjiwjjii) ,(), (jiwjiw) ,(), () , (),(jimjimjimjim定義由函數(shù)m(i,j)的四邊形不等式性質(zhì)可推出函數(shù)s(i,j)的單調(diào)性，即根據(jù)前面的討論，當(dāng)w是滿足四邊形不等式的單調(diào)函數(shù)時，函數(shù)s(i,j)單調(diào)，從而 ),(),() 1,(),(|max),(jiwjkmkimjimkjiss(i,j) s(i,j+1) s(i+1,j+1)，i j),() 1,(min),() 1,(min), 1()1,(jkmkimjkm

9、kimjiskjisjki改進后算法speedDynamicProgramming所需的計算時間為 )(), 1 (),() 1,(), 1(121010101nOnOrsnrnsrnOriisriisOnrnrnrrni采用每次合并集裝箱數(shù)最少的相鄰2堆貨物的貪心策略，并不能得到最優(yōu)解。適當(dāng)放松相鄰性約束，引入相容結(jié)點對概念。如圖，原始結(jié)點用方形結(jié)點表示，合并生成的結(jié)點用圓形結(jié)點表示。最小相容結(jié)點對ai和aj 是滿足下面條件的結(jié)點對：（1結(jié)點ai和aj 之間沒有方形結(jié)點；（2在所有滿足條件1的結(jié)點中ai+aj的值最小；（3在所有滿足條件1和2的結(jié)點中下標 i 最小；（4在所有滿足條件1）（2

10、和3的結(jié)點中下標 j 最小。相應(yīng)的最小相容合并樹，如下圖。根據(jù)上述定理，容易從各原始結(jié)點在相容合并樹中所處的層序構(gòu)造出相應(yīng)的最優(yōu)合并樹，如下圖。1. 組合階段: 將給定的n個數(shù)作為方形結(jié)點依序從左到右排列，a1，a2，an。反復(fù)刪除序列中最小相容結(jié)點對ai和aj，(ib(i)。設(shè)區(qū)間I(k)( ki )是區(qū)間集S(i)中的一個區(qū)間，1 i n。如果對于S(i)的任意擴展S(i)T，當(dāng)區(qū)間JT且在S(i)T中有從I(1)到J的路時，在S(i)T中從I(1)到J的任一最短路都不含區(qū)間I(k)，則稱區(qū)間I(k)是S(i)中的無效區(qū)間。若S(i)中的區(qū)間I(k)不是無效區(qū)間則稱其為S(i)中的有效區(qū)間

11、。性質(zhì)性質(zhì)1：區(qū)間：區(qū)間I(k)是是S(i)中的有效區(qū)間，則對任意中的有效區(qū)間，則對任意kji，區(qū)間，區(qū)間I(k)是是S(j)中的有效區(qū)間。另一方面，若區(qū)間中的有效區(qū)間。另一方面，若區(qū)間I(k)是是S(i)中的無效中的無效區(qū)間，則對任意區(qū)間，則對任意ji，區(qū)間，區(qū)間I(k)是是S(j)中的無效區(qū)間。中的無效區(qū)間。性質(zhì)性質(zhì)2：集合：集合S(i)中所有有效區(qū)間的并覆蓋從中所有有效區(qū)間的并覆蓋從a(1)到到b(j)的線段，的線段，其中其中b(j)是是S(i)的最右有效區(qū)間的右端點。的最右有效區(qū)間的右端點。性質(zhì)性質(zhì)3：區(qū)間：區(qū)間I(i)是集合是集合S(i)中的有效區(qū)間當(dāng)且僅當(dāng)在中的有效區(qū)間當(dāng)且僅當(dāng)在S

12、(i)中有一中有一條從條從I(1)到到I(i)的路。的路。 性質(zhì)性質(zhì)4：當(dāng)：當(dāng)ik且且dist(i,i)dist(k,i)時，時，I(k)是是S(i)中的無效區(qū)間。中的無效區(qū)間。 性質(zhì)性質(zhì)5：設(shè)：設(shè)I(j(1)，I(j(2)，I(j(k)是是S(i)中的有效區(qū)間，且中的有效區(qū)間，且j(1)j(2)k），且），且dist(i,i)k且且dist(i,i)1)不包含不包含S(k-1)中任一有效區(qū)間中任一有效區(qū)間I(j)的右的右端點端點b(j)，則對任意，則對任意ik，I(k)是是S(i)中的無效區(qū)間。中的無效區(qū)間。 算法算法shortestIntervalPaths步驟步驟1：dist(1,1)w

13、(1)；步驟步驟2：for (i=2;i=n;i+)(2.1): j=min k | a(i)b(k);1ki ;if (j不存在不存在) dist(i,i)+;else dist(i,i)dist(j,i-1)+w(i);(2.2): for (ki)if (dist(i,i)dist(k,i-1) dist(k,i)+;else dist(k,i)dist(k,i-1);步驟步驟3：for (i=2;i=n;i+) if (dist(i,n)=+) j=min k | (dist(k,n)+)&(a(i)b(k) ;dist(i,n)=dist(j,n)+w(i);上述算法的關(guān)鍵是

14、有效地實現(xiàn)步驟(2.1)和(2.2) 用一棵平衡搜索樹2-3樹存儲當(dāng)前區(qū)間集S(i)中的有效區(qū)間。以區(qū)間的右端點的值為序。如下圖。(2.1)的實現(xiàn)對應(yīng)于平衡搜索樹從根到葉的一條路徑上的搜索，在最壞情況下需要時間O(logn)。(2.2)的實現(xiàn)對應(yīng)于反復(fù)檢查并刪除平衡搜索樹中最右葉結(jié)點的前驅(qū)結(jié)點。在最壞情況下，每刪除一個結(jié)點需要時間O(logn)。綜上，算法shortestIntervalPaths用平衡搜索樹的實現(xiàn)方案，在最壞情況下的計算時間復(fù)雜性為O(nlogn)。采用并查集結(jié)構(gòu)。用整數(shù)k表示區(qū)間I(k),1kn。初始時每個元素k構(gòu)成一個單元素集，即集合k是k，1kn。(1)每個當(dāng)前有效區(qū)間

15、I(k)在集合k中。 (2)對每個集合S(i)，設(shè)L(S(i)=I(k)|I(k)是S(i)的無效區(qū)間，且I(k)與S(i)的任一有效區(qū)間均不相交 , L(S(i)中所有區(qū)間均位于S(i)的所有有效區(qū)間并的右側(cè)。 (3)用一個棧AS存放當(dāng)前有效區(qū)間I(i(1)，I(i(2)，I(i(k)。I(i(k)是棧頂元素。該棧稱為當(dāng)前有效區(qū)間棧。(4)對于1kn，記prev(I(k)=minj|a(k)ai由aj+ak, kji所構(gòu)成。 private static void backtrack(int step) / 解最短加法鏈問題的標準回溯法 int i,j,k; if (astep=n) / 找

16、到一條加法鏈 if (step=1;i-) if (2*aiastep) for (j=i;j=1;j-) k=ai+aj; astep+1=k; if (kastep)&(k2maj。由于加倍是加法鏈中元素增大的最快的方式，即ai2ai-1，所以從aj到ai至少需要m+1步。如果預(yù)期在狀態(tài)空間樹T的第d層找到關(guān)于n的一條加法鏈，則以狀態(tài)空間樹第i層結(jié)點ai為根的子樹中，可在第d層找到一條加法鏈的必要條件是2d-iain。當(dāng) 時，狀態(tài)空間樹中以結(jié)點ai為根的子樹中不可能在第d層之前找到最短加法鏈。 設(shè)在求正整數(shù)n的最短加法鏈的逐步深化迭代搜索算法中，當(dāng)前搜索深度為d。且正整數(shù)可表示為n=2t(2k+1)，k0，則在狀態(tài)空間樹的第i層結(jié)點ai處的一個剪枝條件是naiid)2(23ditdtdidiandianii120/log23/log與加法鏈問題密切相關(guān)的冪樹給出了l(n)的更精確的上界。 假設(shè)已定義了冪樹T的第k層結(jié)點，則T的第k+1層結(jié)點可定義如下。依從左到右順序取第k層結(jié)點ak，定義其按從左到右順序排列的兒子結(jié)點為ak+aj，0jk。其中a0,a1,ak，是