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

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

DynamicProgramming

1SoftwareCollege,NEU本章主要內(nèi)容矩陣連乘問題

Matrix-ChainMultiplication

動態(tài)規(guī)劃算法的基本要素

ElementsofDynamicProgramming

流水作業(yè)調(diào)度

SchedulingtoMaximizeProfit0-1背包問題

0-1knapsackproblem

最優(yōu)二叉搜索樹

OptimalBinarySearchTrees2SoftwareCollege,NEU1n=0F(n)=1n=1

F(n-1)+F(n-2)n>1例3－1FibonaccinumbersF(4)F(3)F(2)F(2)F(1)F(1)F(0)動態(tài)規(guī)劃算法F(1)F(0)3SoftwareCollege,NEUComputingthenth

fibonaccinumberusingbottom-upiteration:

f(0)=0f(1)=1f(2)=0+1=1f(3)=1+1=2f(4)=1+2=3f(5)=2+3=5

f(n-2)=f(n-1)=f(n)=f(n-1)+f(n-2)4SoftwareCollege,NEU動態(tài)規(guī)劃算法將待求解的問題分解成若干個子問題，先求解子問題，并存儲子問題的解而避免計算重復(fù)的子問題，再由子問題的解得到原問題的解。算法思想5SoftwareCollege,NEU動態(tài)規(guī)劃與分治的聯(lián)系區(qū)別都是分解成子問題，由子問題的解得到原問題的解。分治中子問題相互獨立，而動態(tài)規(guī)劃中子問題互相有聯(lián)系，且存在重復(fù)計算，即存在重疊子問題。6SoftwareCollege,NEU3.1矩陣連乘問題

Matrix-ChainMultiplication

給定n個矩陣{A1,A2,…,An}，其中Ai

是一個ri-1×ri

矩陣(1≤i≤n)，即Ai×Ai+1是可乘的，求出n個矩陣相乘的最優(yōu)計算次序，使得計算量最小。問題提出設(shè)三個矩陣A1,A2,A3大小分別為10×100，100×5，5×50，考慮(A1(A2

A3)),(A1A2)A3)的結(jié)果與相乘的次數(shù)。7SoftwareCollege,NEU矩陣相乘滿足結(jié)合律，連乘積可以有許多不同的次序。這種次序可以用加括號的方式確定?？疾閮蓚€矩陣相乘的情形：C=AB。如果矩陣A，B分別時p×r和r×q

矩陣，則它們的乘積C將是p×q

矩陣，其(i,j)元素為則共需要pqr次數(shù)乘。3.1矩陣連乘問題A1,A2,A3大小分別為10×100，100×5，5×50，(A1(A2

A3)),((A1A2)A3)的結(jié)果相同，都是10×50的矩陣，計算量分別為75000，7500。8SoftwareCollege,NEU完全加括號的矩陣連乘積單個矩陣是完全加括號的；矩陣連乘積A是完全加括號的，則A可表示為2個完全加括號的矩陣連乘積B和C的乘積并加括號，即A=(BC)?？紤]n=4的情況，此時矩陣運算A*B*C*D可按以下方式（順序）計算(完全加括號方式)：

A*((B*C)*D)，

A*(B*(C*D))，

(A*B)*(C*D)，(A*(B*C))*D3.1矩陣連乘問題9SoftwareCollege,NEU兩個矩陣的乘法

voidMatrixMultiply(int**a,int**b,int**c,int

ra,intca,

int

rb,int

cb){if(ca!=rb)error(“矩陣不可乘”)；

for(inti=0;i<ra;i++)

for(intj=0;j<cb;j++){

intsum=a[i][0]*b[0][j];

for(intk=1;k<ca;k++)sum+=a[i][k]*b[k][j];c[i][j]=sum;}}3.1矩陣連乘問題10SoftwareCollege,NEU窮舉搜索法

對于n個矩陣的連乘積，設(shè)有p(n)個計算次序。我們可以在第k個和第k＋1個矩陣之間將原矩陣劃分為兩個子矩陣序列，然后分別對這兩個矩陣子序列完全加括號，最后對所得的結(jié)果加括號，則其中P(n)=C(n-1)，3.1矩陣連乘問題11SoftwareCollege,NEU1.分析最優(yōu)解的結(jié)構(gòu)設(shè)A[i:j]為矩陣連乘積AiAi+1···Aj計算A[1:n]的最優(yōu)次序，設(shè)該次序在矩陣Ak和Ak＋1之間斷開，1≤k<n,則完全加括號方式為((A1···Ak)(Ak+1···An))總計算量為A[1:k]的加上A[k+1:n]的計算量，再加上A[1:k]和A[k+1:n]相乘的計算量。3.1矩陣連乘問題12SoftwareCollege,NEU最優(yōu)子結(jié)構(gòu)特征計算A[1:n]的一個最優(yōu)次序所包含的計算矩陣子鏈A[1:k]和A[k+1:n]的次序也是最優(yōu)的。矩陣連乘積計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解，也就是最優(yōu)子結(jié)構(gòu)性質(zhì)。3.1矩陣連乘問題考慮A[1:k]和A[k+1:n]相乘所需的計算量，A[i:k]和A[k+1:j]相乘呢?A[1:k]的結(jié)果為r1*rk的矩陣，A[k+1:n]的結(jié)果為rk+1*rn的矩陣，則它們相乘的計算量為p1*pk*pn13SoftwareCollege,NEU2.建立遞歸關(guān)系設(shè)計算A[i:j]所需的最少次數(shù)為m[i][j],原問題的最優(yōu)解為m[1][n]。當(dāng)

i=j時:A[i:j]=Ai,m[i][i]=0,i=1,2,···,n。當(dāng)i<j時:m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpjk∈

{i,i+1,···,j-1}3.1矩陣連乘問題14SoftwareCollege,NEU采用遞歸方法計算int

RecurMatrixChain(inti,int,j,intp[]){if()return0;

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;}參加運算矩陣鏈起始位置矩陣鏈終止位置i==j取第一個斷開位置時計算量記錄當(dāng)前斷開位置循環(huán)取k的可取斷開位置3.1矩陣連乘問題15SoftwareCollege,NEU遞歸樹1······41······12······41······23······41······34······42······23······42······34······41······12······23······34······41······12······31······23······33······34······42······23······32······23······31······12······23.1矩陣連乘問題16SoftwareCollege,NEU可以證明該算法的計算時間T(n)有指數(shù)下界，設(shè)算法中判斷語句和賦值語句花費常數(shù)時間，則由算法的遞歸部分可得關(guān)T(n)的遞歸不等式如下：

因此，當(dāng)n>1時，可用數(shù)學(xué)歸納法證明3.1矩陣連乘問題17SoftwareCollege,NEU對于1≤i≤j≤n，不同的有序?qū)?i,j)對應(yīng)于不同的子問題m[i][j]，因此，不同的子問題的個數(shù)最多只有用動態(tài)規(guī)劃解此問題時，在計算過程中，保存已解決的子問題答案，每個子問題只計算一次，而在后面用到時簡單地查一下，從而避免了大量的重復(fù)計算。3.1矩陣連乘問題18SoftwareCollege,NEU2······42······23······41······23······34······41······11······41······32······33.1矩陣連乘問題3.計算最優(yōu)值19SoftwareCollege,NEU3.計算最優(yōu)值對于m[1][n]可以按照下面順序構(gòu)成m[1][2]m[2][3]m[3][4]m[4][5]……m[n-1][n]m[1][3]m[2][4]m[3][5]……m[n-2][n]m[1][4]m[2][5]m[3][6]……m[n-3][n]m[1][n-1]m[2][n]m[1][n]3.1矩陣連乘問題計算m[i][j]時，只用到已計算出的m[i][k]和m[k+1][j]20SoftwareCollege,NEU3.計算最優(yōu)值置所有只有一個矩陣的矩陣鏈計算量為0，即m[i][i]=0，i=1,2,···,n。通過上一步的結(jié)果可以得到所有矩陣鏈長度為2的子問題的最優(yōu)計算量。通過上兩步的結(jié)果可以得到所有矩陣鏈長度為3的子問題的最優(yōu)計算量

………………3.1矩陣連乘問題計算m[i][j]時，只用到已計算出的m[i][k]和m[k+1][j]21SoftwareCollege,NEU

A1A2A3A4A5A630×3535×1515×55×1010×2020×25例3－2設(shè)要計算矩陣連乘積A1A2A3A4A5A6,其中各矩陣的維數(shù)分別為123456

00000015750262575010005000m[1][1]+m[2][3]+p0p1p3=7875m[1][3]=minm[1][2]+m[3][3]+p0p2p3=180009375118751512543757125105002500537535007875ij22SoftwareCollege,NEU3.計算最優(yōu)值voidMatrixChain(intp,intn,int**m,int**s){for(inti=1;i<=n;i++)m[i][i]=

;//單個矩陣的計算量

for(intr=2;r<=n;r++){//r為每次循環(huán)矩陣鏈的長度

for(inti=1;i<=

;i++){

intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){

intt=m[i][k]+m[k+1][j]+

;if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}}3.1矩陣連乘問題0n–r+1取第一個可取位置，即斷開位置為i循環(huán)取k的可取位置p[i-1]*p[k]*p[j]23SoftwareCollege,NEU計算過程先計算出m[i][i]=0,i=1,2,···,n,然后，依次計算m[i][i+1],i=1,2,···,n-1(矩陣長度為2)；m[i][i+2],i=1,2,···,n-2,(矩陣鏈長度為3)；···.每次計算只用到已計算出的m[i][k]和m[k+1][j]計算順序

m[1][1],m[2][2],m[3][3]….m[n][n]m[1][2],m[2][3],m[3][4]····m[n-1][n]m[1][3],m[2][4],m[3][5]····m[n-2][n]·····

m[1][n-1],m[2][n]

m[1][n]3.1矩陣連乘問題24SoftwareCollege,NEU算法復(fù)雜度算法MatrixChain

的主要計算量取決于程序中對r,i和k的三重循環(huán)。循環(huán)體內(nèi)的計算量為O(1)，三重循環(huán)的總次數(shù)是O(n3)，所以，算法的計算時間上界為O(n3)。3.1矩陣連乘問題25SoftwareCollege,NEU4.構(gòu)造最優(yōu)解上述算法只是明確給出了矩陣最優(yōu)連乘次序所用的數(shù)乘次數(shù)m[1][n]，并未明確給出最優(yōu)連乘次序，即完全加括號方法。但是以s[i][j]為元素的2維數(shù)組卻給出了足夠的信息。事實上，s[i][j]=k說明，計算連乘積A[i:j]的最佳方式應(yīng)該在矩陣Ak

和Ak+1之間斷開，即最優(yōu)加括號方式為(A[i:k])(A[k+1:j])。3.1矩陣連乘問題26SoftwareCollege,NEU123456011333023330333045050考慮計算A[1][6]時的順序S[1][6](A1…A3)(A4…A6)S[1][3]A1(A2A3)S[4][6](A4A5)

A6S[1][1]=0S[2][3]=2A1((A2)(A3))S[2][2]=S[3][3]=