《第3章 動(dòng)態(tài)規(guī)劃》由會(huì)員分享，可在線閱讀，更多相關(guān)《第3章 動(dòng)態(tài)規(guī)劃（48頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,*,*,第,3,章 動(dòng)態(tài)規(guī)劃,1,動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,2,算法總體思想,動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,3,但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。,算法總體思想,n,T(n),=,n/

2、2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),4,如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。,算法總體思想,n,=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,n/2,T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),T(n/4),T(n),Those

3、who cannot remember the past are doomed to repeat it.,-George,Santayana,The life of Reason,Book I:Introduction and,Reason in Common,Sense(1905),5,動(dòng)態(tài)規(guī)劃基本步驟,找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。,遞歸地定義最優(yōu)值。,以自底向上的方式計(jì)算出最優(yōu)值。,根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。,6,完全加括號(hào)的矩陣連乘積,（,1,）單個(gè)矩陣是完全加括號(hào)的；,（,2,）矩陣連乘積 是完全加括號(hào)的，則 可,表示為,2,個(gè)完全加括號(hào)的矩陣連乘積 和,的乘積

4、并加括號(hào)，即,16000,10500,36000,87500,34500,完全加括號(hào)的矩陣連乘積可遞歸地定義為：,設(shè)有四個(gè)矩陣 ，它們的維數(shù)分別是：,總共有五中完全加括號(hào)的方式,7,矩陣連乘問(wèn)題,給定,n,個(gè)矩陣 ，其中 與 是可乘的，?？疾爝@,n,個(gè)矩陣的連乘積,由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。,若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用,2,個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積,8,矩陣連乘問(wèn)題,給定,n,個(gè)矩陣,A,1,A,2,A,n,，其中,A,i,與,A,i,+1,

5、是可乘的，,i=1,2,n-1,。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。,窮舉法,：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。,算法復(fù)雜度分析：,對(duì)于,n,個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)?P(n),。,由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：,(A,1,.,A,k,)(,A,k,+1A,n,),可以得到關(guān)于,P(n),的遞推式如下：,9,矩陣連乘問(wèn)題,窮舉法,動(dòng)態(tài)規(guī)劃,將矩陣連乘積 簡(jiǎn)記為,Ai:j,，這里,i,j,考察計(jì)算,Ai:j,的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣

6、,Ak,和,Ak,+1,之間將矩陣鏈斷開(kāi)，,i,kj,，則其相應(yīng)完全,加括號(hào)方式為,計(jì)算量：,Ai:k,的計(jì)算量加上,Ak+1:j,的計(jì)算量，再加上,Ai:k,和,Ak+1:j,相乘的計(jì)算量,10,分析最優(yōu)解的結(jié)構(gòu),特征：計(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ì),。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。,11,建立遞歸關(guān)系,設(shè)計(jì)算,Ai:j,，,1ijn,，所需要的最少數(shù)乘次數(shù),mi,j,，則原問(wèn)題的最優(yōu)值為,m1,n,當(dāng),i=j,時(shí)，,

7、Ai:j=Ai,，因此，,mi,i=0,，,i=1,2,n,當(dāng),ij,時(shí)，,可以遞歸地定義,mi,j,為：,這里 的維數(shù)為,的位置只有,種,可能,12,計(jì)算最優(yōu)值,對(duì)于,1ijn,不同的有序?qū)?(i,j),對(duì)應(yīng)于不同的子問(wèn)題。因此，不同子問(wèn)題的個(gè)數(shù)最多只有,由此可見(jiàn)，在遞歸計(jì)算時(shí)，,許多子問(wèn)題被重復(fù)計(jì)算多次,。這也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。,用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過(guò)程中，保存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法,13,用動(dòng)態(tài)規(guī)劃法求最優(yōu)解,pub

8、lic 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,(,int,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

9、,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,最長(zhǎng)公共子序列,若給定序列,X=x,1,x,2,x,m,，則另一序列,Z=z,1,z,2,z,k,，是,X,的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列,i,1,i,2,i,k,使得對(duì)于所有,j=1,2,k,有：,z,j,=,x,i,j,。例如，序列,Z=B,，,C,，,D,，,B,是序列,X=A,，,B,，,C,，

10、,B,，,D,，,A,，,B,的子序列，相應(yīng)的遞增下標(biāo)序列為,2,，,3,，,5,，,7,。,給定,2,個(gè)序列,X,和,Y,，當(dāng)另一序列,Z,既是,X,的子序列又是,Y,的子序列時(shí)，稱,Z,是序列,X,和,Y,的,公共子序列,。,給定,2,個(gè)序列,X=x,1,x,2,x,m,和,Y=y,1,y,2,y,n,，找出,X,和,Y,的最長(zhǎng)公共子序列。,18,最長(zhǎng)公共子序列的結(jié)構(gòu),設(shè)序列,X=x,1,x,2,x,m,和,Y=y,1,y,2,y,n,的最長(zhǎng)公共子序列為,Z=z,1,z,2,z,k,，則,(1),若,x,m,=,y,n,，則,z,k,=,x,m,=,y,n,，且,z,k,-1,是,x,m,

11、-1,和,y,n,-1,的最長(zhǎng)公共子序列。,(2),若,x,m,y,n,且,z,k,x,m,，則,Z,是,x,m,-1,和,Y,的最長(zhǎng)公共子序列。,(3),若,x,m,y,n,且,z,k,y,n,，則,Z,是,X,和,y,n,-1,的最長(zhǎng)公共子序列。,由此可見(jiàn)，,2,個(gè)序列的最長(zhǎng)公共子序列包含了這,2,個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有,最優(yōu)子結(jié)構(gòu)性質(zhì),。,19,子問(wèn)題的遞歸結(jié)構(gòu),由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用,cij,記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中，,X,i,=x,1,x,2,x,i,；,Yj,=y,1,y,2,y,j,。當(dāng)

12、,i=0,或,j=0,時(shí)，空序列是,X,i,和,Y,j,的最長(zhǎng)公共子序列。故此時(shí),Cij=0,。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：,20,計(jì)算最優(yōu)值,由于在所考慮的子問(wèn)題空間中，總共有,(,mn,),個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。,Algorithm,lcsLength,(x,y,b),1:m,x.length-1;,2:n,y.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:,e

13、lse,13:cij=cij-1;,14:bij=3;,構(gòu)造最長(zhǎng)公共子序列,Algorithm,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,算法的改進(jìn),在算法,lcsLength,和,lcs,中，可進(jìn)一步將數(shù)組,b,省去。事實(shí)上，數(shù)組元素,cij,的值僅由,ci-1j-1,，,ci-1j,和,cij-1,這,3

14、,個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素,cij,，可以不借助于數(shù)組,b,而僅借助于,c,本身在時(shí)間內(nèi)確定,cij,的值是由,ci-1j-1,，,ci-1j,和,cij-1,中哪一個(gè)值所確定的。,如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上，在計(jì)算,cij,時(shí)，只用到數(shù)組,c,的第,i,行和第,i-1,行。因此，用,2,行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至,O(min(m,n),。,22,凸多邊形最優(yōu)三角剖分,用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即,P=v,0,v,1,v,n,-1,表示具有,n,條邊的凸多邊形。,若,v,i

15、,與,v,j,是多邊形上不相鄰的,2,個(gè)頂點(diǎn)，則線段,v,i,v,j,稱為多邊形的一條弦。弦將多邊形分割成,2,個(gè)多邊形,v,i,v,i+1,v,j,和,v,j,v,j,+1,v,i,。,多邊形的三角剖分,是將多邊形分割成互不相交的三角形的弦的集合,T,。,給定凸多邊形,P,，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù),w,。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。,23,三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題,一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹(shù)，稱為表達(dá)式的語(yǔ)法樹(shù)。例如，完全加括號(hào)的矩陣連乘積,(A,1,(A,2,A,3,)(A,4,(A,5,A,6,)

16、,所相應(yīng)的語(yǔ)法樹(shù)如圖,(a),所示。,凸多邊形,v,0,v,1,v,n,-1,的三角剖分也可以用語(yǔ)法樹(shù)表示。例如，圖,(b),中凸多邊形的三角剖分可用圖,(a),所示的語(yǔ)法樹(shù)表示。,矩陣連乘積中的每個(gè)矩陣,A,i,對(duì)應(yīng)于凸,(n+1),邊形中的一條邊,v,i-1,v,i,。三角剖分中的一條弦,v,i,v,j,，,ij,，對(duì)應(yīng)于矩陣連乘積,Ai+1:j,。,24,最優(yōu)子結(jié)構(gòu)性質(zhì),凸多邊形的最優(yōu)三角剖分問(wèn)題有最優(yōu)子結(jié)構(gòu)性質(zhì)。,事實(shí)上，若凸,(n+1),邊形,P=v,0,v,1,v,n,-1,的最優(yōu)三角剖分,T,包含三角形,v,0,v,k,v,n,，,1kn-1,，則,T,的權(quán)為,3,個(gè)部分權(quán)的和：三角形,v0vkvn,的權(quán)，子多邊形,v,0,v,1,v,k,和,v,k,v,k,+1,v,n,的權(quán)之和。可以斷言，由,T,所確定的這,2,個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲?v,0,v,1,v,k,或,v,k,v,k,+1,v,n,的更小權(quán)的三角剖分將導(dǎo)致,T,不是最優(yōu)三角剖分的矛盾。,25,最優(yōu)三角剖分的遞歸結(jié)構(gòu),定義,tij,，,1ijn,為凸子多邊形,vi-1,vi,vj,的最優(yōu)三角