《第8讲动态规划算法和实例分析ppt课件》由会员分享，可在线阅读，更多相关《第8讲动态规划算法和实例分析ppt课件（21页珍藏版）》请在金锄头文库上搜索。
1、动态规划算法和实例分析动态规划算法和实例分析n n动态规划简介动态规划简介动态规划简介动态规划简介n n0-10-10-10-1背包问题背包问题背包问题背包问题n n最最最最长公共子序列长公共子序列长公共子序列长公共子序列动态规划动态规划简介简介n n动态规划的基本动态规划的基本动态规划的基本动态规划的基本思想思想思想思想 动态规划动态规划(DP(DP：Dynamic Programming)Dynamic Programming)是一种重要的程是一种重要的程序设计手段，其基本思想是在对一个问题的多阶段决策中，序设计手段，其基本思想是在对一个问题的多阶段决策中，按照某一顺序，根据每一步所选决策
2、的不同，会引起状态的按照某一顺序，根据每一步所选决策的不同，会引起状态的转移，最后转移，最后会在变化的状态中获取到一个决策序列。会在变化的状态中获取到一个决策序列。动态规划就是为了使获取的决策序列在某种条件下达动态规划就是为了使获取的决策序列在某种条件下达到最优。动态规划是一种将多阶段决策过程转化为一系列单到最优。动态规划是一种将多阶段决策过程转化为一系列单阶段问题，然后逐个求解的程序设技方法。阶段问题，然后逐个求解的程序设技方法。引例：引例：已知已知6 6种物品和一个可载重量为种物品和一个可载重量为6060的背包，物品的背包，物品i(i=1,2,i(i=1,2,6),6)的的重量重量w wi
3、 i分别为分别为(15,17,20,12,9,14)(15,17,20,12,9,14)，产生，产生的效益的效益p pi i分别为分别为(32,37,46,26,21,30)(32,37,46,26,21,30)。装包时每一件物品。装包时每一件物品可以装入，也可以不装，但不可拆开装。确定如何装包，使可以装入，也可以不装，但不可拆开装。确定如何装包，使所得装包总效益最大。所得装包总效益最大。动态规划简介动态规划简介n n动态规划的基本思想动态规划的基本思想动态规划的基本思想动态规划的基本思想n引例分析引例分析多阶段决策问题，装每一件物品就是一个阶段，每个阶段都多阶段决策问题，装每一件物品就是一个
4、阶段，每个阶段都有一个决策：物品装还是不装。有一个决策：物品装还是不装。n约束条件和约束条件和目标函数目标函数n按照单位效益最大化装按照单位效益最大化装包，得包，得x xi i的序列为的序列为(0,1,1,1,1,0)(0,1,1,1,1,0)，总效益为，总效益为130130n按重量最大化装包，得按重量最大化装包，得x xi i的序列为的序列为( (0,1,1,0,1,1)0,1,1,0,1,1)，总效，总效益为益为134134n结论：决策序列结论：决策序列( (0,1,1,0,1,1)0,1,1,0,1,1)为最优决策序列为最优决策序列动态规划简介动态规划简介n n动态规划的动态规划的动态规
5、划的动态规划的步骤步骤步骤步骤n将所求最优化问题分成若干个阶段，找出最优解的性质，将所求最优化问题分成若干个阶段，找出最优解的性质，并刻画其结构特征。并刻画其结构特征。n将问题发展到将问题发展到各个阶段时所处的不同状态表示出来，确定各个阶段时所处的不同状态表示出来，确定各个阶段状态之间的递推关系，并确定初始各个阶段状态之间的递推关系，并确定初始( (边界边界) )条件。条件。n应用递推求解最优值。应用递推求解最优值。n根据计算最有值时所得到的信息根据计算最有值时所得到的信息，构造最优解。，构造最优解。n n动态规划问题的动态规划问题的动态规划问题的动态规划问题的特征特征特征特征n最优最优子结构
6、。问题的最优解包含了其子问题的最优解，则子结构。问题的最优解包含了其子问题的最优解，则称该问题具有最优子结构性质。称该问题具有最优子结构性质。n重叠子问题重叠子问题。用递归算法自顶向下解问题时，有些子问题。用递归算法自顶向下解问题时，有些子问题会被反复计算多次，称这些字问题重叠。动态规划算法利会被反复计算多次，称这些字问题重叠。动态规划算法利用这种子问题重叠性质，对每个字问题只解一次用这种子问题重叠性质，对每个字问题只解一次( (保存下保存下来来) )，已有尽可能多的利用这些子问题的解。，已有尽可能多的利用这些子问题的解。动态规划算法和实例分析动态规划算法和实例分析n n动态规划简介动态规划简
7、介动态规划简介动态规划简介n n0-10-10-10-1背包问题背包问题背包问题背包问题n n最长公共子序列最长公共子序列最长公共子序列最长公共子序列0-10-1背包问题背包问题n n0-10-1背包问题背包问题n n逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计n建立递推关系建立递推关系设设m(i,j)m(i,j)为背包容量为背包容量j j，可取物品范围为，可取物品范围为i,i+1,i,i+1,n,n的最大的最大效益值。则效益值。则n当当0=jw(i)0=j=w(i)j=w(i)时，有两种选择：时，有两种选择：不装入物品不装入物品i i，这时的最大效益值与，
8、这时的最大效益值与m(i+1,j)m(i+1,j)相同相同；装入物品装入物品i i，这时会产生效益，这时会产生效益p(i)p(i)，背包剩余容量为，背包剩余容量为j-w(i)j-w(i)，可以选择物品，可以选择物品i+1i+1, , ,n n来装，最大效益值为来装，最大效益值为m(i+1,j-w(i)+p(i)m(i+1,j-w(i)+p(i)；0-10-1背包问题背包问题n n0-10-1背包问题背包问题n n逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计n最优值计算最优值计算根据边界条件计算根据边界条件计算m(n,j)m(n,j)for(j=0;j=c;j
9、+)for(j=0;j=wn) if(j=wn) mnj=pn; mnj=pn; else else mnj=0; mnj=0;0-10-1背包问题背包问题n n逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计n最优值计算最优值计算逆推计算逆推计算m(i,j) m(i,j) for(i=n-1;i=1;i-) for(i=n-1;i=1;i-) /逆推计算逆推计算m(i,j),i=n-1.1m(i,j),i=n-1.1 for(j=0;j=c;j+) for(j=0;j=wi&mi+1j=wi&mi+1j m(i+1,cw), i=1,2,if m(i,cw)
10、m(i+1,cw), i=1,2,n-1,n-1 则则x(i)=1x(i)=1，装载，装载w(i)w(i); ; 其中：其中：cwcw从从c c开始开始(cw=c)(cw=c)，cw=cw-x(i)*w(i)cw=cw-x(i)*w(i)elseelse x(i)=0x(i)=0，不装载，不装载w(i);w(i);cw=c;for(sp=0,sw=0,i=1;imi+1cw)/x(i)=1,装载装载w(i)cw-=wi;/cw=cw-x(i)*w(i)sw+=wi;sp+=pi;printf(%2dt%3dt%3dn,i,wi,pi);0-10-1背包问题背包问题n n逆推动态规划算法设计逆推
11、动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计n构造最优解构造最优解步骤步骤2 2比较所装载的物品效益之和与最优值，决定比较所装载的物品效益之和与最优值，决定w(n)w(n)是否装载，是否装载，方法：方法： if (m1c-if (m1c-效益之和效益之和) ) 等于等于 物品物品n n的效益的效益pnpn 装入装入w(n)w(n)if(m1c-sp=pn)/判断判断w(n)是否装载是否装载sw+=wi;sp+=pi;printf(%2dt%3dt%3dn,n,wn,pn);knapsack(0-1)动态规划算法和实例分析动态规划算法和实例分析n n动态规划简介动态规划简介动态规划简
12、介动态规划简介n n0-10-10-10-1背包问题背包问题背包问题背包问题n n最长公共子序列最长公共子序列最长公共子序列最长公共子序列最长公共子序列最长公共子序列n n最长公共子序列概念最长公共子序列概念最长公共子序列概念最长公共子序列概念n子子序列序列一个给定序列的子序列是在该序列中删去若干元素后所得到一个给定序列的子序列是在该序列中删去若干元素后所得到的序列。即：给定的序列。即：给定X=xX=x1 1,x,x2 2, ,x,xm m 和和Z=zZ=z1 1,z,z2 2, ,z,zk k ，X X的的子序列是指存在一个严格递增下标序列子序列是指存在一个严格递增下标序列ii1 1,i,i
13、2 2, ,i,ik k ，使得，使得对于所有的对于所有的j=1,2,j=1,2,k k，有，有z zj j=x=xijij。例如：。例如：Z=b,d,c,aZ=b,d,c,a是是X=a,b,c,d,c,b,aX=a,b,c,d,c,b,a的一个子序列的一个子序列n公共子序列公共子序列若序列若序列Z Z是序列是序列X X的子序列，又是序列的子序列，又是序列Y Y的子序列，则称的子序列，则称Z Z是序是序列列X X和序列和序列Y Y的公共子序列。例如：的公共子序列。例如：序列序列bcbabcba是是abcbdababcbdab与与bdcababdcaba的公共子序列的公共子序列最长公共子序列最长
14、公共子序列n n问题描述问题描述问题描述问题描述给定两个序列给定两个序列X=xX=x1 1,x,x2 2, ,x,xm m 和和Y=yY=y1 1,y,y2 2, ,y,yn n ，找出序列，找出序列X X和和Y Y的最长公共子序列。的最长公共子序列。最长公共子序列最长公共子序列n n最长公共子序列最长公共子序列n n最长公共子序列最长公共子序列n n逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计计算最优值计算最优值计算最优值计算最优值根据边界条件计算根据边界条件计算c(i,n)c(i,n)和和c(m,j)c(m,j)m=strlen(x); m=strlen
15、(x); n=strlen(y);n=strlen(y);for(i=0;i=m;i+)for(i=0;i=m;i+) cin=0; cin=0; for(j=0;j=n;j+)for(j=0;j=0;i-)for(i=m-1;i=0;i-) for(j=n-1;j=0;j-) for(j=n-1;j=0;j-) if(xi=yj) if(xi=yj) cij=ci+1j+1+1; cij=ci+1j+1+1; else else if(cij+1ci+1j) if(cij+1ci+1j) cij=cij+1; cij=cij+1; else else cij=ci+1j; cij=ci+1j
16、; 经过上述推导，最优值在经过上述推导，最优值在c00c00中。中。最优值推导示例最优值推导示例最长公共子序列最长公共子序列n n逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计构造最优解构造最优解构造最优解构造最优解为了能够构造最优解，在逆推计算最优值的过程中，利用为了能够构造最优解，在逆推计算最优值的过程中，利用s(i,j)s(i,j)记录记录x(i)x(i)与与y(j)y(j)比较的结果：比较的结果：l当当x(i)=y(j)x(i)=y(j)时，时， s(i,j)=1 s(i,j)=1l当当x(ix(i) )! !=y(j)=y(j)时，时，s(i,j)=
17、0s(i,j)=0X X序列的每一项与序列的每一项与Y Y序列的每一项逐一比较，根据序列的每一项逐一比较，根据s(i,j)s(i,j)与与c(i,j)c(i,j)的取值构造最长公共子序列。对的取值构造最长公共子序列。对x(i)x(i)与与y(j)y(j)比较，其比较，其中中i=0,1,i=0,1,m-1; j=t,m-1; j=t,n-1(tn-1(t从从0 0开始），当确定最长公共开始），当确定最长公共子序列中的一项时，通过子序列中的一项时，通过t=t+1t=t+1操作避免重复取项。操作避免重复取项。l若若s(i,j)=1s(i,j)=1且且c(i,j)=c(0,0)c(i,j)=c(0,0
18、)时，取时，取x(i)x(i)为最长公共序列为最长公共序列中的第中的第1 1项。项。l若若s(i,j)=1s(i,j)=1且且c(i,j)=c(0,0)-wc(i,j)=c(0,0)-w时，取时，取x(i)x(i)为最长公共序为最长公共序列中的第列中的第w w项（其中，项（其中，w w从从0 0开始，每确定最长公共子序列开始，每确定最长公共子序列中的一项，中的一项，w w增一）。增一）。最长公共子序列最长公共子序列n n逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计逆推动态规划算法设计构造最优解构造最优解构造最优解构造最优解for(t=0,w=0,i=0;i=m-1;i+)for(t=0,w=0,i=0;i=m-1;i+) for(j=t;j=n-1;j+) for(j=t;j=n-1;j+) if(sij=1 & cij=c00-w) if(sij=1 & cij=c00-w) printf(%c,xi);printf(%c,xi);w+;w+;t=j+1;t=j+1;break;break; CommonSubsequenceCommonSubsequence
