算法設(shè)計(jì)與分析-3

1、 學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn):理解動(dòng)態(tài)規(guī)劃算法的概念，動(dòng)態(tài)規(guī)劃vs遞歸分治 掌握動(dòng)態(tài)規(guī)劃算法的基本要素 （1）最優(yōu)子結(jié)構(gòu)性質(zhì) （2）重疊子問(wèn)題性質(zhì)掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。 (1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 (2)遞歸地定義最優(yōu)值。 (3)以自底向上的方式以自底向上的方式計(jì)算出最優(yōu)值。 (4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。通過(guò)應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略。（1）矩陣連乘問(wèn)題；（2）最長(zhǎng)公共子序列；（3）最大子段和（4）凸多邊形最優(yōu)三角剖分；（5）(多邊形游戲)（6）圖像壓縮；（7）背包問(wèn)題；（8）最優(yōu)二叉搜索樹（9）(流水作業(yè)調(diào)度)（10）(電路布線)n與分治法類似，其基本思想

2、也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題;先求子問(wèn)題解，然后合成原問(wèn)題解nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=n大問(wèn)題自上而下分解為子問(wèn)題時(shí)，可以有多種分解方法。 e.g. 歸并排序，矩陣連乘n如果不同分解方法對(duì)應(yīng)的子問(wèn)題及其解不同，并導(dǎo)致合并后的原問(wèn)題解不同，則需要考慮各種可能的分解方法。此時(shí)，無(wú)法直接采用分治法求解：e.g. 矩陣連乘1. 分解得到的子問(wèn)題往往不是互相獨(dú)立的，用分治法求解，需要計(jì)算的子問(wèn)題數(shù)目太多，時(shí)間復(fù)雜性指數(shù)級(jí)別2. 不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。 E.g. Fibonacci數(shù)列計(jì)算，見后與分治法區(qū)

3、別nT(n)=n/2T(n/4) T(n/4) T(n/4) T(n/4)n/2T(n/4) T(n/4) T(n/4) T(n/4)n/2T(n/4) T(n/4) T(n/4) T(n/4)n/2T(n/4) T(n/4) T(n/4) T(n/4)n解決方法： 保存已解決的子問(wèn)題的答案，在需要時(shí)再找出已求得的答案，避免大量重復(fù)計(jì)算，得到多項(xiàng)式時(shí)間算法。 利用表來(lái)記錄子問(wèn)題的答案，表的大小為多項(xiàng)式量級(jí)n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)示例：分治法 vs 動(dòng)

4、態(tài)規(guī)劃n算法1基于遞歸分治 F(n) 1. if (n = 1 return 1; 2. else return F(n-1)+ F(n-2); 問(wèn)題：復(fù)雜性O(shè)(2n) 原因：自上而下的自上而下的遞歸計(jì)算過(guò)程中，一些子問(wèn)題被多次重 復(fù)計(jì)算10( )11(1)(2)1nF nnF nF nnFibonacci數(shù)F(6)F(4)F(3)F(2)F(1)F(0)F(2)F(1)F(0)F(1)F(5)F(4)F(3)F(2)F(1)F(0)F(1)F(3)F(2)F(2)F(1)F(0)F(1)F(1)F(0)子問(wèn)題子問(wèn)題F(3)重復(fù)計(jì)算重復(fù)計(jì)算3次次子問(wèn)題子問(wèn)題F(2)重復(fù)計(jì)算重復(fù)計(jì)算5次次n算法

5、2：非遞歸的分治算法 保存子問(wèn)題計(jì)算結(jié)果，只計(jì)算1次，以后碰到同樣子問(wèn)題時(shí)，直接調(diào)用已有結(jié)果F1(n) 0. 初始化數(shù)組 vi -1, 0 i n 1. if vn 0 then 2. vn F1(n-1) + F1(n-2) 3. return vn 數(shù)組vn: 存儲(chǔ)子問(wèn)題結(jié)果的數(shù)組， vi：表示子問(wèn)題Fi的解， vi=-1：表示子問(wèn)題Fi還沒(méi)有被計(jì)算問(wèn)題：自上而下的計(jì)算過(guò)程中，避免了多次計(jì)算同一子問(wèn)題，但又多次函數(shù)調(diào)用。每次調(diào)用需要花費(fèi)較多時(shí)間用于參數(shù)傳遞和動(dòng)態(tài)鏈接n算法3自下而上的迭代算法：動(dòng)態(tài)規(guī)劃算法F2(n) 1. F(0) 1; 2. F(1) 1; 3. for i 2 to n

6、 do 4. Fi F1(i-1) + F1(i-2) /* 問(wèn)題問(wèn)題-子問(wèn)題間的遞歸公式子問(wèn)題間的遞歸公式 5. return Fn 特點(diǎn)： 1）時(shí)間復(fù)雜性 O(n) 2) 自下而上，迭代計(jì)算 3) 利用數(shù)組，保存中間（子問(wèn)題）計(jì)算結(jié)果。每個(gè)子問(wèn)題只計(jì)算一次n1.找出最優(yōu)解的性質(zhì)，刻劃其結(jié)構(gòu)特征-最優(yōu)子結(jié)構(gòu)特征n2. 遞歸地定義最優(yōu)值： 刻畫原問(wèn)題解與子問(wèn)題解間的（數(shù)值）關(guān)系: 表達(dá)式中存在尋優(yōu)變量、最優(yōu)目標(biāo)值尋優(yōu)變量、最優(yōu)目標(biāo)值n3. 以自底向上自底向上的方式計(jì)算出各個(gè)子問(wèn)題、原問(wèn)題的最優(yōu)值，并避免子問(wèn)題的重復(fù)計(jì)算（記錄已計(jì)算的子問(wèn)題解）n4. 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解12（

7、1）矩陣連乘問(wèn)題；乘法次數(shù)最少（2）最長(zhǎng)公共子序列；公共子序列的長(zhǎng)度最長(zhǎng) （3）最大子段和子段中的數(shù)字之和最大（4）凸多邊形最優(yōu)三角剖分；三角形上權(quán)之和為最小（6）圖像壓縮；（9）背包問(wèn)題；（10）最優(yōu)二叉搜索樹。（7）電路布線；（8）流水作業(yè)調(diào)度；作業(yè)運(yùn)行時(shí)間最短（5）多邊形游戲；u給定n個(gè)可連乘的矩陣A1, A2, ,An,連乘積A1A2, ,An 。u根據(jù)矩陣乘法結(jié)合律，可有多種不同計(jì)算次序，每種次序有不同的計(jì)算代價(jià))數(shù)乘次數(shù)數(shù)乘次數(shù)（取決于各矩陣的行、列數(shù)和計(jì)算次序）u給定2個(gè)矩陣Api,pj,Bpj,pk, AB 為pi,pk矩陣，數(shù)乘次數(shù)pipjpku多個(gè)矩陣的連乘計(jì)算次序可用完全

8、加括號(hào)來(lái)確定見下頁(yè)1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB這5種計(jì)算次序?qū)?yīng)的計(jì)算代價(jià)分別為： 16000, 10500, 36000, 87500, 34500u設(shè)有四個(gè)矩陣A, B, C, D, 它們的維數(shù)分別是：u總共有五種完全加括號(hào)的方式舉例(40*30*5) + 10*40*5 + 50*10*5CD40,5B(CD)10,5A(B(CD)50,5u完全加括號(hào)的矩陣連乘積可遞歸地定義為：（1）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積 是完全加括號(hào)的，則 可 表示為2個(gè)完全加括號(hào)的矩陣連乘積 和 的乘積并加括號(hào)，即 AABC)(

9、BCA加括號(hào)：矩陣連乘的計(jì)算次序n給定n個(gè)矩陣 ， 其中 與 是可乘的， ?？疾爝@n個(gè)矩陣的連乘積 n由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。n若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積,.,21nAAAiA1iA1,.,2 , 1ninAAA.21給定n個(gè)矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1，2，n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最

10、少。u方法方法1：窮舉法：窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。 算法復(fù)雜度分析：算法復(fù)雜度分析： 對(duì)于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序下的組合方式（即完全加括號(hào)的組合方式）為P(n)。 每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A1.Ak)(Ak+1An)，關(guān)于P(n)的遞推式如下：)/4()(11)()(1)(2/ 311nnPnnknPkPnPnnk窮舉法u 方法方法2：動(dòng)態(tài)規(guī)劃：動(dòng)態(tài)規(guī)劃 將矩陣連乘積 簡(jiǎn)記為Ai:j ，這里ij jiiAAA.1考察計(jì)算Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣A

11、k和Ak+1之間將矩陣鏈斷開，ikj，則其相應(yīng)完全加括號(hào)方式為).)(.(211jkkkiiAAAAAA計(jì)算量：Ai:k的計(jì)算量 + Ak+1:j的計(jì)算量 +Ai:k和Ak+1:j相乘的計(jì)算量n特征： 計(jì)算Ai:j的最優(yōu)次序所包含的計(jì)算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。即： 矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。 問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。n設(shè)計(jì)算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問(wèn)題的最優(yōu)值為m1,n n當(dāng)i=j時(shí)，Ai:j=Ai，因此，mi,i=0，i=1,2,nn

12、當(dāng)ij時(shí)，n斷開位置kn可以遞歸地定義mi,j為：jkipppjkmkimjim1, 1,這里 的維數(shù)為 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 種可能kij ).)(.(211jkkkiiAAAAAAn對(duì)于1ijn，不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問(wèn)題。因此，不同子問(wèn)題的個(gè)數(shù)最多只有n由此可見，在遞歸計(jì)算時(shí)，許多子問(wèn)題被重復(fù)計(jì)算多次許多子問(wèn)題被重復(fù)計(jì)算多次 這也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。n用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算： 1）在計(jì)算過(guò)程中，保存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次 2

13、）而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算 最終得到多項(xiàng)式時(shí)間的算法)(22nnn子問(wèn)題Ai,i, 1i nvoid MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; /*規(guī)模為1的子問(wèn)題的最優(yōu)解 for (int r = 2; r = n; r+) /*自下而上，從規(guī)模為r=2的子問(wèn)題開始， 依次計(jì)算規(guī)模為2、3、n的子問(wèn)題 for (int i = 1; i = n - r+1; i+) /*考察規(guī)模為r的共n-r+1個(gè)子問(wèn)題 mi, j, j-i= r-1, int j=i+

14、r-1; /* 子問(wèn)題左端點(diǎn)i，右端點(diǎn)j, 規(guī)模r mij =0+ mi+1j+ pi-1*pi*pj; /*設(shè)置子問(wèn)題mi,j的初始最優(yōu)值 sij = i; /*記錄子問(wèn)題最優(yōu)值的初始斷點(diǎn)位置 for (int k = i+1; k j; k+) /*依次考察不同斷點(diǎn)，計(jì)算mi,j最優(yōu)值 int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; 輸入?yún)?shù)最優(yōu)值斷開位置子問(wèn)題mi, j的遞推比較矩陣維度1(.)iijA AA1n子問(wèn)題規(guī)模r：2nr左端點(diǎn)i：1( 0) return mij; /* Ai,j 如果以前以計(jì)算過(guò)，

15、則 mi,j0，直接返回計(jì)算結(jié)果， 避免重復(fù)計(jì)算 if (i = j) return 0; /* Ai,j =Ai,i, 只有1個(gè)矩陣的最小規(guī)模子問(wèn)題 /* 以下各步依次比較 k=i,j-1 等多種劃分方法，求最優(yōu)劃分和最優(yōu)值 int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; /*初始最佳劃分點(diǎn)位置k=i for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t;

16、 sij = k; mij = u; return u;Ai,i*Ai+1,jAi,k*Ak+1,j 備忘錄 vs 動(dòng)態(tài)規(guī)劃n備忘錄方法采用自上而下的遞歸分解法n與動(dòng)態(tài)規(guī)劃法一樣，避免子問(wèn)題重復(fù)計(jì)算n但由于采用遞歸，需要多次函數(shù)調(diào)用和參數(shù)傳遞，計(jì)算時(shí)間仍然比動(dòng)態(tài)規(guī)劃要大若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對(duì)于所有j=1,2,k有：zj=xijE.g. 對(duì)序列X=A，B，C，B，D，A，B，子序列Z=B，C，D，B ，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。 應(yīng)用：網(wǎng)絡(luò)內(nèi)容審查, 敏感字檢查給定2個(gè)序列X和Y，當(dāng)

17、另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列公共子序列。問(wèn)題：給定2個(gè)序列X=x1, x2, xm和Y=y1,y2,yn，找出X和Y的最長(zhǎng)最長(zhǎng)公共子序列 nE.g. X=(A, B, C, B, D, A, B)Y=(B, D, C, A, B, A)子序列: Z1=(B, C, A), 長(zhǎng)度3 Z2=(B,C, B, A)，長(zhǎng)度4設(shè)序列X(m)=x1,x2,xm和Y(n)=y1,y2,yn的最長(zhǎng)公共子序列為Z(k)=z1,z2,zk ，則(1)若xm=yn，則zk=xm=yn，且Z(k-1)=z1, z2,zk-1 是X(m-1)= x1,x2,xm-1和Y(n-1

18、)=y1,y2,yn-1的最長(zhǎng)公共子序列BCBAX(m) :CBAY(n) :BBCBX(m-1) :Y(n-1) : Z(k) :CBBA Z(k-1) :CBBCBB問(wèn)題規(guī)模前綴前綴n問(wèn)題歸結(jié)：原問(wèn)題 子問(wèn)題(問(wèn)題規(guī)模更小) 原問(wèn)題: X(m), Y(n), 最優(yōu)解:Z(k)X(m-1), Y(n-1)X(m-1), Y(n)X(m), Y(n-1)（1）（2）（3）子問(wèn)題最優(yōu)解： Z(k-1) Z(k) Z(k) 上述3種情況下，原問(wèn)題最優(yōu)解包括了子問(wèn)題最優(yōu)解！前綴前綴3種情況：(2)若xmyn且zkxm，則Z(k)是x(m-1)和Y(n)的最長(zhǎng)公共子序列BCBACBABBCBCBBAX

19、(m) :Y(n) :X(m-1) : Z(k) :問(wèn)題規(guī)模前綴前綴A(3)若xmyn且zkyn，則Z(k)是X(m)和y(n-1)的最長(zhǎng)公共子序列BCBACBABCBBACBABX(m) :Y(n-1) :Y(n) : Z(k) :問(wèn)題規(guī)模 前綴前綴由此可見，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴前綴(i.e. 子問(wèn)題子問(wèn)題)的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。 根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。 cij：序列X(i)和Y(j)的最長(zhǎng)公共子序列的長(zhǎng)度，X(i)=x1,x2,xi；Y(j)=y1,y2,yj。 當(dāng)i=0或j=0時(shí)，即

20、其中1個(gè)序列為空，則空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)Cij=0。 其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：00,0 11 1,0;max 1, 1 ,0;ijijijc ijc iji jxyc ijc iji jxy或3種情況 對(duì)X(m)和Y(n)，總共有(mn)個(gè)不同的子問(wèn)題，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值，以提高算法效率。void LCSLength(int m，int n，char *x，char *y，int *c， int *b)數(shù)組x*和y*：存儲(chǔ)2個(gè)輸入序列X(m)、Y(n)輸出數(shù)組c：cij存儲(chǔ)序列Xi、Yj的最長(zhǎng)公共子序列的長(zhǎng)度輸出數(shù)組b： bij 記

21、錄cij的值是由哪個(gè)子問(wèn)題得到的(3種情 況之一)，構(gòu)造最長(zhǎng)公共子序列時(shí)用到X(i)=x1,x2,xi, 1i m；Y(j)=y1,y2,yj, 1j n；void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; /*初始化, Yj為空時(shí) for (i = 1; i = n; i+) c0i = 0; /*初始化， Xi為空時(shí) for (i = 1; i = m; i+) /*兩重循環(huán)，自下而上， 計(jì)算子問(wèn)題X(i), Y(j) for (j = 1; j

22、 =cij-1) /*情況2 cij=ci-1j; bij=2; else cij=cij-1; /*情況3 bij=3; 每個(gè)數(shù)組單元的計(jì)算耗時(shí)O(1)，算法耗時(shí)：O(mn)算法LCSLength構(gòu)造了數(shù)組bij，據(jù)此可遞歸構(gòu)造出X(i)、Y(j)的最長(zhǎng)公共子序列：void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1, j-1, x, b); coutxi; /*第1種情況下，X(i)和Y(j)的最長(zhǎng)公共子序列由X(i-1)和 Y(j-1)的解LCS(i-1, j-1, x, b)，加

23、上位于最后的，加上位于最后的Xi 組成組成 else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b); /*其它2種情況下，原問(wèn)題解 等于子問(wèn)題解過(guò)程： 從bm,n開始，依其值在數(shù)組b中搜索。1） bi,j=1, Xi和Yj的最長(zhǎng)公共子序列由Xi-1和Yj-1的最長(zhǎng)公共子序列，在尾部加上xi得到2） bi,j=2, Xi和Yj的最長(zhǎng)公共子序列與Xi-1和Yj的的最長(zhǎng)公共子序列相同3） bi,j=3, Xi和Yj的最長(zhǎng)公共子序列與Xi和Yj-1的的最長(zhǎng)公共子序列相同算法中，每次遞歸調(diào)用使i或j減一，算法的計(jì)算時(shí)間為O(m+n)在算法lcsLengt

24、h和lcs中，可進(jìn)一步將數(shù)組b省去： 數(shù)組元素cij的值僅由ci-1j-1，ci-1j和cij-1這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素cij，可以不借助于數(shù)組b而僅借助于c本身在O(1)時(shí)間內(nèi)確定cij的值是由ci-1j-1，ci-1j和cij-1中哪一個(gè)值所確定的。如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少： 在計(jì)算cij時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n)。最大子段和n給定n個(gè)整數(shù)組成的序列序列a1,a2,an，求該序列形如 ，1i、j n, 的子段和的最

25、大值nE.g. -2, 11, -4, 13, -5, -2，最大子段和 =20 子段的起點(diǎn)i、長(zhǎng)度、終點(diǎn)j不固定jkk ia42kka一、簡(jiǎn)單算法 用數(shù)組a存儲(chǔ)給定的n個(gè)整數(shù)a1,a2,an，注意到，采用2重循環(huán)，計(jì)算復(fù)雜性為O(n2)1jjkjkk ik iaaa int MaxSum(int n, int *a，int &besti, int &bestj) int sum=0 for (int i = 1; i = n; i+) int thissum=0; for (int j=i; i sum) sum=thissum; besti=i; bestj=j return sum i:

26、 1nij: injjkk ia2重循環(huán)55n問(wèn)題采用二維表述MaxSum(i, j)，算法兩重循環(huán)，導(dǎo)致二次項(xiàng)復(fù)雜性O(shè)(n2)自上而下分治算法n目標(biāo)：進(jìn)一步改進(jìn)算法復(fù)雜性n將序列a1:n分解為長(zhǎng)度相等的2段a1:n/2和an/2+1:n，分別求出這2個(gè)子段的和，與a1:n的最大子段和相比，有三種情況1） a1:n/2與a1:n的最大子段和相同 最大子段落在前半部分2） an/2+1:n與a1:n的最大子段和相同 最大子段落在后半部分3） a1:n的最大子段和為 ，并且1i n/2, n/2+1 j n 最大子段橫跨中點(diǎn)jkk ian對(duì)第3種情況，an/2和an/2+1 一定在最優(yōu)子序列中：1

27、) 在a1:n/2中計(jì)算出S1=2) 在an/2+1:n中計(jì)算出S2=3) 最優(yōu)值： S1+S2/21/2maxnki nk ia jkk iaan/2+1*an/2/2 1/2 1maxjknj nk na ijleftsleftsumrightsrightsum int MaxSubSum(int *a, int left, int right) 數(shù)組 子段左界 子段右界 int sum=0 if (left= =right) sum=aleft 0 ? aleft:0; else int center=(left+right)/2; 一分為二 int leftsum= MaxSubSum

28、(a, left, center); 求左子段最優(yōu)值 int rightsum=MaxSubSum(a, center+1, right,); 求右子段最優(yōu)值 int s1=0; int lefts=0; for (int i=center; i = left; i-) /*假設(shè)為第3種情況， 求左子段中的最優(yōu)子段和值s1，由中點(diǎn)開始，自右向左搜索 lefts+=aj; if (leftss1) s1=lefts; int s2=0; int rights=0; for (int i=center+1; i s2) s2=rights; sum=s1+s2; 與第1、第2種情況比較 if (s

29、umleftsum) sum=leftsum; if (sum0時(shí)，時(shí)，bj=bj-1+aj， 當(dāng)當(dāng)bj-1=0時(shí)時(shí), bj=ajn故得到如下遞歸方程： max 1 , ,1b jb ja j a jjn問(wèn)題：a1, a2, , aj-1, aj, 指標(biāo)：bj 子問(wèn)題: a1, a2, , aj-1, 指標(biāo): bj-1 子問(wèn)題: aj, 指標(biāo): ajnint MaxSum(int n, int *a) /*計(jì)算長(zhǎng)度為n的最大子段和 int sum=0; b=0; for (int i = 1; i 0) b+=ai; else b=ai; if (bsum) sum=b; return sum

30、; 從序列左端第1個(gè)元素a1開始，自左向右，根據(jù)遞歸方程，逐步計(jì)算bi, 1in。 算法時(shí)間、空間復(fù)雜性均為O(n)。-2, 11, -4, 13, -5, -2用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P=v0,v1,vn-1表示具有n條邊的凸多邊形。若vi與vj是多邊形上不相鄰的2個(gè)頂點(diǎn)，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個(gè)多邊形vi,vi+1,vj和vj,vj+1,vi。多邊形的三角剖分多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T三角形頂點(diǎn)：凸多邊形頂點(diǎn)，邊：多邊形邊、弦。最優(yōu)值？！：給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w（如歐

31、氏距離）。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小 最優(yōu)值。 示例： 利用三角剖分，計(jì)算GSM/CDMA網(wǎng)絡(luò)小區(qū)覆蓋范圍Voronoi圖矩陣連乘/表達(dá)式的完全加括號(hào)方式問(wèn)題與三角剖分問(wèn)題具有相似性對(duì)應(yīng)于相同理論模型，可相互歸結(jié)(reduction): 1）多個(gè)矩陣的排列順序 對(duì)應(yīng)于圖中頂點(diǎn)排列順序 2）序列中2個(gè)矩陣的加括號(hào) (Ai Al) 對(duì)應(yīng)于 頂點(diǎn)Ai 與Al間的邊或弦表達(dá)式的完全加括號(hào)問(wèn)題可以表示為一棵完全二叉樹，稱為表達(dá)式的語(yǔ)法樹 e.g. 完全加括號(hào)的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語(yǔ)法樹如圖 (a)所示。vk(A1(A2A3)(

32、A4(A5A6)多出的一條邊n個(gè)矩陣連乘A1,n對(duì)應(yīng)于凸(n+1)邊形的三角剖分凸多邊形v0,v1,vn-1的三角剖分也可以用語(yǔ)法樹表示。例如，圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語(yǔ)法樹表示：1） 樹根節(jié)點(diǎn)對(duì)應(yīng)V0V62）葉節(jié)點(diǎn)對(duì)應(yīng)邊Vi-1Vi3）非葉結(jié)點(diǎn)對(duì)應(yīng)剖分多邊形的弦邊三角剖分與矩陣連乘積對(duì)應(yīng)關(guān)系1. 矩陣連乘積中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。2. 三角剖分中的一條弦vivj，ij，對(duì)應(yīng)于矩陣連乘積Ai+1:j。凸多邊形的最優(yōu)三角剖分問(wèn)題有最優(yōu)子結(jié)構(gòu)性質(zhì)： 根據(jù)頂點(diǎn)vk，將序列分為2部分v0,v1,vk、 vk+1,v1,vn-1 若凸(n+

33、1)邊形P=v0,v1,vn-1的最優(yōu)三角剖分T包含三角形v0vkvn，1kn-1，例如圖(b)中的V3 ，則T的權(quán)為3個(gè)部分權(quán)的和：1）三角形v0vkvn的權(quán)， e.g. v0v3v62）子多邊形v0,v1,vk權(quán), e.g. v0v1v2v33) 子多邊形vk,vk+1,vn權(quán), e.g.v3v4v5v6子問(wèn)題劃分：一分為三可以斷言： 由T所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。 因?yàn)槿粲衯0,v1,vk或vk,vk+1,vn的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。 問(wèn)題/子問(wèn)題形式化表述： j-i+2個(gè)頂點(diǎn)組成的多邊形Pvi-1,vi,vj, 1i j n問(wèn)題/子問(wèn)題最優(yōu)化

34、目標(biāo) tij，1ijn, 凸子多邊形vi-1,vi,vj的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值。 為方便起見，設(shè)退化的多邊形vi-1,vi具有權(quán)值0。原問(wèn)題目標(biāo)：凸(n+1)邊形P的最優(yōu)權(quán)值為t1n最小化72n問(wèn)題歸結(jié)：原問(wèn)題 子問(wèn)題(問(wèn)題規(guī)模更小) 原問(wèn)題: Pvi-1,vi,vj, 最優(yōu)解:ti,jPvi-1,vi,vkTravi-1,vk,vjPvk,vk+1,vj（1）（2）（3）e.g. i=0, k=3, j=6vk(A1(A2A3)(A4(A5A6) 子問(wèn)題最優(yōu)解： tvi-1, vk wvi-1vkvj tvk+1, vj 73tij的值利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算:1) 當(dāng)j-i1時(shí)

35、，凸子多邊形至少有3個(gè)頂點(diǎn)。 /* vi-1,vi,vj2) 用頂點(diǎn)vk, 進(jìn)行子問(wèn)題劃分3）由最優(yōu)子結(jié)構(gòu)性質(zhì)，tij的值應(yīng)為tik的值加上tk+1j的值，再加上三角形vi-1vkvj的權(quán)值，其中ikj-1由于在計(jì)算時(shí)還不知道k的確切位置，而k的所有可能位置只有j-i個(gè)，因此可以在這j-i個(gè)位置中選出使tij值達(dá)到最小的位置由此，tij可遞歸地定義為：jijivvvwjktkitjitjkijki)(1min010606006min 0 16()kkijttkt kw v v vij e.g. void MinWeightTriangulation(int n，Type * t, int *s

36、) for (int i = 1; i = n; i+) tii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n-r+1; i+) int j= i + r 1 tij = ti+1j + w(i-1, i, j) sij =i; for (int k =i+1; k i+r-1; k+) int u=tik + tk+1j + W(i-1,k,j); if (u10,000，采用復(fù)雜性階次較高的動(dòng)態(tài)規(guī)劃算法求解，運(yùn)行時(shí)間過(guò)長(zhǎng)，不具有實(shí)用性！nE.g. 見下頁(yè)例子87Assume N = 100,000 and processor s

37、peed is 1,000,000,000 operations per second(10億次/秒，普通微機(jī)運(yùn)算速度)FunctionRunning Time2N3.2 x 1030086 yearsN43171 yearsN311.6 daysN210 secondsN N0.032 secondsN log N0.0017 secondsN0.0001 seconds N3.2 x 10-7 secondslog N1.2 x 10-8 seconds88n假設(shè)單核微機(jī) 1. 主頻為 F=3GHz=3 109次/每秒 2. 1個(gè)機(jī)器指令周期時(shí)長(zhǎng) t=1/F = (1/3) * 10-9

38、秒 3. 1條指令平均需要3個(gè)周期，則1條指令平均執(zhí)行時(shí)間為 (3/3) * 10-9 秒nCPU運(yùn)算速度： 每秒執(zhí)行的指令數(shù)目 = 1 / 1條指令平均執(zhí)行時(shí)間 = (3/3) * 109 條/秒 = 10億條指令/秒 n如果基于微機(jī)平臺(tái)，采用動(dòng)態(tài)規(guī)劃三角剖分方法，如果基于微機(jī)平臺(tái)，采用動(dòng)態(tài)規(guī)劃三角剖分方法，計(jì)算基站計(jì)算基站Voronoi圖，當(dāng)基站數(shù)目圖，當(dāng)基站數(shù)目n10,000時(shí)，運(yùn)行時(shí)，運(yùn)行時(shí)間時(shí)間2-3天，不可接受天，不可接受!89動(dòng)態(tài)規(guī)劃法的適用性動(dòng)態(tài)規(guī)劃法的適用性n需要結(jié)合實(shí)際問(wèn)題背景，優(yōu)化算法，降低算法復(fù)雜性 分析遞歸表達(dá)式，避免過(guò)度搜索子問(wèn)題的各種組合，根據(jù)啟發(fā)式信息，選取某一

39、種或少數(shù)某幾種組合由求解全局最優(yōu)解（最小、最大），改為求解全局次優(yōu)解（比較小、比較大）nE.g. 三角剖分n不需要搜索、比較Pvi-1,vi,vj中的每個(gè)vk，而是按照一定啟發(fā)式信息，優(yōu)先選取某個(gè)剖分點(diǎn)vk，e.g. vk= v3，避免最內(nèi)層循環(huán)，將算法復(fù)雜性由O(n3) 降為O(n2)jijivvvwjktkitjitjkijki)(1min01. 窮搜90void MinWeightTriangulation(int n，Type * t, int *s) for (int i = 1; i = n; i+) tii = 0; for (int r = 2; r = n; r+) /*第1

40、層循環(huán) for (int i = 1; i = n-r+1; i+) /*第2層循環(huán) int j= i + r 1 tii = ti+1j + w(i-1, i, j) sii =i; for (int k =i+1; k i+r-1; k+) int u=tik + tk+1j + W(i-1,k,j); if (utij) tij) =u; sij) =k; 利用啟發(fā)式信息，在第2層循環(huán)內(nèi)部，直接選取某個(gè)vk，避免第3層循環(huán)，算法時(shí)間復(fù)雜性降為O(n2)Z找到更好的劃分，并記錄結(jié)果t: 記錄子問(wèn)題最優(yōu)值s：記錄子問(wèn)題最優(yōu)劃分點(diǎn) 子問(wèn)題vi、vj, 子問(wèn)題規(guī)模r=j-i+1自下而上，不同規(guī)模

41、r的子問(wèn)題ii+1j91動(dòng)態(tài)規(guī)劃法的適用性動(dòng)態(tài)規(guī)劃法的適用性nE.g. 利用啟發(fā)式（而非動(dòng)態(tài)規(guī)劃）三角剖分算法，得到以基站為頂點(diǎn)的Delaunay三角網(wǎng)有多種啟發(fā)式構(gòu)造方法n在此基礎(chǔ)上轉(zhuǎn)換為Voronoi圖，計(jì)算全網(wǎng)基站覆蓋范圍n優(yōu)點(diǎn)：算法運(yùn)行時(shí)間可接受，e.g. 4小時(shí)左右n缺點(diǎn)： 1. 有可能無(wú)法完全滿足三角剖分要求，極少部分的弦相交 2. Delaunay三角網(wǎng)上的各三角形邊之和有可能非全局最小，而只是局部極小、比較小n實(shí)際問(wèn)題中，從實(shí)用性、適用性角度，實(shí)際問(wèn)題中，從實(shí)用性、適用性角度， tradeoff ! between 算法解質(zhì)量算法解質(zhì)量and 算法運(yùn)行時(shí)間算法運(yùn)行時(shí)間解質(zhì)量：解

42、質(zhì)量：是否達(dá)到全局最大、最小是否達(dá)到全局最大、最小多邊形游戲是一個(gè)單人玩的游戲，開始時(shí)有一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的多邊形。每個(gè)頂點(diǎn)被賦予一個(gè)整數(shù)值，每條邊被賦予一個(gè)運(yùn)算符“+”或“*”。所有邊依次用整數(shù)從1到n編號(hào)。游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：(1)選擇一條邊E以及由E連接著的2個(gè)頂點(diǎn)V1和V2；(2)用一個(gè)新的頂點(diǎn)取代邊E以及由E連接著的2個(gè)頂點(diǎn)V1和V2。將由頂點(diǎn)V1和V2的整數(shù)值通過(guò)邊E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。問(wèn)題:對(duì)于給定的多邊形，計(jì)算最高得分。102294153627v7v1v2v3v4v5v

43、6+*1234567102294153627v7v1v2v3v4v5v6+*234567Step1: 1022v7v1+1v7Step2: 1022v7v1+132v17102294153627v1v2v3v4v5v6+*234567Step2: 32v1794153627v2v3v4v5v6+*234567頂點(diǎn)減為6個(gè)Step3: v173294153627v2v3v4v5v6+*23567415v3v4+419v34Step3: v173293627v2v5v6+*2356719v34頂點(diǎn)減為5個(gè)n游戲的得分/最優(yōu)值： 最后所剩頂點(diǎn)上的整數(shù)值n目標(biāo)：最大化最后所剩頂點(diǎn)上的整數(shù)值n問(wèn)題解的結(jié)

44、構(gòu)： 不同的刪除邊、合并頂點(diǎn)的順序問(wèn)題形式化表述問(wèn)題形式化表述p(i，j) ： 在所給多邊形中，從頂點(diǎn)i(1in)開始，長(zhǎng)度為j(鏈中有j個(gè)頂點(diǎn))的順時(shí)針鏈p(i，j) 可表示為： vi, opi+1, , opi+j-2, vi+j-1e.g. i=2, j=5 p(2,5): v2, *, v3, +, v4, *, v5, +, v6 op3+1=+,94153627v2v3v4v5v6+*3456 如果這條鏈的最后一次合并運(yùn)算最后一次合并運(yùn)算在opi+s處發(fā)生(1sj-1)，則可在opi+s處將鏈p(i，j)分割為2個(gè)子鏈： 1）p(i,s) 2）p(i+s, j-s) E.g. 1)

45、 i=2, j=5 , s=2, opi+2=op4=op3+1=+2) p(i,s)=p(2,2): v2, *, v33) p(i+s, j-s)=p(4, 3): v4, *, v5, +, v6 P(i, s) 與子鏈的關(guān)系與子鏈的關(guān)系由由2條子鏈合并而成條子鏈合并而成93627v2v5v6+*35619v3494153627v2v3v4v5v6+*3456p(i,s)=p(2,2) m1= 36p(i+s, j-s)=p(4, 3) m2=max(36+27)*15, 27+36*15設(shè)m1是對(duì)子鏈p(i，s)的任意一種合并方式得到的值，而a和b分別是在所有可能的合并中得到的最小值和

46、最大值。e.g. p(i,s)=p(2,2), m1=9*4=36m2是p(i+s，j-s)的任意一種合并方式得到的值，而c和d分別是在所有可能的合并中得到的最小值和最大值。 e.g. p(i+s, j-s)=p(4, 3), 15*36 +27 m2 (27+36)*5 依此定義有am1b，cm2d 子鏈p(i，s)和p(i+s，j-s)的合并方式?jīng)Q定了p(i, j)在opi+s處斷開后的合并方式，在opi+s處合并后其值為 m=(m1) opi+s (m2)e.g. opi+s =op2+2=op3+1=+,有以下性質(zhì)：(1)當(dāng)opi+s=+時(shí)，顯然有a+cmb+d(2)當(dāng)opi+s=*時(shí)

47、，有minac，ad，bc，bdmmaxac，ad，bc，bd 換句話說(shuō)，主鏈的最大值和最小值可由子鏈的最大換句話說(shuō)，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。值和最小值得到。 遞歸求解n需要同時(shí)求子鏈P(i, j)=vi, opi+1, , opi+j-2, vi+j-1合并的最大最小值n最優(yōu)化目標(biāo)： mi,j,0：p(i,j)合并的最小值 mi,j,1： p(i,j)合并的最大值合并的最大值n最優(yōu)合并在opi+s處將p(i,j)分為2個(gè)長(zhǎng)度小于j的子鏈p(i,s)和p(i+s, j-s)n記2個(gè)子鏈合并后的最大最小值為 a= mi, i+s, 0, b= mi, i+s, 1 c=

48、 mi+s, j-s, 0, d= mi+s, j-s, 1n將p(i, j)在opi+s處斷開后的最大值記為 maxf(i, j, s) , 最小值記為 minf(i, j, s) e.g. maxf(2, 5, 2)minf(i, j, s)= 1) a+c opi+s=+2) minac, ad, bc, bd, opi+s=*maxf(i, j, s)=1) b+d opi+s=+2) maxac, ad, bc, bd, opi+s=*最優(yōu)斷開位置s有1s j-1共j-1種情況，故有如下遞歸方程：1） m(i, j, 0) = min minf(i, j, s), 1s j, 1i,

49、 j n m(i, j, 1) = max maxf(i, j, s), 1s j, 1i, j n2）邊界條件 m(i, 1, 0) = vi, 1i n; m(i, 1, 1) = vi, 1i n;方法：采用圖像變位壓縮存儲(chǔ)格式1) 將所給的象素點(diǎn)序列p1, p2,pn, 0pi255, 分割成m個(gè)連續(xù)段S1,S2,Sm2) 第i個(gè)象素段Si中(1im)，有l(wèi)i個(gè)象素,且該段中每個(gè)象素都只用bi (8) 位表示 計(jì)算機(jī)中，一幅有n個(gè)像素點(diǎn)的圖像用象素點(diǎn)灰度值序列p1, p2, pn表示, 整數(shù)pi, 1in, 表示圖像中像素點(diǎn)i的灰度值, 范圍在0255，1個(gè)像素點(diǎn)最多最多用8 bits

50、表示，。 E.g. iPhone4：Retina屏幕， 3.5英寸640960像素, 點(diǎn)距0.007705cm，像素密度326像素/英寸(ppi)，1600萬(wàn)色目標(biāo)：如何用更少的bits表示不同的像素點(diǎn)灰度值灰度值小，用的bits少方法：采用圖像變位壓縮存儲(chǔ)格式1) 將所給的象素點(diǎn)序列p1, p2,pn, 0pi255, 分割成m個(gè)連續(xù)段S1,S2,Sm2) 第i個(gè)象素段Si中(1im)，有l(wèi)i個(gè)象素,且該段中每個(gè)象素都只用bi (8) 位表示0 1 7 3 5 9 13 11 15 33 35 41 44 51 39 219 241 180 209015，9個(gè)像素, 4bits3263，6個(gè)

51、像素, 6bits128255，4個(gè)像素, 8bits等長(zhǎng)存儲(chǔ): (9 + 6 + 4)*8 = 152 bits;3段變長(zhǎng)存儲(chǔ)：9*4 + 6*6 + 4*8 = 104 bits2段劃分設(shè) ，表示前i-1個(gè)段的像素總數(shù)，則第i個(gè)象素段Si為11ikklit,1ilititippS, 1 i m， 見下頁(yè) 一幅圖像的鄰近區(qū)域內(nèi)的顏色一般相近，需要使用的表達(dá)顏色的bits相近S1S2S3p1pnS1S2SmSi第i段有l(wèi)i個(gè)象素，每個(gè)像素用bi bits表示前i-1個(gè)段的像素總數(shù)ti,1ilititippS第i段像素集合：Si-1前i-1個(gè)段像素為： p1,p2, , ptipti11ikkl

52、it對(duì)第Si段，設(shè) ，表示該段像素值最大的像素所需灰度值存儲(chǔ)位數(shù)，hi=bi8。存儲(chǔ)空間分析：需要表示出每段的段長(zhǎng)、該段所用位數(shù)每段的段長(zhǎng)、該段所用位數(shù)1）對(duì)Si段中每一個(gè)像素pi，其需要的灰度值存儲(chǔ)需要一定的位數(shù)bi來(lái)存儲(chǔ), 需要3 bits表示bi的大小2）假設(shè)Si段中的像素總數(shù)li限制為1 li 255，需要用8bits表示li的數(shù)值3）第i個(gè)象素段所需的存儲(chǔ)空間為li*bi+11位4）按此格式存儲(chǔ)象素序列p1,p2,pn，分成m段，需要 bits 的存儲(chǔ)空間。1maxlog1kilitkitiphmibilmi11*1位數(shù)bi=300000長(zhǎng)度li=4011100第Si段有4個(gè)像素，每

53、個(gè)像素占3bits總位數(shù)23 bits = 3 + 8 + 4*3 確定象素序列p1, p2, pn的最優(yōu)分段，使得依此分段所需的存儲(chǔ)空間最少, 約束條件： 每個(gè)分段的長(zhǎng)度不超過(guò)256，即每個(gè)分段中的像素總數(shù)不超過(guò)256優(yōu)化變量：分段數(shù)目、每段段長(zhǎng)目標(biāo)：總存儲(chǔ)空間極小化設(shè)li, bi, 1i m, 是p1,p2,pn的最優(yōu)分段。 顯而易見，見下頁(yè)1) l1, b1是p1,pl1的最優(yōu)分段 2) li, bi， 2i m, 是pl1+1,pn的最優(yōu)分段 , 即圖象壓縮問(wèn)題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。原問(wèn)題: p1,p2,pn，解: m段，每段長(zhǎng)li, 位數(shù)bi, 1i m子問(wèn)題1: 第1段p1, pl1

54、, 解: l1, b1子問(wèn)題2: 剩余部分pl1+1 , , pn, 解: li, bi, 2i m p1pnS1S2SmSili個(gè)象素，每個(gè)像素用bi bits表示前i-1個(gè)段的像素總和ti,1ilititippS第i段像素集合：Si-1l1個(gè)象素，用b1 bits表示 設(shè)si，1in，是前i個(gè)象素序列p1,pi的最優(yōu)分段所需的存儲(chǔ)位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)易知：其中11), 1max(b*min256,min1ikikkisisik1maxlog),bmax(kjkipji1bmax(1, )logmax 1ki kk iikip 表示最后1段的長(zhǎng)度、位數(shù)最后一段i-k+1像素所占位數(shù)p1pi

55、pi-k斷點(diǎn)1k 256第2個(gè)子問(wèn)題pi-k+1, pi, 1）長(zhǎng)度k，有k個(gè)像素。2）由于每段長(zhǎng)度=256，因此斷點(diǎn)k的位置最多有256個(gè)；再考慮到原問(wèn)題的長(zhǎng)度有可能小于256，因此斷點(diǎn)位置: 1k min(256,i)3）最后一段pi-k+1, pi, 有k個(gè)像素，每個(gè)像素最多需要的存儲(chǔ)位數(shù)原問(wèn)題： p1, pi-k, pi-k+1,pi，長(zhǎng)度i子問(wèn)題1: p1, pi-k, 長(zhǎng)度i-k子問(wèn)題2:pi-k+1, pi, 長(zhǎng)度k最優(yōu)解si最優(yōu)解si-k最后1段1bmax(1, )logmax 1ki kk iikip 算法復(fù)雜度分析：算法復(fù)雜度分析：由于算法compress中對(duì)k的循環(huán)次數(shù)不

56、超這256，故對(duì)每一個(gè)確定的i，可在時(shí)間O(1)內(nèi)完成的計(jì)算。因此整個(gè)算法所需的計(jì)算時(shí)間為O(n)119 給定n種物品1, 2, 3, ,n和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。 問(wèn)：應(yīng)如何選擇裝入背包的物品，使得裝入背包中裝入背包中物品的總價(jià)值最大?0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題： 找出1個(gè)n元0-1向量(x1,x2,xn), xi0,1, 1in, 使得niiixv1maxnixCxwiniii1,1 , 01120n最優(yōu)子結(jié)構(gòu)性質(zhì) 設(shè)(x1,x2,xn)是相對(duì)于n種物品1, 2, 3, ,n的1個(gè)最優(yōu)解，則(x2,xn)是子問(wèn)題2,3,4,n的1個(gè)最優(yōu)解，即

57、原問(wèn)題最優(yōu)解包括了子問(wèn)題最優(yōu)解證明：反證法2maxniiiv x20,1,2niiiiw xCxin 121原問(wèn)題：n種物品1, 2, 3, ,n子問(wèn)題2：n-1種物品2, 3, ,n解: (x1,x2,xn)(最優(yōu))解: (x2,xn)(最優(yōu))子問(wèn)題1：1解: (x1)122n問(wèn)題的形式化表示： n個(gè)物品的背包問(wèn)題的2個(gè)因素：1）物品1, 2, 3, , n2) 背包容量C將n個(gè)物品背包問(wèn)題的不同子問(wèn)題表示為：1）i：子問(wèn)題i, i+1, , n的起點(diǎn)2）j: 子問(wèn)題的背包容量12 i-1 i i+1 n-1 n原問(wèn)題子問(wèn)題原問(wèn)題表示為123給定n個(gè)物品1,2,n, 其子問(wèn)題定義為：nikk

58、kxvmaxnkixjxwknikkk,1 , 0 子問(wèn)題的最優(yōu)值定義為m(i, j)，即m(i, j)是背包容量為j，可選擇物品為i, i+1, , n時(shí)0-1背包問(wèn)題的最優(yōu)值。 原問(wèn)題的最優(yōu)解可表示為m(1, c)124n根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i, j)的遞歸式: 1）邊界條件：對(duì)于只有1個(gè)物品n、背包容量為j的子問(wèn)題( , )00nnnjwvm n jjw容量j大于物品n的重量wn，n可放入背包，放入后價(jià)值為vn容量j小于物品n的重量wn，n無(wú)法放入背包，價(jià)值為01252）對(duì)子問(wèn)題說(shuō)明：考察子問(wèn)題中的物品i, i+1, i+2, , n-1, n， i ) 如果第i種物品重

59、量wi大于容量j，可以不考慮第i種物品，子問(wèn)題縮減為規(guī)模更小的ii)如果第i種物品重量wi小于容量j，第i種物品可以考慮放入，分為2種情況： *情況1：將第i種物品放入，對(duì)總價(jià)值的貢獻(xiàn)為vi，剩余容量為jwi ，子問(wèn)題縮減為規(guī)模更小的 *情況2：第i種物品不放入，背包容量仍為j ，子問(wèn)題縮減為規(guī)模更小的(0,1) (1, ),(1,)( , )0(1, )maxiiiixim ij m ijwvjwm i jjwm ij126: i, i+1, i+2, , n-1, n: i+1, i+2, , n-1, nijwiwj是否放入物品i放入不放背包無(wú)法容納物品i背包可以容納物品i: i+1,

60、i+2, , n-1, n: i+1, i+2, , n-1, nXi=0Xi=0Xi=1127Knapsack算法：算法：p73算法復(fù)雜度分析：算法復(fù)雜度分析： 從m(i, j)的遞歸式容易看出，算法需要O(nc)計(jì)算時(shí)間 當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算時(shí)間較多。 例如，當(dāng)c2n時(shí)，算法需要(n2n)計(jì)算時(shí)間。 128n說(shuō)明： 子問(wèn)題表示方法的設(shè)計(jì)是關(guān)鍵，不同子問(wèn)題表示方法影響到問(wèn)題分解/合成、遞歸方程、算法實(shí)現(xiàn)方法、效率E.g. 1. 矩陣連乘：Ai, j = O(n3)2. 最長(zhǎng)公共子序列中的X(m)=x1,x2,xm和Y(n)=y1,y2,yn，Z(k), Cmn, O(m+n)3