第3章動態(tài)規(guī)劃

1、1)E-mail: weiliu_Tel: 135748184482 動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=3 但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復(fù)計算了許多次。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)4 如果能夠保存已解決的子問題的答案，而在

2、需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法。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)5 找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 遞歸地定義最優(yōu)值。 以自底向上的方式計算出最優(yōu)值。 根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。6（1）單個矩陣是完全加括號的；（2）矩陣連乘積 是完全加括號的，則 可 表示為2個完全加括號的矩陣連乘積 和 的乘積并加括號，即 AABC)(BCADCBA , , ,1050A4010B3040C530D)(DBCA)

3、(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 36000, 87500, 34500u完全加括號的矩陣連乘積可遞歸地定義為：u設(shè)有四個矩陣 ，它們的維數(shù)分別是：u總共有五種完全加括號的方式7n給定n個矩陣 ， 其中 與 是可乘的， ?？疾爝@n個矩陣的連乘積 n由于矩陣乘法滿足結(jié)合律，所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。n若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法計算出矩陣連乘積,.,21nAAAiA1iA1,.,2 , 1ninAAA.218 給定n個矩

4、陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1,2 ,n-1。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少數(shù)乘次數(shù)最少。u窮舉法窮舉法：列舉出所有可能的計算次序，并計算出每一種計算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。 算法復(fù)雜度分析：算法復(fù)雜度分析：對于n個矩陣的連乘積，設(shè)其不同的計算次序為P(n)。由于每種加括號方式都可以分解為兩個子矩陣的加括號問題：(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk9u動態(tài)規(guī)劃動態(tài)規(guī)劃將矩陣連乘積 簡記為Ai

5、:j ，這里ij jiiAAA.1考察計算Ai:j的最優(yōu)計算次序。設(shè)這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，ikj，則其相應(yīng)完全加括號方式為).)(.(211jkkkiiAAAAAA計算量：Ai:k的計算量加上Ak+1:j的計算量，再加上Ai:k和Ak+1:j相乘的計算量10 特征：計算Ai:j的最優(yōu)次序所包含的計算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。 矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。11n設(shè)計算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原

6、問題的最優(yōu)值為m1,n n當(dāng)i=j時，Ai:j=Ai，因此，mi,i=0，i=1,2,nn當(dāng)ij時，n可以遞歸地定義mi,j為：jkipppjkmkimjim1, 1,這里 的維數(shù)為 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 種可能kij 12n對于1ijn不同的有序?qū)?i,j)對應(yīng)于不同的子問題。因此，不同子問題的個數(shù)最多只有n由此可見，在遞歸計算時，許多子問題被重復(fù)計算多許多子問題被重復(fù)計算多次次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。n用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向依據(jù)其遞歸式以自底向上的方式進行計算上的方式進行

7、計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復(fù)計算，最終得到多項式時間的算法)(22nnn13public static void matrixChain(int p, int m, int s) int n=p.length-1; for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (i

8、nt k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t 0) return mij; if (i = j) return 0; int u = lookupChain(i+1,j) + pi-1*pi*pj; sij = 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; sij = k; mij = u; return u; 17 若給定序列X=x1,x2,xm，則另一

9、序列Z=z1,z2,zk，是X的子序列是指存在一個嚴格遞增下標(biāo)序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。 給定2個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列公共子序列。 給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。 18設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最

10、長公共子序列。(2)若xmyn且zkxm，則Z是xm-1和Y的最長公共子序列。(3)若xmyn且zkyn，則Z是X和yn-1的最長公共子序列。由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)最優(yōu)子結(jié)構(gòu)性質(zhì)構(gòu)性質(zhì)。 19由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列和的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時Cij=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：jijiyxjiyxjijijicj

11、icjicjic; 0,; 0,0, 01,1max1 11020由于在所考慮的子問題空間中，總共有(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。 Algorithm lcsLength(x,y,b)1: mx.length-1;2: ny.length-1;3: ci0=0; c0i=0;4: for (int i = 1; i = m; i+)5: for (int j = 1; j =cij-1) 10: cij=ci-1j;11: bij=2;12: else 13: cij=cij-1;14: bij=3;構(gòu)造最長公共子序列構(gòu)造最長公共子序列Alg

12、orithm 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); System.out.print(xi); else if (bij= 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); 21在算法lcsLength和lcs中，可進一步將數(shù)組b省去。事實上，數(shù)組元素cij的值僅由ci-1j-1，ci-1j和cij-1這3個數(shù)組元素的值所確定。對于給定的數(shù)組元素cij，可以不借助于數(shù)組b而僅借助于c本身在時間內(nèi)確定cij的值是由ci-1j-1，ci-1

13、j和cij-1中哪一個值所確定的。如果只需要計算最長公共子序列的長度，則算法的空間需求可大大減少。事實上，在計算cij時，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計算出最長公共子序列的長度。進一步的分析還可將空間需求減至O(min(m,n)。22niiixv1maxnixCxwiniii1,1 , 01給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?0-1背包問題是一個特殊的整數(shù)規(guī)劃問題。23設(shè)所給0-1背包問題的子問題nikkkxvmaxnkixjxwknikkk,1 , 0的最優(yōu)值為m

14、(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i，j)的遞歸式如下。iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(nnnwjwjvjnm00),(算法復(fù)雜度分析：算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計算時間。當(dāng)背包容量c很大時，算法需要的計算時間較多。例如，當(dāng)c2n時，算法需要(n2n)計算時間。 24由m(i,j)的遞歸式容易證明，在一般情況下，對每一個確定的i(1in)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳

15、躍點是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由其全部跳躍點惟一確定。如圖所示。對每一個確定的i(1in)，用一個表pi存儲函數(shù)m(i，j)的全部跳躍點。表pi可依計算m(i，j)的遞歸式遞歸地由表pi+1計算，初始時pn+1=(0，0)。 25n=3，c=6，w=4，3，2，v=5，2，1。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0, 0)(2, 1)m(1,x)(3,2

16、)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)26函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運算得到的。因此，函數(shù)m(i,j)的全部跳躍點包含于函數(shù)m(i+1，j)的跳躍點集pi+1與函數(shù)m(i+1，j-wi)+vi的跳躍點集qi+1的并集中。易知，(s,t)qi+1當(dāng)且僅當(dāng)wisc且(s-wi,t-vi)pi+1。因此，容易由pi+1確定跳躍點集qi+1如下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另一方面

17、，設(shè)(a，b)和(c，d)是pi+1qi+1中的2個跳躍點，則當(dāng)ca且db時，(c，d)受控于(a，b)，從而(c，d)不是pi中的跳躍點。除受控跳躍點外，pi+1qi+1中的其他跳躍點均為pi中的跳躍點。由此可見，在遞歸地由表pi+1計算表pi時，可先由pi+1計算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳躍點得到表pi。27n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。初始時p6=(0,0)，(w5,v5)=(4,6)。因此，q6=p6(w5,v5)=(4,6)。p5=(0,0),(4,6)。q5=p5(w4,v4)=(5,4),(9,10)。從跳躍

18、點集p5與q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中看到跳躍點(5,4)受控于跳躍點(4,6)。將受控跳躍點(5,4)清除后，得到p4=(0,0),(4,6),(9,10)q4=p4(6，5)=(6，5)，(10，11)p3=(0，0)，(4，6)，(9，10)，(10，11)q3=p3(2，3)=(2，3)，(6，9)p2=(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)q2=p2(2，6)=(2，6)，(4，9)，(6，12)，(8，15)p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15)p1的最后的那個跳躍點(8,

19、15)給出所求的最優(yōu)值為m(1,c)=15。28上述算法的主要計算量在于計算跳躍點集pi(1in)。由于qi+1=pi+1(wi，vi)，故計算qi+1需要O(|pi+1|)計算時間。合并pi+1和qi+1并清除受控跳躍點也需要O(|pi+1|)計算時間。從跳躍點集pi的定義可以看出，pi中的跳躍點相應(yīng)于xi,xn的0/1賦值。因此，pi中跳躍點個數(shù)不超過2n-i+1。由此可見，算法計算跳躍點集pi所花費的計算時間為從而，改進后算法的計算時間復(fù)雜性為O(2n)。當(dāng)所給物品的重量wi(1in)是整數(shù)時，|pi|c+1，(1in)。在這種情況下，改進后算法的計算時間復(fù)雜性為O(minnc,2n)。 nniinniOOipO22| 1|2229 什么是二叉搜索樹？（1）若它的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；（2）若它的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；（3 它的左、右子樹也分別為二叉排序樹45125333724100619078在隨機的情況下，二叉查找樹的平均查找長度和 是等數(shù)量級的nlog30查找成功與不成功的概率二查找樹的期望耗費有 個節(jié)點的二