《算法設(shè)計(jì)與分析》第三章動(dòng)態(tài)規(guī)劃課件

第3章動(dòng)態(tài)規(guī)劃（Dynamic-Programming）3.1動(dòng)態(tài)規(guī)劃法的基本思想3.2動(dòng)態(tài)規(guī)劃法的適用條件3.3動(dòng)態(tài)規(guī)劃法的基本步驟3.4應(yīng)用舉例－0/1背包問(wèn)題第3章動(dòng)態(tài)規(guī)劃（Dynamic-Programming）33.1動(dòng)態(tài)規(guī)劃法的基本思想為求解給定問(wèn)題，有一系列子問(wèn)題需要解答。對(duì)這些子問(wèn)題按照某種方式仔細(xì)設(shè)計(jì)，使得其后的每一個(gè)子問(wèn)題都可以通過(guò)上面已經(jīng)求出的一個(gè)或多個(gè)子問(wèn)題的合并而獲得其解。3.1動(dòng)態(tài)規(guī)劃法的基本思想為求解給定問(wèn)題，有一系列子問(wèn)題需3.1動(dòng)態(tài)規(guī)劃法的基本思想動(dòng)態(tài)規(guī)劃法與分治法的異同：與分治法類似，動(dòng)態(tài)規(guī)劃法也是對(duì)問(wèn)題進(jìn)行遞歸分解。而當(dāng)遞歸分解得到的子問(wèn)題不互相獨(dú)立時(shí)，用分治法求解，則有些子問(wèn)題被重復(fù)計(jì)算了許多次。而動(dòng)態(tài)規(guī)劃法通過(guò)保存已解決的子問(wèn)題的解，在需要時(shí)再找出已求得的解，可以避免大量重復(fù)計(jì)算。3.1動(dòng)態(tài)規(guī)劃法的基本思想動(dòng)態(tài)規(guī)劃法與分治法的異同：3.2動(dòng)態(tài)規(guī)劃法的適用條件動(dòng)態(tài)規(guī)劃法解所能解決的問(wèn)題一般具有以下兩個(gè)基本因素：一、最優(yōu)子結(jié)構(gòu)性質(zhì)

當(dāng)問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解時(shí)，稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。二、重疊子問(wèn)題性質(zhì) 遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問(wèn)題的重疊性質(zhì)。其它同分治法3.2動(dòng)態(tài)規(guī)劃法的適用條件動(dòng)態(tài)規(guī)劃法解所能解決的問(wèn)題一般具3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì) 當(dāng)問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解時(shí)，稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。例1：Fibonacci數(shù)問(wèn)題

nn≤1F(n)＝

F(n-1)＋F(n-2)n>13.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì) 當(dāng)問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解時(shí)，稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。例2：求解二項(xiàng)式系數(shù)11m=0n=m其它＝3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)11m=0n=3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)

在分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的，然后再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解，從而導(dǎo)致矛盾。3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)在分析問(wèn)題的最3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)

例3最短路徑問(wèn)題 設(shè)G是有向圖，若G中從頂點(diǎn)i到頂點(diǎn)j有路徑存在，找出最短的一條。下面證明最短路徑問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)例3最短路3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)證明：設(shè)i,i1,i2,…,ik,j是從i到j(luò)的一條最短路徑。從初始頂點(diǎn)i開始，設(shè)從i到下一頂點(diǎn)i1的判定已經(jīng)做出。接下去，問(wèn)題就轉(zhuǎn)化為用i1替代i，重復(fù)原來(lái)的問(wèn)題，找出一條從i1到j(luò)的路徑。顯然，i1,i2,…,ik,j一定構(gòu)成了從從i1到j(luò)的最短路徑（與原問(wèn)題相同的最優(yōu)子序列）

3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)證明：3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)證明： 若不然，設(shè)i1,r1,r2,…,rp,j是一條從i1

到j(luò)的最短路徑，則i,i1,r1,r2,…,rp,j將是一條從i到j(luò)的路徑且比路徑i,i1,i2,…,ik,j要短，得出矛盾。所以，最短路徑問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)證明：3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)

利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。3.2動(dòng)態(tài)規(guī)劃法的適用條件一、最優(yōu)子結(jié)構(gòu)性質(zhì)利用問(wèn)題的最優(yōu)3.2動(dòng)態(tài)規(guī)劃法的適用條件二、重疊子問(wèn)題性質(zhì) 遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問(wèn)題的重疊性質(zhì)。3.2動(dòng)態(tài)規(guī)劃法的適用條件二、重疊子問(wèn)題性質(zhì)3.2動(dòng)態(tài)規(guī)劃法的適用條件二、重疊子問(wèn)題性質(zhì) 例1：Fibonacci數(shù)問(wèn)題的遞歸樹Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)T(n)=O(Fib(n))3.2動(dòng)態(tài)規(guī)劃法的適用條件二、重疊子問(wèn)題性質(zhì)Fib(5)F3.2動(dòng)態(tài)規(guī)劃法的適用條件二、重疊子問(wèn)題性質(zhì) 例2：求解二項(xiàng)式系數(shù)的遞歸樹T(n)=O()3.2動(dòng)態(tài)規(guī)劃法的適用條件二、重疊子問(wèn)題性質(zhì)T(n)=O(3.3動(dòng)態(tài)規(guī)劃法的基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。－－考察是否適合采用動(dòng)態(tài)規(guī)劃法。遞歸地定義最優(yōu)值(建立遞歸式或動(dòng)態(tài)規(guī)劃方程)。以自底向上迭代的方式（或以自頂向下的備忘錄方法）計(jì)算出最優(yōu)值；根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。3.3動(dòng)態(tài)規(guī)劃法的基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特3.3動(dòng)態(tài)規(guī)劃法的基本步驟例1Fibonacci數(shù)問(wèn)題 求解步驟：

1具有最優(yōu)子結(jié)構(gòu)性質(zhì)

2具有重疊子問(wèn)題性質(zhì)

3建立遞歸式或動(dòng)態(tài)規(guī)劃方程

4求解值。3.3動(dòng)態(tài)規(guī)劃法的基本步驟例1Fibonacci數(shù)問(wèn)題3.3動(dòng)態(tài)規(guī)劃法的基本步驟intFib(intn){f1=f2=0;for(f=1,i=0;i<=n;i++){ f2=f1;f1=f;f=f1+f2;}returnf;}3.3動(dòng)態(tài)規(guī)劃法的基本步驟intFib(intn)3.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù) 求解步驟：

1具有最優(yōu)子結(jié)構(gòu)性質(zhì)

2具有重疊子問(wèn)題性質(zhì)

3建立遞歸式或動(dòng)態(tài)規(guī)劃方程

4求解。3.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù)3.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù) 求解方法：

1動(dòng)態(tài)規(guī)劃法：計(jì)算如下序列：

S0={} S1={，}

S2={，，}Sn={，，，…,}3.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù)Sn={3.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù)

1動(dòng)態(tài)規(guī)劃法：

Pascal三角形n011112121313314146415151010516161520156171721353521713.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù)Pascal3.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù)intBinom（intn,intm）{ intb[MAXSIZE]; b[0]=1; for(i=1;i<=n;i++){ b[i]=1 for(j=i-1;j>0;j++) b[j]=b[j]+b[j-1]; } returnb[m];}3.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù)3.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù) 求解方法：

2備忘錄法：

備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看，避免了相同子問(wèn)題的重復(fù)求解。3.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù)備忘錄方法的3.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù)2備忘錄法：

intBinom（intn,intm）{ if(n==m||m==0){filltable(n,m,0);return1;}else{ if(!lookupTable(n-1,m,t1)){ t1=Binom(n-1,m);filltable(n-1,m,t1); } if(!lookupTable(n-1,m-1,t2)){ t2=Binom(n-1,m-1);filltable(n-1,m-1,t2); }returnt1+t2;}}3.3動(dòng)態(tài)規(guī)劃法的基本步驟例2求解二項(xiàng)式系數(shù)intBi3.4應(yīng)用舉例－0/1背包問(wèn)題0-1背包問(wèn)題給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。3.4應(yīng)用舉例－0/1背包問(wèn)題0-1背包問(wèn)題給定n種物品和3.4應(yīng)用舉例－0/1背包問(wèn)題1最優(yōu)子結(jié)構(gòu)性質(zhì)考查

2建立遞歸方程

3重疊子問(wèn)題性質(zhì)考查

4求解

3.4應(yīng)用舉例－0/1背包問(wèn)題1最優(yōu)子結(jié)構(gòu)性質(zhì)考查

20-1背包問(wèn)題設(shè)所給0-1背包問(wèn)題的子問(wèn)題的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問(wèn)題的最優(yōu)值。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下。0-1背包問(wèn)題設(shè)所給0-1背包問(wèn)題的子問(wèn)題的最優(yōu)值為m(i，3.4應(yīng)用舉例－0/1背包問(wèn)題求解：

1動(dòng)態(tài)規(guī)劃法

//權(quán)為整數(shù)的迭代法思考：備忘錄法3.4應(yīng)用舉例－0/1背包問(wèn)題求解：

1動(dòng)態(tài)規(guī)劃法

/0-1背包問(wèn)題---權(quán)為整數(shù)的迭代法voidKnapSack(intv[],intw[],intc,intn,intm[][])//求m[][]{intjMax=min(w[n]-1,c);for(j=0;j<=jMax;j++)//m(n,j)=00=<j<w[n] m[n][j]=0;for(j=w[n];j<=c;j++)//m(n,j)=v[n]j>=w[n] m[n][j]=v[n];for(i=n-1;i>1;i--){ intjMax=min(w[i]-1,c); for(j=0;j<=jMax;j++)//m(i,j)=m(i+1,j)0=<j<w[i] m[i][j]=m[i+1][j]; for(j=w[i];j<=c;j++)//m(n,j)=v[n]j>=w[n] m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1]) m[1][c]=max(m[