《算法優(yōu)化策略》ppt課件

1、給定由n個(gè)整數(shù)(能夠?yàn)樨?fù)整數(shù))組成的序列a1,a2,an,求該序列形如 的子段和的最大值。當(dāng)一切整數(shù)均為負(fù)整數(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; 留意到 ，那么可將算法中的最后一個(gè)for循環(huán)省去，防止反復(fù)計(jì)算只需求O(n2)的計(jì)算時(shí)間。1jikkjikjkaaa假設(shè)將所給的序列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中計(jì)算出 ，并在an/2

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

4、lic static 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è) ，那么給定一個(gè)m行n列的整數(shù)矩陣a，試求矩陣a的一個(gè)子矩陣，使其各元素之和為最大。 2121)2, 1, 2, 1(iiijjjjiajjiis)2, 1, 2, 1(max211211jjiisnjjmii)2, 1(max)2, 1, 2, 1(maxmax)2, 1, 2, 1(max2112112112

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

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

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

8、單調(diào) 對于滿足四邊形不等式的單調(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í)，函數(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,(jk

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

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

11、有效區(qū)間。性質(zhì)性質(zhì)1：區(qū)間：區(qū)間I(k)是是S(i)中的有效區(qū)間，那么對恣意中的有效區(qū)間，那么對恣意kji，區(qū)間，區(qū)間I(k)是是S(j)中的有效區(qū)間。另一方面，假設(shè)區(qū)間中的有效區(qū)間。另一方面，假設(shè)區(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ū)間的右端點(diǎn)。的最右有效區(qū)間的右端點(diǎn)。性質(zhì)性質(zhì)3：區(qū)間：區(qū)間I(i)是集合是集合S(i)中的有效區(qū)間當(dāng)且僅當(dāng)在中的

12、有效區(qū)間當(dāng)且僅當(dāng)在S(i)中有一中有一條從條從I(1)到到I(i)的路。的路。 性質(zhì)性質(zhì)4：當(dāng)：當(dāng)ik且且dist(i,i)dist(k,i)時(shí)，時(shí)，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)的右的右端點(diǎn)端點(diǎn)b(j)，那么對恣意，那么對恣意ik，I(k)是是S(i)中的無效區(qū)間。中的無效區(qū)間。 算法算法shortestIntervalPaths步驟步驟1：

13、dist(1,1)w(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);上述

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

15、當(dāng)前有效區(qū)間I(k)在集合k中。 (2)對每個(gè)集合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)用一個(gè)棧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) / 解最短加法鏈問題的規(guī)范回溯法 int i,j,k; if (astep=

16、n) / 找到一條加法鏈 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步。假設(shè)預(yù)期在形狀空間樹T的第d層找到關(guān)于n的一條加法鏈，那么以形狀空間樹第i層結(jié)點(diǎn)ai為根的子樹中，可在第d層找到一條加法鏈的必要條件是2d-iain。當(dāng) 時(shí)，形狀空間樹中以結(jié)點(diǎn)ai為根的子樹中不能夠在第d層之前找到最短加法鏈。 設(shè)在求正整數(shù)n的最短加法鏈的逐漸深化迭代搜索算法中，當(dāng)前搜索深度為d。且正整數(shù)可表示為n=2t(2k+1)，k0，那么在形狀空間樹的第i層結(jié)點(diǎn)ai處的一個(gè)剪枝條件是naiid)2(23ditdtdidiandianii120/log23/log與加法鏈問題親密相關(guān)的冪樹給出了l(n)的更準(zhǔn)確的上界。 假設(shè)已定義了冪樹T的第k層結(jié)點(diǎn)，那么T的第k+1層結(jié)點(diǎn)可定義如下。依從左到右順序取第k層結(jié)點(diǎn)ak，定義其按從左到右順序陳列的兒子結(jié)點(diǎn)為ak+aj，0jk。其中a0,a1,ak，