第8講+動(dòng)態(tài)規(guī)劃算法和實(shí)例分析課件

動(dòng)態(tài)規(guī)劃算法和實(shí)例分析動(dòng)態(tài)規(guī)劃簡介0-1背包問題最長公共子序列動(dòng)態(tài)規(guī)劃算法和實(shí)例分析動(dòng)態(tài)規(guī)劃簡介動(dòng)態(tài)規(guī)劃簡介動(dòng)態(tài)規(guī)劃的基本思想動(dòng)態(tài)規(guī)劃(DP：DynamicProgramming)是一種重要的程序設(shè)計(jì)手段，其基本思想是在對(duì)一個(gè)問題的多階段決策中，按照某一順序，根據(jù)每一步所選決策的不同，會(huì)引起狀態(tài)的轉(zhuǎn)移，最后會(huì)在變化的狀態(tài)中獲取到一個(gè)決策序列。

動(dòng)態(tài)規(guī)劃就是為了使獲取的決策序列在某種條件下達(dá)到最優(yōu)。動(dòng)態(tài)規(guī)劃是一種將多階段決策過程轉(zhuǎn)化為一系列單階段問題，然后逐個(gè)求解的程序設(shè)技方法。引例：已知6種物品和一個(gè)可載重量為60的背包，物品i(i=1,2,…,6)的重量wi分別為(15,17,20,12,9,14)，產(chǎn)生的效益pi分別為(32,37,46,26,21,30)。裝包時(shí)每一件物品可以裝入，也可以不裝，但不可拆開裝。確定如何裝包，使所得裝包總效益最大。動(dòng)態(tài)規(guī)劃簡介動(dòng)態(tài)規(guī)劃的基本思想動(dòng)態(tài)規(guī)劃簡介動(dòng)態(tài)規(guī)劃的基本思想引例分析多階段決策問題，裝每一件物品就是一個(gè)階段，每個(gè)階段都有一個(gè)決策：物品裝還是不裝。約束條件和目標(biāo)函數(shù)按照單位效益最大化裝包，得xi的序列為(0,1,1,1,1,0)，總效益為130按重量最大化裝包，得xi的序列為(0,1,1,0,1,1)，總效益為134結(jié)論：決策序列(0,1,1,0,1,1)為最優(yōu)決策序列

動(dòng)態(tài)規(guī)劃簡介動(dòng)態(tài)規(guī)劃的基本思想

動(dòng)態(tài)規(guī)劃簡介動(dòng)態(tài)規(guī)劃的步驟將所求最優(yōu)化問題分成若干個(gè)階段，找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。將問題發(fā)展到各個(gè)階段時(shí)所處的不同狀態(tài)表示出來，確定各個(gè)階段狀態(tài)之間的遞推關(guān)系，并確定初始(邊界)條件。應(yīng)用遞推求解最優(yōu)值。根據(jù)計(jì)算最有值時(shí)所得到的信息，構(gòu)造最優(yōu)解。動(dòng)態(tài)規(guī)劃問題的特征最優(yōu)子結(jié)構(gòu)。問題的最優(yōu)解包含了其子問題的最優(yōu)解，則稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。重疊子問題。用遞歸算法自頂向下解問題時(shí)，有些子問題會(huì)被反復(fù)計(jì)算多次，稱這些字問題重疊。動(dòng)態(tài)規(guī)劃算法利用這種子問題重疊性質(zhì)，對(duì)每個(gè)字問題只解一次(保存下來)，已有盡可能多的利用這些子問題的解。動(dòng)態(tài)規(guī)劃簡介動(dòng)態(tài)規(guī)劃的步驟動(dòng)態(tài)規(guī)劃算法和實(shí)例分析動(dòng)態(tài)規(guī)劃簡介0-1背包問題最長公共子序列動(dòng)態(tài)規(guī)劃算法和實(shí)例分析動(dòng)態(tài)規(guī)劃簡介0-1背包問題

0-1背包問題

0-1背包問題逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)建立遞推關(guān)系設(shè)m(i,j)為背包容量j，可取物品范圍為i,i+1,…,n的最大效益值。則當(dāng)0<=j<w(i)時(shí)，物品i不可能裝入，最大效益值與m(i+1,j)相同；當(dāng)j>=w(i)時(shí)，有兩種選擇：⑴不裝入物品i，這時(shí)的最大效益值與m(i+1,j)相同；⑵裝入物品i，這時(shí)會(huì)產(chǎn)生效益p(i)，背包剩余容量為j-w(i)，可以選擇物品i+1,…,n來裝，最大效益值為m(i+1,j-w(i))+p(i)；0-1背包問題逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)0-1背包問題

0-1背包問題

0-1背包問題逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)最優(yōu)值計(jì)算⑴根據(jù)邊界條件計(jì)算m(n,j)for(j=0;j<=c;j++)

//計(jì)算m(n,j)if(j>=w[n])m[n][j]=p[n];elsem[n][j]=0;0-1背包問題逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)⑴根據(jù)邊界條件計(jì)算m(n,0-1背包問題逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)最優(yōu)值計(jì)算⑵逆推計(jì)算m(i,j)for(i=n-1;i>=1;i--)//逆推計(jì)算m(i,j),i=n-1...1for(j=0;j<=c;j++)if(j>=w[i]&&m[i+1][j]<m[i+1][j-w[i]]+p[i]) m[i][j]=m[i+1][j-w[i]]+p[i]; else m[i][j]=m[i+1][j];⑶經(jīng)過上述推導(dǎo)，最優(yōu)值在m[1][c]中。最優(yōu)值推導(dǎo)示例0-1背包問題逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)⑵逆推計(jì)算m(i,j)最0-1背包問題逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)構(gòu)造最優(yōu)解—步驟1ifm(i,cw)>m(i+1,cw),i=1,2,…,n-1則x(i)=1，裝載w(i);其中：cw從c開始(cw=c)，cw=cw-x(i)*w(i)else

x(i)=0，不裝載w(i);cw=c;for(sp=0,sw=0,i=1;i<=n-1;i++)if(m[i][cw]>m[i+1][cw]) //x(i)=1,裝載w(i){cw-=w[i]; //cw=cw-x(i)*w(i)sw+=w[i];sp+=p[i];printf("%2d\t%3d\t%3d\n",i,w[i],p[i]);}0-1背包問題逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)cw=c;0-1背包問題逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)構(gòu)造最優(yōu)解—步驟2比較所裝載的物品效益之和與最優(yōu)值，決定w(n)是否裝載，方法：

if(m[1][c]-效益之和)等于物品n的效益p[n]

裝入w(n)if(m[1][c]-sp==p[n]) //判斷w(n)是否裝載{sw+=w[i];sp+=p[i];printf("%2d\t%3d\t%3d\n",n,w[n],p[n]);}knapsack(0-1)0-1背包問題逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)if(m[1][c]-sp動(dòng)態(tài)規(guī)劃算法和實(shí)例分析動(dòng)態(tài)規(guī)劃簡介0-1背包問題最長公共子序列動(dòng)態(tài)規(guī)劃算法和實(shí)例分析動(dòng)態(tài)規(guī)劃簡介最長公共子序列最長公共子序列概念子序列一個(gè)給定序列的子序列是在該序列中刪去若干元素后所得到的序列。即：給定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,d,c,a}是X={a,b,c,d,c,b,a}的一個(gè)子序列公共子序列若序列Z是序列X的子序列，又是序列Y的子序列，則稱Z是序列X和序列Y的公共子序列。例如：

序列"bcba"是"abcbdab"與"bdcaba"的公共子序列最長公共子序列最長公共子序列概念最長公共子序列問題描述給定兩個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出序列X和Y的最長公共子序列。最長公共子序列問題描述最長公共子序列

最長公共子序列

最長公共子序列

最長公共子序列

最長公共子序列逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)——計(jì)算最優(yōu)值⑴根據(jù)邊界條件計(jì)算c(i,n)和c(m,j)m=strlen(x);n=strlen(y);for(i=0;i<=m;i++)c[i][n]=0;for(j=0;j<=n;j++)c[m][j]=0;最長公共子序列逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)——計(jì)算最優(yōu)值⑴根據(jù)邊界條最長公共子序列逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)——計(jì)算最優(yōu)值⑵逆推計(jì)算c(i,j)for(i=m-1;i>=0;i--)for(j=n-1;j>=0;j--)if(x[i]==y[j])c[i][j]=c[i+1][j+1]+1;else{if(c[i][j+1]>c[i+1][j])c[i][j]=c[i][j+1];elsec[i][j]=c[i+1][j];}⑶經(jīng)過上述推導(dǎo)，最優(yōu)值在c[0][0]中。最優(yōu)值推導(dǎo)示例最長公共子序列逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)——計(jì)算最優(yōu)值⑵逆推計(jì)算c最長公共子序列逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)——構(gòu)造最優(yōu)解為了能夠構(gòu)造最優(yōu)解，在逆推計(jì)算最優(yōu)值的過程中，利用s(i,j)記錄x(i)與y(j)比較的結(jié)果：當(dāng)x(i)=y(j)時(shí)，s(i,j)=1當(dāng)x(i)!=y(j)時(shí)，s(i,j)=0X序列的每一項(xiàng)與Y序列的每一項(xiàng)逐一比較，根據(jù)s(i,j)與c(i,j)的取值構(gòu)造最長公共子序列。對(duì)x(i)與y(j)比較，其中i=0,1,…,m-1;j=t,…n-1(t從0開始），當(dāng)確定最長公共子序列中的一項(xiàng)時(shí)，通過t=t+1操作避免重復(fù)取項(xiàng)。若s(i,j)=1且c(i,j)=c(0,0)時(shí)，取x(i)為最長公共序列中的第1項(xiàng)。若s(i,j)=1且c(i,j)=c(0,0)-w時(shí)，取x(i)為最長公共序列中的第w項(xiàng)（其中，w從0開始，每確定最長公共子序列中的一項(xiàng)，w增一）。最長公共子序列逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)——構(gòu)造最優(yōu)解最長公共子序列逆推動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)——構(gòu)造最優(yōu)解