算法分析與設(shè)計(jì)（三）

-動(dòng)態(tài)規(guī)劃教學(xué)課件主講人：王春平Email:wangcp@

浙江工業(yè)大學(xué)計(jì)算機(jī)學(xué)院2矩陣連乘問題動(dòng)態(tài)規(guī)劃的基本要素最長(zhǎng)公共子序列凸多邊形最優(yōu)三角剖分0-1背包問題主要內(nèi)容3矩陣連乘問題(1)矩陣A和B的可乘條件：A的列數(shù)等于B的行數(shù)。

令A(yù)是p*q的矩陣，B是q*r的矩陣，則乘積C=AB是一個(gè)p*r的矩陣，其計(jì)算需q*r*p次乘法。

矩陣乘法的結(jié)合律(AssociativeLaw)：令矩陣A1和A2可乘，矩陣A2和A3可乘，則有：A1A2A3=(A1A2)A3=A1(A2A3)4矩陣連乘問題(2)

矩陣連乘(Matrix-ChainMultiplication)：給定n個(gè)矩陣{A1,A2,A3,…,An}，其中Ai與Ai+1是可乘的，計(jì)算這n個(gè)矩陣的連乘積A1A2A3

…An。

從矩陣乘法的結(jié)合律可看出，n個(gè)矩陣的連乘積可有多種計(jì)算次序。完全加括號(hào)的n個(gè)矩陣連乘積的定義(用于確定矩陣連乘的計(jì)算次序)：1）單個(gè)矩陣是完全加括號(hào)的；2）矩陣連乘積A是完全加括號(hào)的，則A可表示為2個(gè)完全加括號(hào)的矩陣連乘積B和C的乘積并加括號(hào)，即A=(BC)。5矩陣連乘問題(3)矩陣連乘計(jì)算示例：

設(shè)A1,A2,A3分別為10*100，100*5和5*50的矩陣，則有：1）A1

A2

A3=(A1

A2)A3需10*100*5+10*5*50=7500次乘法。2）A1

A2

A3=A1(A2

A3)需100*5*50+10*100*50=75000次乘法。結(jié)論：矩陣連乘積的計(jì)算次序?qū)ζ溆?jì)算量的影響非常大！6矩陣連乘問題(4)

矩陣連乘問題：確定矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。

效率低下的窮舉法(MethodofExhaustion)：1）對(duì)于n個(gè)矩陣的連乘積，設(shè)其有不同的計(jì)算次序P(n)

。2）對(duì)于矩陣序列的每種加括號(hào)方式(即確定計(jì)算次序)都可分解為兩個(gè)子矩陣序列的加括號(hào)問題：(A1...Ak)(Ak+1…An)，則P(n)的遞推式如下：其中：C(n)為組合學(xué)中的CatalanNumbers(卡塔蘭數(shù))，

該數(shù)以比利時(shí)數(shù)學(xué)家EugèneCharlesCatalan(1814.05-1894.02)命名。7矩陣連乘問題(5)動(dòng)態(tài)規(guī)劃法(DynamicProgramming)：將矩陣連乘積A1A2…An簡(jiǎn)記為A[1:n]

，其中1≤n。

1)

分析最優(yōu)解的結(jié)構(gòu)：考察計(jì)算A[1:n]的最優(yōu)計(jì)算次序。將矩陣序列A[1:n]分解為A[1:k]和A[k+1:n]。2)

建立遞歸關(guān)系：找出矩陣序列和子矩陣序列的最小乘法次數(shù)之間的關(guān)系。3)計(jì)算最優(yōu)值：比較并找出矩陣連乘的最小乘法次數(shù)。4)構(gòu)造最優(yōu)解：使用回溯法(Traceback)找出最優(yōu)加括號(hào)次序。8矩陣連乘問題(6)動(dòng)態(tài)規(guī)劃法(一)：分解最優(yōu)解的結(jié)構(gòu)1)考察計(jì)算A[1:n]的最優(yōu)計(jì)算次序。設(shè)該最優(yōu)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，1≤k<n，則其相應(yīng)的完全加括號(hào)方式為：

((A1A2…Ak)(Ak+1Ak+2…An))。2)顯然，子矩陣序列

(A1A2…Ak)和

(Ak+1Ak+2…An)的計(jì)算次序也須是最優(yōu)的(可用反證法證明)。3)矩陣連乘計(jì)算次序問題的最優(yōu)解實(shí)際上包含著其子問題的最優(yōu)解，這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)(OptimalSubstructure)。9矩陣連乘問題(7)動(dòng)態(tài)規(guī)劃法(二)：建立遞歸關(guān)系1)令計(jì)算A[i:j](其中1≤i≤j≤n)所需的最少乘法次數(shù)為m[i,j]，則A[1:n]計(jì)算次序問題的最優(yōu)值為m[1,n]。2)當(dāng)i=j時(shí)，A[i:j]=A[i:i]=Ai，因此，m[i,i]=0，i=1,2,…,n

3)當(dāng)i<j時(shí)，設(shè)矩陣序列A[i:j]的最優(yōu)次序在Ak和Ak+1處斷開，則m[i,j]=m[i,k]+

m[k+1,j]+pjpi-1pk(其中Ai的維數(shù)為pi-1*pi)。顯然k的取值區(qū)間為[i,j)，共j-i種可能，因此進(jìn)一步地有：10矩陣連乘問題(8)動(dòng)態(tài)規(guī)劃法(三)：計(jì)算最優(yōu)值1)令計(jì)算A[i:j](其中1≤i≤j≤n)所需最少數(shù)乘法次數(shù)為m[i,j]

。2)根據(jù)m[i,j]的遞歸式可編寫自頂向下的遞歸算法來計(jì)算m[1,n]，這種方法將會(huì)耗費(fèi)指數(shù)級(jí)的計(jì)算時(shí)間(與窮舉法相同)。3)實(shí)際上，有序?qū)?i,j)的選擇共有種，相應(yīng)的子問題也最多有個(gè)，因此可采用自底向上的遞歸或非遞歸方法(每個(gè)子問題只計(jì)算一次)來消去自頂向下的遞歸算法中對(duì)于相同子問題的重復(fù)計(jì)算。11矩陣連乘問題(9)動(dòng)態(tài)規(guī)劃法(三)：計(jì)算最優(yōu)值(實(shí)現(xiàn))voidMatrixChain(int*p，intn，int**m，int**s){for(inti=1;i<=n;i++)m[i][i]=0;//矩陣鏈長(zhǎng)度為1for(intr=2;r<=n;r++){//矩陣鏈長(zhǎng)度為r，逐步增加for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;

//設(shè)k=i為斷裂處，然后逐步加大k找到最佳

for(intk=i+1;k<j;k++){//計(jì)算長(zhǎng)度為r的最優(yōu)值intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}}說明：1)s[i][j]為最優(yōu)次序的斷開位置；2)算法時(shí)間復(fù)雜度取決于三重循環(huán)，為：O(n3)；3)算法空間復(fù)雜度為：O(n2)12矩陣連乘問題(10)動(dòng)態(tài)規(guī)劃法(三)：計(jì)算最優(yōu)值(示例)A1A2A3A4A5A6303535

1515

55

1010

2020

25令：則：k為[2,5)13矩陣連乘問題(11)動(dòng)態(tài)規(guī)劃法(四)：構(gòu)造最優(yōu)解，根據(jù)s[i,j]可回溯追蹤出各個(gè)斷開處(即加括號(hào)處)，代碼如下：voidTraceback(inti,intj,int**s){if(i==j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<“MultiplyA”<<i<<“,”<<s[i][j];cout<<“andA”<<(s[i][j]+1)<<“,”<<j<<endl;}14矩陣連乘問題動(dòng)態(tài)規(guī)劃的基本要素最長(zhǎng)公共子序列凸多邊形最優(yōu)三角剖分0-1背包問題主要內(nèi)容15動(dòng)態(tài)規(guī)劃的基本要素(1)動(dòng)態(tài)規(guī)劃(DynamicProgramming)法的步驟如下：1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征；2）遞歸地定義最優(yōu)值；3）以自底向上的方式計(jì)算出最優(yōu)值；4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。

動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素：最優(yōu)子結(jié)構(gòu)和子問題重疊。16動(dòng)態(tài)規(guī)劃的基本要素(2)最優(yōu)子結(jié)構(gòu)性質(zhì)(OptimalSubstructure)：當(dāng)問題的最優(yōu)解包含著其子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。

分析問題最優(yōu)子結(jié)構(gòu)的反證法：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)，然后再證明在此假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。17動(dòng)態(tài)規(guī)劃的基本要素(3)子問題重疊(OverlappingSubproblems)：遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次，該性質(zhì)稱為子問題的重疊性質(zhì)。通常地，不同的子問題個(gè)數(shù)隨問題的大小呈現(xiàn)多項(xiàng)式增長(zhǎng)；而常規(guī)自頂向下的遞歸算法復(fù)雜度呈現(xiàn)指數(shù)級(jí)增長(zhǎng)。動(dòng)態(tài)規(guī)劃算法中對(duì)每一個(gè)子問題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。18動(dòng)態(tài)規(guī)劃的基本要素(4)矩陣連乘的最優(yōu)次序問題的自頂向下的直接遞歸算法。

int

RecurMatrixChain(inti,intj){

if(i==j)return

0;

intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];

s[i][j]=i;for(intk=i+1;k<j;k++){

intt=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];

if(t<u){

u=t;

s[i][j]=k;

}

}

returnu;

}19動(dòng)態(tài)規(guī)劃的基本要素(5)

RecurMatrixChain的A[1:4]遞歸分解示例：20動(dòng)態(tài)規(guī)劃的基本要素(6)

RecurMatrixChain的算法復(fù)雜度分析，令條件語句和賦值語句執(zhí)行時(shí)間為常數(shù)，則由：當(dāng)n>1時(shí)，有：因此，T(n)=。21動(dòng)態(tài)規(guī)劃的基本要素(7)備忘錄方法：其控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，要點(diǎn)如下：1)備忘錄方法為每個(gè)求解過的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。2)備忘錄方法也采用了自頂向下的遞歸方法，主程序如下。

intMemorizedMatrixChain(intn,int**m,int**s){

for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)m[i][j]=0;

returnLookupChain(1,n);

}22動(dòng)態(tài)規(guī)劃的基本要素(8)備忘錄方法的LookupChain函數(shù)intLookupChain(inti，intj){if(m[i][j]>0)returnm[i][j];if(i==j)return0;intu=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;returnu;}說明：1)數(shù)組m用于保存子問題的最優(yōu)值；2)算法時(shí)間復(fù)雜度也為：O(n3)；3)算法空間復(fù)雜度為：O(n2)23矩陣連乘問題動(dòng)態(tài)規(guī)劃的基本要素最長(zhǎng)公共子序列凸多邊形最優(yōu)三角剖分0-1背包問題主要內(nèi)容24最長(zhǎng)公共子序列(1)

子序列(Subsequence)令序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}為X的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列{i1,i2,…,ik}使得對(duì)于全部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}。

公共子序列(CommonSubsequence)：對(duì)于給定的兩個(gè)X和Y序列，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。25最長(zhǎng)公共子序列(2)

最長(zhǎng)公共子序列問題(LongestCommonSubsequence)：對(duì)于給定的序列X={x1,x2,…,xm}和序列Y={y1,y2,…,yk}，求它們最長(zhǎng)的公共子序列。

窮舉法：對(duì)于X的所有子序列，檢查它是否也是Y的子序列，在檢查過程中記錄最長(zhǎng)的公共子序列。當(dāng)X的所有子序列都檢查過后，結(jié)果即為X和Y的最長(zhǎng)公共子序列。

由于序列X共有2m個(gè)子序列(根據(jù)二項(xiàng)式定理)，因此窮舉法的時(shí)間復(fù)雜度為指數(shù)級(jí)。26最長(zhǎng)公共子序列(3)

采用動(dòng)態(tài)規(guī)劃法求解最長(zhǎng)公共子序列問題：最優(yōu)子結(jié)構(gòu)性質(zhì)的證明。

設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk}，則有：1)若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列。2)若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長(zhǎng)公共子序列。3)若xm≠yn且zk≠yn，則Z是X和Yn-1的最長(zhǎng)公共子序列。

從上述3點(diǎn)可推出(反證法)，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此最長(zhǎng)公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。27最長(zhǎng)公共子序列(4)

采用動(dòng)態(tài)規(guī)劃法求解最長(zhǎng)公共子序列問題：子問題的遞歸結(jié)構(gòu)及子問題重疊性質(zhì)。

要找出序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk}，可按如下方式遞歸進(jìn)行：1)若xm=yn，則查找Xm-1和Yn-1的最長(zhǎng)公共子序列，將其結(jié)果與xm合并即為X和Y的最長(zhǎng)公共子序列。2)若xm≠yn，則分別查找Xm-1和Y，X和Yn-1的最長(zhǎng)公共子序列，二者中的較長(zhǎng)者即為X和Y的最長(zhǎng)公共子序列。

從上述2點(diǎn)可看出，求解Xm-1和Yn-1，Xm-1和Y，X和Yn-1的最長(zhǎng)公共子序列時(shí)都包含了一個(gè)公共的子問題，即：求解Xm-1和Yn-1的最長(zhǎng)公共子序列。

28最長(zhǎng)公共子序列(5)

采用動(dòng)態(tài)規(guī)劃法求解最長(zhǎng)公共子序列問題：建立子問題最優(yōu)值的遞歸關(guān)系。令c[i][j]為序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度，其中Xi={x1,x2,…,xi}，Yj={y1,y2,…,yj}，則有：1)當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)c[i][j]=0。2)當(dāng)i≠0且j≠0時(shí)，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系。29最長(zhǎng)公共子序列(6)

采用動(dòng)態(tài)規(guī)劃法求解最長(zhǎng)公共子序列問題：求解最優(yōu)值。

1)采用直接遞歸算法的復(fù)雜度為指數(shù)級(jí)；2)在所考慮的子問題空間中共有θ(mn)個(gè)不同的子問題，因此可采用自底向上的非遞歸算法可提高效率，具體如下：voidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;//處理j=0的情況for(i=1;i<=n;i++)c[0][i]=0;//處理i=0的情況for(i=1;i<=m;i++)//處理i,j均不等于0的情況for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}

elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}

else{c[i][j]=c[i][j-1];b[i][j]=3;}}}說明：1)數(shù)組c用于保存X和Y的最長(zhǎng)子序列長(zhǎng)度；2)數(shù)組b[i][j]用于保存c[i][j]是由哪個(gè)子問題求解得到的；3)算法時(shí)間復(fù)雜度為：O(mn)30最長(zhǎng)公共子序列(7)

采用動(dòng)態(tài)規(guī)劃法求解最長(zhǎng)公共子序列問題：構(gòu)造最長(zhǎng)公共子序列(根據(jù)LCSLength的數(shù)組b可快速構(gòu)造X和Y的最長(zhǎng)公共子序列)，算法如下：voidLCS(inti，intj，char*x，int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1，j-1，x，b);cout<<x[i];}elseif(b[i][j]==2)LCS(i-1，j，x，b);elseLCS(i，j-1，x，b);}說明：1)當(dāng)b[i][j]=1時(shí)，表示Xi和Yj的最長(zhǎng)公共子序列為Xi-1和Yj-1的最長(zhǎng)公共子序列加上xi組成；2)當(dāng)b[i][j]=2時(shí)，表示Xi和Yj的最長(zhǎng)公共子序列與Xi-1和Yj的最長(zhǎng)公共子序列相同；3)當(dāng)b[i][j]=3時(shí)，表示Xi和Yj的最長(zhǎng)公共子序列與Xi-和Yj-1的最長(zhǎng)公共子序列相同；4)LCS算法的時(shí)間復(fù)雜度為：O(m+n)。31最長(zhǎng)公共子序列(8)

采用動(dòng)態(tài)規(guī)劃法求解最長(zhǎng)公共子序列問題的空間復(fù)雜度改進(jìn)：1)在算法LCSLength和LCS中，數(shù)組元素c[i][j]的值僅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素c[i][j]，可不借助于數(shù)組b而僅借助于c本身來確定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一個(gè)值所確定的。因此數(shù)組b的空間需求可省略。2)如只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上在計(jì)算c[i][j]時(shí)，只用到數(shù)組c的第i行和第i-1行。因此只用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度，進(jìn)一步分析還可將空間需求減至O(min{m,n})。32矩陣連乘問題動(dòng)態(tài)規(guī)劃的基本要素最長(zhǎng)公共子序列凸多邊形最優(yōu)三角剖分0-1背包問題主要內(nèi)容33凸多邊形最優(yōu)三角剖分(1)

多邊形(Polygon)：它是由平面(Plane)上一系列直線段首尾相連而成。各直線段稱為邊(Side)。連接直線的點(diǎn)稱為頂點(diǎn)(Vertex)。

簡(jiǎn)單多邊形(SimplePolygon)：該多邊形的邊除了頂點(diǎn)之外沒有交點(diǎn)。

凸多邊形(ConvexPolygon)：它是一個(gè)簡(jiǎn)單多邊形，且該多邊形內(nèi)部或邊界上任意兩點(diǎn)的連線上所有點(diǎn)都在其內(nèi)部。34凸多邊形最優(yōu)三角剖分(2)

多邊形的表示：用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P={v0,v1,…,vn-1}表示具有n條邊(v0v1,

v1v2,…,vn-1vn，其中vn=v0)的凸多邊形。

弦(Chord)的定義：若vi與vj是多邊形上不相鄰的2個(gè)頂點(diǎn)，則直線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個(gè)多邊形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。

多邊形的三角剖分(Triangulation)問題：指將多邊形P分割成互不相交的三角形。對(duì)于用于分割的弦的集合T，多邊形P內(nèi)任意一條不在集合T內(nèi)的弦必與集合T內(nèi)的某條弦相交。

定理：集合T中共有n-3條弦并多邊形P剖分成n-2個(gè)三角形。v6v1v4v5v3v2v0v6v1v4v5v3v2v035凸多邊形最優(yōu)三角剖分(3)多邊形的最優(yōu)三角剖分問題：

對(duì)于給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得該三角剖分中諸三角形上的權(quán)之和為最小。

定義在三角形上的權(quán)函數(shù)(Weight)示例：1)權(quán)函數(shù)定義：w(vi,vj,vk)=|vivj|+|vjvk|+|vkvi|，其中|vivj|表示頂點(diǎn)vi和頂點(diǎn)vj之間的歐氏距離(EuclideanDistance)；2)定義在上述權(quán)函數(shù)w上的最優(yōu)三角剖分是最小弦長(zhǎng)三角剖分。Euclid(歐幾里得)(幾何之父，約325B.C.-265B.C.)36凸多邊形最優(yōu)三角剖分(4)

三角剖分的結(jié)構(gòu)及其相關(guān)問題：1)一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹，稱為表達(dá)式的語法樹。如：完全加括號(hào)的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應(yīng)的語法樹如圖(a)所示。2)凸多邊形{v0,v1,…vn-1}的三角剖分也可以用語法樹表示。如：圖(b)中凸多邊形的三角剖分可用圖(a)所示的語法樹表示。3)凸n邊形的三角剖分與有n-1個(gè)葉結(jié)點(diǎn)的語法樹有一一對(duì)應(yīng)關(guān)系。

說明：矩陣連乘積中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，i<j，對(duì)應(yīng)于矩陣連乘積A[i+1:j]。37凸多邊形最優(yōu)三角剖分(5)凸多邊形的最優(yōu)三角剖分問題：最優(yōu)子結(jié)構(gòu)性質(zhì)的證明(反證法)。

1)若凸(n+1)邊形P={v0,v1,…,vn}的最優(yōu)三角剖分T包含三角形v0vkvn，1≤k≤n-1，則T的權(quán)為3個(gè)部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形{v0,v1,…,vk}和{vk,vk+1,…,vn}的權(quán)之和。2)根據(jù)上述假設(shè)可得，由T所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衶v0,v1,…,vk}或{vk,vk+1,…,vn}的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。v6v1v4v5v3v2v0k=338凸多邊形最優(yōu)三角剖分(6)凸多邊形的最優(yōu)三角剖分問題：子問題重疊。

1)若凸(n+1)邊形P={v0,v1,…,vn}的最優(yōu)三角剖分T包含三角形v0vkvn，1≤k≤n-1，則T的權(quán)為3個(gè)部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形{v0,v1,…,vk}和{vk,vk+1,…,vn}的權(quán)之和。2)因此，當(dāng)k取不同的位置時(shí)，很多子問題計(jì)算是重復(fù)的。v6v1v4v5v3v2v0k=4v6v1v4v5v3v2v0k=3陰影部分為子問題重疊示例39凸多邊形最優(yōu)三角剖分(7)凸多邊形的最優(yōu)三角剖分問題：計(jì)算最優(yōu)值。

1)令t[i][j]為凸子多邊形{vi-1,vi,…,vj}的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值(1≤i<j≤n)，即其最優(yōu)值。因此，要計(jì)算的凸(n+1)邊形P的最優(yōu)權(quán)值即可表示為：t[1][n]。2)設(shè)退化的多邊形{vi-1,vi}具有權(quán)值0(此時(shí)無法做三角形剖分)，即：t[i][i]=0。3)根據(jù)上述兩點(diǎn)和最優(yōu)子結(jié)構(gòu)性質(zhì)可得t[i][j]的遞歸計(jì)算公式如下：說明：

當(dāng)j-i≥1時(shí)，凸子多邊形至少有3個(gè)頂點(diǎn)(i-1,i,j)。由最優(yōu)子結(jié)構(gòu)性質(zhì)，t[i][j]的值應(yīng)為t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的權(quán)值，其中i≤k≤j-1。

由于k的所有可能位置有j-i個(gè)，故還需要在這j-i個(gè)位置中選出使t[i][j]值達(dá)到最小的位置。40凸多邊形最優(yōu)三角剖分(8)凸多邊形的最優(yōu)三角剖分問題：解最優(yōu)值實(shí)現(xiàn)。

publicvoidminWeightTriangulation(intn,int**t,int**s){

for(inti=1;i<=n;i++)t[i][i]=0;//2個(gè)頂點(diǎn)的多邊形

for(intr=2;r<=n;r++){//逐步增加頂點(diǎn)數(shù)

for(inti=1;i<=n-r+1;i++){

intj=i+r-1;t[i][j]=t[i+1][j]+weight(i-1,i,j);//從k=i開始，省略了t[i][i]

s[i][j]=i;

for(intk=i+1;k<j;k++){//逐步移動(dòng)頂點(diǎn)k的位置

intu=t[i][k]+t[k+1][j]+weight(i-1,k,j);

if(u<t[i][j]){

t[i][j]=u;

s[i][j]=k;}

}

}

}

}說明：1)數(shù)組t用于保存子問題的最優(yōu)值；2)數(shù)組s[i][j]保存了與vi-1和vi一起構(gòu)成三角形的第3個(gè)頂點(diǎn)；3)算法時(shí)間復(fù)雜度也為：O(n3)；4)算法空間復(fù)雜度為：O(n2)41矩陣連乘問題動(dòng)態(tài)規(guī)劃的基本要素最長(zhǎng)公共子序列凸多邊形最優(yōu)三角剖分0-1背包問題主要內(nèi)容420-1背包問題(1)

0-1背包問題(0-1KnapsackProblem)：給定n種物品和一背包。物品i的重量是wi，價(jià)值為vi，背包的容量為c。如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?

形式化描述如下：給定c>0,wi>0,vi>0,1≤i≤n，請(qǐng)找出n元0-1向量(x1,x2,…,xn),，1≤i≤n，使得：規(guī)劃目標(biāo)：約束條件：說明：xi=0表示物品i不裝入，xi=1表示物品i裝入430-1背包問題(2)

0-1背包問題：最優(yōu)子結(jié)構(gòu)性質(zhì)的證明(反證法)。若{y1,y2,…,yn}為0-1背包問題的一個(gè)最優(yōu)解，則

{y2,…,yn}是其子問題的最優(yōu)解，子問題如下：規(guī)劃目標(biāo)：約束條件：反正法：假設(shè){y2,…,yn}不是上述子問題的最優(yōu)解，則可令{z2,…,zn}是上述子問題的最優(yōu)解，即：且。故進(jìn)一步有：即：因此：{y1,z2,…,zn}是比{y1,y2,…,yn}更優(yōu)的解，這與前提相矛盾。440-1背包問題(3)

0-1背包問題：子問題遞歸關(guān)系的建立。令：m(i,j)為子問題的最優(yōu)值，子問題如下：規(guī)劃目標(biāo)：約束條件：即：m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。由最優(yōu)子結(jié)構(gòu)性質(zhì)可得：特別地：不裝入物品i裝入物品i裝不下物品i450-1背包問題(4)

0-1背包問題：最優(yōu)值m(1,c)的實(shí)現(xiàn)。voidknapsack(intv[],int*w,intc,intn,int**m){

intjmax=min(w[n]-1,c);//1)僅可選物品n時(shí)，容量為j的子問題的最優(yōu)值

for(intj=0;j<=jmax;j++)m[n][j]=0;//注意j為整數(shù)for(intj=w[n];j<=c;j++)m[n][j]=v[n];

for(inti=n-1;i>1;i--){//2)逐步增加物品數(shù)至n及容量至c

jmax=min(w[i]-1,c);//僅可選物品i時(shí)，容量為j的子問題的最優(yōu)值

for(intj=0;j<=jmax;j++)m[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];//處理物品1，最后一件的邊界情況if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}說明：1)數(shù)組m用于保存子問題的最優(yōu)值；2)根據(jù)m[i][c]和m[i+1][c]的大小關(guān)系可判斷物品i是否裝入；3)算法時(shí)間復(fù)雜度也為：O(nc)，空間復(fù)雜度為：O(n2)460-1背包問題(5)

0-1背包問題：Knapsack求解最優(yōu)值示例。設(shè)：n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}jmax=min(w[5]-1,10)jmax=w[5]-1=3for(intj=0;j<=3;j++)m[5][j]=0;m[5][0]~m[5][3]=0for(intj=w[5];j<=10;j++)m[5][j]=v[5];m[5][4]~m[5][10]=6m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。i=n=51)470-1背包問題(6)n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。00006666666i=5i=4i=3i=2i=1j=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10

m(5,j)求值示意圖480-1背包問題(7)n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}for(intj=w[4];j<=10;j++)m[4][j]=max(m[4+1][j],m[4+1][j-w[4]]+v[4]);m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。m[4][5]=max(m[4+1][5],m[4+1][5-5]+v[4])=max(6,0+4)=6j=5m[4][6]=max(m[4+1][6],m[4+1][6-5]+v[4])=max(6,0+4)=6j=6m[4][7]=max(m[4+1][7],m[4+1][7-5]+v[4])=max(6,0+4)=6j=7m[4][8]=max(m[4+1][8],m[4+1][8-5]+v[4])=max(6,0+4)=6j=8m[4][9]=max(m[4+1][9],m[4+1][9-5]+v[4])=max(6,6+4)=10j=9m[4][10]=max(m[4+1][10],m[4+1][10-5]+v[4])=max(6,6+4)=10j=10i=n-1=42)jmax=min(w[4]-1,10)jmax=w[4]-1=4for(intj=0;j<=jmax;j++)m[4][j]=m[4+1][j];m[4][0]~m[4][3]=0m[4][4]=m[5][4]=6490-1背包問題(8)000066666660000666661010i=5i=4i=3i=2i=1j=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10

m(4,j)求值示意圖n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。500-1背包問題(9)n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}for(intj=w[3];j<=10;j++)m[3][j]=max(m[3+1][j],m[3+1][j-w[3]]+v[3]);m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。m[3][6]=max(m[3+1][6],m[3+1][6-6]+v[3])=max(6,0+5)=6j=6m[3][7]=max(m[3+1][7],m[3+1][7-6]+v[3])=max(6,0+5)=6j=7m[3][8]=max(m[3+1][8],m[3+1][8-6]+v[3])=max(6,0+5)=6j=8m[3][9]=max(m[3+1][9],m[3+1][9-6]+v[3])=max(10,0+5)=10j=9m[3][10]=max(m[3+1][10],m[3+1][10-6]+v[3])=max(10,6+5)=11j=10i=n-1-1=33)jmax=min(w[3]-1,10)jmax=w[3]-1=5for(intj=0;j<=jmax;j++)m[3][j]=m[3+1][j];m[3][0]~m[3][3]=0m[3][4]~m[3][5]=6510-1背包問題(10)0000666666600006666610100000666661011i=5i=4i=3i=2i=1j=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10

m(3,j)求值示意圖n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,

6}m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。520-1背包問題(11)n=5,c=10,w={2,2,6,5,4},v={6,3,

5,4,6}for(intj=w[2];j<=10;j++)m[2][j]=max(m[2+1][j],m[2+1][j-w[2]]+v[2]);m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。m[2][2]=max(m[2+1][2],m[2+1][2-2]+v[2])=max(0,0+3)=3j=2i=n-1-1-1=24)jmax=min(w[2]-1,10)jmax=w[2]-1=1for(intj=0;j<=jmax;j++)m[2][j]=m[2+1][j];m[2][0]~m[2][1]=0m[2][3]=max(m[2+1][3],m[2+1][3-2]+v[2])=max(0,0+3)=3j=3m[2][4]=max(m[2+1][4],m[2+1][4-2]+v[2])=max(6,0+3)=6j=4m[2][5]=max(m[2+1][5],m[2+1][5-2]+v[2])=max(6,0+3)=6j=5m[2][6]=max(m[2+1][6],m[2+1][6-2]+v[2])=max(6,6+3)=9j=6m[2][7]=max(m[2+1][7],m[2+1][7-2]+v[2])=max(6,6+3)=9j=7m[2][8]=max(m[2+1][8],m[2+1][8-2]+v[2])=max(6,6+3)=9j=8m[2][9]=max(m[2+1][9],m[2+1][9-2]+v[2])=max(10,6+3)=10j=9m[2][10]=max(m[2+1][10],m[2+1][10-2]+v[2])=max(11,6+3)=11j=10530-1背包問題(12)00006666666000066666101000006666610110033669991011i=5i=4i=3i=2i=1j=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10

m(2,j)求值示意圖n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。540-1背包問題(13)n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}for(intj=w[1];j<=10;j++)m[1][j]=max(m[1+1][j],m[1+1][j-w[1]]+v[1]);m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。m[1][2]=max(m[1+1][2],m[1+1][2-2]+v[1])=max(3,0+6)=6j=2i=n-1-1-1-1=15)jmax=min(w[1]-1,10)jmax=w[2]-1=1for(intj=0;j<=jmax;j++)m[1][j]=m[1+1][j];m[1][0]~m[1][1]=0m[1][3]=max(m[1+1][3],m[1+1][3-2]+v[1])=max(3,0+6)=6j=3m[1][4]=max(m[1+1][4],m[1+1][4-2]+v[1])=max(6,3+6)=9j=4m[1][5]=max(m[1+1][5],m[1+1][5-2]+v[1])=max(6,3+6)=9j=5m[1][6]=max(m[1+1][6],m[1+1][6-2]+v[1])=max(9,6+6)=12j=6m[1][7]=max(m[1+1][7],m[1+1][7-2]+v[1])=max(9,6+6)=12j=7m[1][8]=max(m[1+1][8],m[1+1][8-2]+v[1])=max(9,9+6)=15j=8m[1][9]=max(m[1+1][9],m[1+1][9-2]+v[1])=max(11,9+6)=15j=9m[1][10]=max(m[1+1][10],m[1+1][10-2]+v[1])=max(11,9+6)=15j=10550-1背包問題(14)000066666660000666661010000066666101100336699910110066991212151515i=5i=4i=3i=2i=1j=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10

m(1,j)求值示意圖n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。560-1背包問題(15)

0-1背包問題：構(gòu)造最優(yōu)解。inttraceback(int**m,int*w,intc,intn,int*x){for(inti=1;i<n;i++){if(m[i][c]==m[i+1][c])x[i]=0;//二者相等說明物品i不裝入else{x[i]=1;c=c-w[i];}x[n]=(m[n][c])?1:0;}}說明：1)x[i]為0表示物品i不裝入，為1表示裝入；2)算法時(shí)間復(fù)雜度也為：O(n)570-1背包問題(16)000066666660000666661010000066666101100336699910110066991212151515n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}m(i,j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。

0-1背包問題：構(gòu)造最優(yōu)解示例。i=5i=4i=3i=2i=1j=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10

m(1,j)示意圖

m(1,10)!=m(2,10)

x[1]=1

m(2,8)!=m(3,8)

x[2]=1

m(3,6)=m(4,6)

x[3]=0

m(4,6)=m(5,6)

x[4]=0

m(5,6)=6

x[5]=1580-1背包問題(17)

Knapsack算法的時(shí)間復(fù)雜度為O(nc)，當(dāng)c>2n時(shí)，算法的復(fù)雜度為O(n2n)。此外Knapsack算法在處理的過程中還要求容量j必須是整數(shù)。當(dāng)容量和重量為實(shí)數(shù)怎么辦？

算法改進(jìn)的基礎(chǔ)：函數(shù)m(i,j)隨著j的單調(diào)不減跳躍特征?？疾烊缦率纠簄=5,c=10,

w={2,2,6,5,4},v={6,3,5,4,6}則當(dāng)i=5時(shí)，有：m(5,j)j204682468104,m(5,4)590-1背包問題(18)根據(jù)函數(shù)m(i,j)隨著j的單調(diào)不減跳躍特征，則有：1)因此容量j不僅可為整數(shù)，也可以為實(shí)數(shù)。2)對(duì)于j為實(shí)數(shù)時(shí)，m(i,j)的值可通過記錄跳躍點(diǎn)，然后查表來確定。

令p[i]表示m(i,j)的全部跳躍點(diǎn)，顯然p[i]是一個(gè)遞增升序排列。令：q[i+1]表示m(i+1,j-wi)+vi的全部跳躍點(diǎn)，又p[i+1]為m(i+1,j)的全部跳躍點(diǎn)，則有：

p[i]

p[i+1]

q[i+1]。600-1背包問題(19)

p[i]與p[i+1]的遞歸關(guān)系：m(i,j)的跳躍點(diǎn)是m(i+1,j)和m(i+1,j-wi)+vi的跳躍點(diǎn)的并集的子集。

p[i]的求解示例(n=5,c=10,

w={2,2,6,5,4},v={6,3,5,4,6})。1)i=6,根據(jù)p[i]的定義有：p[6]={0,0}。610-1背包問題(20)要點(diǎn)：

p[i]為

m(i,j)的跳躍點(diǎn)，q[i+1]為m(i+1,j-wi)+vi的跳躍點(diǎn)，p[i+1]為m(i+1,j)的跳躍點(diǎn)，且：

p[i]

p[i+1]

q[i+1]。

p[i]的求解示例(n=5,c=10,

w={2,2,6,5,4},v={6,3,5,4,6})：2)i<6,根據(jù)查表得：1)i=6,根據(jù)p[i]的定義有：p[6]={0,0}。000066666660000666661010000066666101100336699910110066991212151515i=5i=4i=3i=2i=1j=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10p[5]={(0,0),(4,6)}p[4]={(0,0),(4,6),(9,10)}p[3]={(0,0),(4,6),(9,10),(10,11)}p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)}p[1]={(0,0),(2,6),(4,9),(6,12),(8,15)}620-1背包問題(21)

p[i]與p[i+1]的遞歸關(guān)系：m(i,j)的跳躍點(diǎn)是m(i+1,j)和m(i+1,j-wi)+vi的跳躍點(diǎn)的并集的子集，即：p[i]

p[i+1]

q[i+1]。推論：對(duì)于跳躍點(diǎn)

，則當(dāng)且僅當(dāng)wi≤s≤c且。因此q[i+1]可進(jìn)一步地表示如下：for(intj=w[3];j<=10;j++)m[3][j]=max(m[3+1][j],m[3+1][j-w[3]]+v[3]);m[3][6]=max(m[3+1][6],m[3+1][6-6]+v[3])=max(6,0+5)=6j=6m[3][7]=max(m[3+1][7],m[3+1][7-6]+v[3])=max(6,0+5)=6j=7m[3][8]=max(m[3+1][8],m[3+1][8-6]+v[3])=max(6,0+5)=6j=8m[3][9]=max(m[3+1][9],m[3+1][9-6]+v[3])=max(10,0+5)=10j=9i=n-1-1=3示例：jmax=min(w[3]-1,10)jmax=w[3]-1=5for(intj=0;j<=jmax;j++)m[3][j]=m[3+1][j];m[3][0]~m[3][3]=0，m[3][4]~m[3][5]=6說明：1)(s,t)=(10,11)2)(10-6,11-5)為p[4]的一個(gè)跳躍點(diǎn)。m[3][10]=max(m[3+1][10],m[3+1][10-6]+v[3])=max(10,6+5)=11j=10630-1背包問題(22)

p[i+1]與q[i+1]的受控關(guān)系：

設(shè)(a,b)和(c,d)是p[i+1]

q[i+1]中的2個(gè)跳躍點(diǎn)，則當(dāng)c

a且d<b時(shí)，(c,d)受控于(a,b)，從而(c,d)不是p[i]中的跳躍點(diǎn)。除受控跳躍點(diǎn)外，p[i+1]

q[i+1]中的其它跳躍點(diǎn)均為p[i]中的跳躍點(diǎn)。受控跳躍點(diǎn)可簡(jiǎn)易標(biāo)識(shí)為：“容量大，值卻小，快刪走”。

因此，在遞歸地由表p[i+1]計(jì)算表p[i]時(shí)，可先由p[i+1]計(jì)算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳躍點(diǎn)得到表p[i]。

p[i+1]與q[i+1]的受控關(guān)系示例：1）由：p[5]={(0,0),(4,6)}，則根據(jù)公式有：q[5]=p[5]

(w4,v4)={(5,4),(9,10)}。2）故：p[4]

p[5]q[5]={(0,0),(4,6),(5,4),(9,10)}，根據(jù)受控規(guī)則有進(jìn)一步有：跳躍點(diǎn)(4,6)和(5,4)存在著5>4且6>4，因此(5,4)不是p[4]的跳躍點(diǎn)。000066666660000666661010000066666101100336699910110066991212151515i=5i=4i=3i=2i=1j=0j=1j=2j=3j=4j=5j=6j=7j=8j=9j=10p[5]={(0,0),(4,6)}p[4]={(0,0),(4,6),(9,10)}p[3]={(0,0),(4,6),(9,10),(10,11)}p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)}p[1]={(0,0),(2,6),(4,9),(6,12),(8,15)}640-1背包問題(23)1)p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6]