第四讲-动态规划专题讲座.ppt

《第四讲-动态规划专题讲座.ppt》由会员分享，可在线阅读，更多相关《第四讲-动态规划专题讲座.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析算法设计与分析第四讲第四讲 动态规划动态规划算法设计与分析 第四讲 动态规划l 主要内容主要内容 动态规划的基本原理动态规划的基本原理动态规划的递推方法动态规划的递推方法 经典问题的动态规划算法设计实例经典问题的动态规划算法设计实例l 重点重点 最优性原理，动态规划的递推方法最优性原理，动态规划的递推方法l 难点难点具体问题的动态规划算法具体问题的动态规划算法算法设计与分析 第四讲 动态规划一、多段图问题一、多段图问题k 段有向图段有向图G=(V,E),|V|=n;V=V1,V2,Vk;uVi,vVi+1,1ik-1,E:c(u,v)求求s到到t的成本最小的路径的成本最小的路径s

2、,v2,v3,v4,t，其中其中,viVi。132546879111012stV1V2V3V4V54.1 基本原理基本原理算法设计与分析 第四讲 动态规划求解方案初探求解方案初探1)穷举穷举2)多级决策多级决策:分三个阶段确定最小成本路径上的节点分三个阶段确定最小成本路径上的节点v2,v3,v4132546879111012stV1V2V3V4V5算法设计与分析 第四讲 动态规划二、动态规划二、动态规划任务：任务：决策序列：决策序列：v1,v2,v3,v4,v5；v1=s,v5=t,viVi,i=2,3,4132546879111012stV1V2V3V4V5最优决策序列为路径长度最短的节点序

3、列最优决策序列为路径长度最短的节点序列 s,v2,v3,v4,t确定一个多级决策问题的最优决策序列确定一个多级决策问题的最优决策序列算法设计与分析 第四讲 动态规划状态转移过程状态转移过程状态序列状态序列s0s1sksn状态序列状态序列s0 x1xkxn决策序列决策序列算法设计与分析 第四讲 动态规划最优性原理最优性原理(最优子结构性质最优子结构性质)2)一个一个 n 级级决策是最优的，则以第决策是最优的，则以第 k(kn)级决策形成的状态作级决策形成的状态作为初态的任何一个为初态的任何一个 n-k 级级的子决策也必然是最优的。的子决策也必然是最优的。三种表述三种表述1)对于一个多级决策问题的

4、对于一个多级决策问题的最优决策最优决策来说，无论过程的初始状来说，无论过程的初始状态和初始决策是什么态和初始决策是什么,其余的决策相对于初始决策所产生的状态其余的决策相对于初始决策所产生的状态必然构成一个必然构成一个最优决策子序列最优决策子序列。3)D(i,j)=D(i,k),D(k+1,j)算法设计与分析 第四讲 动态规划例：例：k段图问题的最优性原理说明段图问题的最优性原理说明假设：假设：v1 vq vk是最短路径，是最短路径，那么：那么：v1 vq,vq vk也是最短路径。也是最短路径。算法设计与分析 第四讲 动态规划递推方法递推方法1)递推的任务递推的任务3)向后递推向后递推确定决策向

5、量 X=(x1,x2,xn)各分量的值2)向前递推向前递推算法设计与分析 第四讲 动态规划4.2 多段图多段图(multistage graph)向前递推向前递推c(i,k)=arg minc+c(i+1,j)1iK-1,1k|Vi|,1j|Vi+1|向后递推向后递推c(i,k)=arg minc(i-1,j)+c2iK,1j|Vi-1|,1k|Vi|kjt Vi Vi+1 vi,k vi+1,jc(i,k)c(i+1,j)c一、递推公式一、递推公式算法设计与分析 第四讲 动态规划二、递推算法二、递推算法节点编号节点编号0 n-1,s.t.,k|kVik|kVi+1dn:各各节节点到点到t最小

6、成本路径上的后向最小成本路径上的后向邻邻接接节节点点Cn:各节点到汇点的最短路径，各节点到汇点的最短路径，向前递推算法向前递推算法cii=n:E,cij0;pk:存存储储s到到t最小成本路径上的最小成本路径上的节节点点编编号号.算法设计与分析 第四讲 动态规划ForwardShortestPath(float cn,int k,int n)float Cn;int dn,pk;C0:n-2=MAX;Cn-1=0;for(i=n-2;i=0;i-)for(j=i+1;j0)&(cij+CjCi)Ci=cij+Cj;di=j;for(p0=0,pk-1=n-1,i=1;ik-1;k+)pi=dpi

7、-1;时间复杂度时间复杂度:O(n2)O(n+e)邻接表邻接表 邻接矩阵邻接矩阵算法设计与分析 第四讲 动态规划向后递推算法向后递推算法ForwardShortestPath(float cn,int k,int n)float Cn;int dn,pk;C0=0;C1:n-1=MAX;for(i=1;i=0;j-)if(cji0)&(Cj+cji0;k-)pi=dpi+1;算法设计与分析 第四讲 动态规划例例4.1 把把 n 个资源分配给个资源分配给 r 个项目的问题个项目的问题,如果把如果把 0jn 个资源个资源分配给项目分配给项目 i,所获得的利润为所获得的利润为 N(i,j),要求使总

8、利润最大化的分要求使总利润最大化的分配方法。配方法。r个资源分配问题的个资源分配问题的r+1段图模型段图模型:n=4n=4n=3n=2n=1n=0n=4n=3n=2n=1n=0n=0N(1,0)N(1,1)N(1,2)N(1,3)N(1,4)N(2,0)N(2,1)N(2,0)N(2,1)N(3,4)N(3,3)N(3,2)N(3,1)N(3,0)算法设计与分析 第四讲 动态规划4.3 每对节点之间的最短路径长度每对节点之间的最短路径长度 一、问题描述一、问题描述cnn是是G的成本邻接矩阵的成本邻接矩阵求每对节点之间的最短路径长度求每对节点之间的最短路径长度A(i,j).G=(V,E)为为n节

9、点的有向图节点的有向图123462113算法设计与分析 第四讲 动态规划二、递推公式二、递推公式k:编号最大的中间节点编号最大的中间节点Ak(i,j):最短路径长度最短路径长度令：令：递推公式递推公式向后逐级递推：向后逐级递推：A1(i,j),A2(i,j),An-1(i,j),An(i,j)最短路径长度：最短路径长度：A(i,j)=An(i,j)123462113算法设计与分析 第四讲 动态规划 三、算法实现时需考虑的问题三、算法实现时需考虑的问题 1)怎样表示怎样表示“”2)怎样判断怎样判断 i 到到 j 是否存在最短路径是否存在最短路径3)怎样表示怎样表示 i 到到 j 最短路径上的节点

10、序列最短路径上的节点序列算法设计与分析 第四讲 动态规划用动态规划法设计一个算法用动态规划法设计一个算法,对对page123的图的图5.12,编程并上机编程并上机实现求每对节点间的最短路径长度实现求每对节点间的最短路径长度,输出路径上的节点序列输出路径上的节点序列.课外练习：课外练习：算法设计与分析 第四讲 动态规划4.4 最优二分检索树最优二分检索树(optimal binary search tree)算法设计与分析 第四讲 动态规划ifforwhilerepeatloop图(a)ifforrepeatloopwhile图(b)一、问题描述一、问题描述成功检索的平均比较次数成功检索的平均比

11、较次数:图图(a)图图(b)12/511/54.4 最优二分检索树最优二分检索树(optimal binary search tree)算法设计与分析 第四讲 动态规划已知已知a1,a2,ana1a2anai的检索概率为的检索概率为P(i)假设假设a0=-,an+1=+aiXiai+1Xi的检索概率为的检索概率为Q(i)在整个检索空间在整个检索空间a0 X0 a1 X1 a2 X2,an-1 Xn-1 an Xn an+1算法设计与分析 第四讲 动态规划a2a1a5a4a3x0 x1x5x4x2x3检索的预期成本检索的预期成本最优二分检索树最优二分检索树使使cost(T)最小的二分检索树最小的

12、二分检索树 算法设计与分析 第四讲 动态规划二、递推方法二、递推方法最优二分检索树模型最优二分检索树模型akLR算法设计与分析 第四讲 动态规划预期检索成本预期检索成本令：算法设计与分析 第四讲 动态规划递推公式递推公式c(0,k-1)=cost(TL)c(k,n)=cost(TR)c(0,n)=cost(T)akLR算法设计与分析 第四讲 动态规划构造步骤构造步骤1)令令 j-i=1，求，求c(i,j),W(i,j),r(i,j)r(i,j)：包含：包含Xi,ai+1,Xi+1,aj,Xj等节点的最优二分检索树的根等节点的最优二分检索树的根2)令令 j-i=2,3,n，递推地求出所有，递推地

13、求出所有c(i,j),W(i,j),r(i,j)3)根据根据 r(i,j)构造最优二分检索树构造最优二分检索树算法设计与分析 第四讲 动态规划三、递推算法三、递推算法已知已知 an:a0a1a2an-1;pn,qn.初始条件为初始条件为 wii=qi;cii=0,rii=0.计算所有的计算所有的 wij,cij,rij.算法设计与分析 第四讲 动态规划OptRecursion(float*p,float*q,float cn+1,int rn+1)float wn+1n+1;for(i=0;i=n;i+)wii=qi;cii=0;rii=0;for(i=0;i=n-1;i+)wii+1=qi+

14、pi+1+qi+1;cii+1=wii+1;rii+1=i+1;for(m=2;m=n;m+)for(i=0;i=n-m;i+)for(j=i+m,wij=qi,k=i+1;k=j;k+)wij+=pk+qk;k=i+1;cij=cik-1+ckj+wij;rij=k;for(k+;k=j;k+)if(t=cik-1+ckj+wij)cij)cij=t;rij=k;时间时间复复杂杂度：度：算法设计与分析 第四讲 动态规划四、由四、由 r(i,j)构造最优二分检索树构造最优二分检索树struct NODE KEYWORD key;struct NODE*lch,*rch;struct NODE*

15、OptBinTree(i,j)struct NODE*T;if(j-ikey=arij;T-lch=OptBinTree(i,rij-1);T-rch=OptBinTree(rij,j);return T;算法设计与分析 第四讲 动态规划例例 已知 n=4,(a1,a2,a3,a4)=(do,if,read,while),p(1:4)=(3,3,1,1),q(0:4)=(2,3,1,1,1)。w(i,j),c(i,j),r(i,j)的值为：j i01234w c rw c rw c rw c rw c r02 0 08 8 112 19 116 25 216 32 213 0 07 7 29

16、12 211 19 221 0 03 3 35 8 331 0 03 3 441 0 0r(0,4)=2r(0,1)=1r(2,4)=3r(3,4)=4算法设计与分析 第四讲 动态规划4.5 0/1背包问题背包问题(0/1 knapsack problem)一、问题描述一、问题描述已知已知 M,n,wi,pi其中，其中，X=x1,x2,xn,xi0,1,pi0,wi0,0in.算法设计与分析 第四讲 动态规划二、最优性原理二、最优性原理m(l,j,X)表示表示，xi0,1,pi0,wi0,lij.,s.t.,max0/1背包问题背包问题:最优性原理表述：设最优性原理表述：设 y1,y2,yn是

17、是 m(1,n,M)的最优解，的最优解，那么，那么，y2,y3,yn必定是子问题必定是子问题 m(2,n,M-y1w1)的最优解。的最优解。m(1,n,M).算法设计与分析 第四讲 动态规划三、向后递推三、向后递推任务：任务：fi(X)：m(1,i,X)的最优解的最优解X0,f0(X)=-;X0,f0(X)=0.初始条件：初始条件：fi(X)=max fi-1(X),fi-1(X-wi)+pi 递推公式：递推公式：递推公式递推公式算法设计与分析 第四讲 动态规划例例 n=3,W=(2,3,4),P=(1,2,5),M=6.f0(X)=-0X0X0f1(X)=-max0,-+1=0max0,0+

18、1=1X00X2X2f2(X)=-max0,-+2=0 max1,-+2=1max1,0+2=2max1,1+2=3X00X22X33X5X5 f3(M)=max3,1+5=6M=6fi(X)=max fi-1(X),fi-1(X-wi)+pi X=(1,0,1)算法设计与分析 第四讲 动态规划 1 2 3 4 5 6 7 x12f0(x)=0 1 2 3 4 5 6 7 x12f0(x-w1)+p1 1 2 3 4 5 6 7 x12f1(x)图解说明图解说明f0(X)=-0X0X0f1(X)=-max0,-+1=0max0,0+1=1X00X2X2算法设计与分析 第四讲 动态规划 1 2

19、3 4 5 6 7 x12f1(x)1 2 3 4 5 6 7 x12f1(x-w2)+p23 1 2 3 4 5 6 7 x12f2(x)3f1(X)=-max0,-+1=0max0,0+1=1X00X2X2f2(X)=-max0,-+2=0 max1,-+2=1max1,0+2=2max1,1+2=3X00X22X33X5X5算法设计与分析 第四讲 动态规划 1 2 3 4 5 6 7 x12f2(x)3 1 2 3 4 5 6 7 8 9 x12f2(x-w3)+p3345678f3(x)1 2 3 4 5 6 7 8 9 x12345678f2(X)=-max0,-+2=0 max1,

20、-+2=1max1,0+2=2max1,1+2=3X00X22X33XM 的的(Pj,Wj).算法设计与分析 第四讲 动态规划例例 n=3,W=(2,3,4),P=(1,2,5),M=6。算法设计与分析 第四讲 动态规划回溯求最优决策序列回溯求最优决策序列已知最末序偶已知最末序偶(Pl,Wl)Sn,回溯求回溯求 x1,x2,xn 的步的步骤骤:l然后再判断留在然后再判断留在 Sn-1中的中的(Pl,Wl)或或(Pl-pn,Wl-wn)是否属于是否属于Sn-2以确定以确定 xn-1 的的值值,依此依此类类推推,直到推出直到推出 x1.l如果如果(Pl,Wl)Sn-1,xn=0;Sn-1,则则(P

21、l-pn,Wl-wn)Sn-1,xn=1;l如果如果(Pl,Wl)算法设计与分析 第四讲 动态规划四、递推算法四、递推算法几个变量几个变量位置位置012345678910Pm00101230125Wm00202350234Si-1l h l h l k,j h l hFn+1F0F1F2F3Fi:Si第一第一对对序偶存序偶存储储位置位置,next:P,W下一个空位下一个空位Si-1的序偶按的序偶按(Pj,Wj)的升序顺序产生并存储的升序顺序产生并存储;S1i不分配存储不分配存储,每生成一对序偶即与每生成一对序偶即与Si-1的序偶按支配的序偶按支配-清除规则归并到清除规则归并到Si.算法设计与分

22、析 第四讲 动态规划Knapsack01(float*p,float*w,float*P,float*W,int*X)int Fn+1;F0=P0=W0=0;l=h=0;next=h+1;for(i=1;i=n-1;i+)Fi=next;k=j=l;while(k=h)&(Wk+wi-1)=M)pp=Pk+pi-1;ww=Wk+wi-1;while(j=h)&(Wjww)Pnext=Pj;Wnext=Wj;next+;j+;if(jPnext-1)Pnext=pp;Wnext=ww;next+;while(j=h)&(Pj=Pnext-1)j+;k+;while(j0;i-)for(j=Fi-

23、1;Wj+wi-1M;j-);py=Pj+pi-1;wy=Wj+pi-1;if(pxpy)Xi-1=0;else Xi-1=1;px=Pj;wx=Wj;时间复杂度时间复杂度:空间复杂度：空间复杂度：1+2+2n-1=O(2n)P,W数组各需要数组各需要O(2n)的附加存储空间的附加存储空间算法设计与分析 第四讲 动态规划4.6 可靠性设计问题可靠性设计问题 一、问题描述一、问题描述该系统的可靠性为该系统的可靠性为:n台设备串联在一起构造一个系统台设备串联在一起构造一个系统:D1r1D2r2Dnrn缺点缺点:即使每一台设备的可靠性很高，系统的可靠性不一定很高即使每一台设备的可靠性很高，系统的可靠

24、性不一定很高 算法设计与分析 第四讲 动态规划解决方案解决方案:同类设备并联的多级串联系统同类设备并联的多级串联系统 D11.D1m1r1 D21.D2m2r2 Dn1.Dnmnrn第第i级的可靠性级的可靠性:系统的可靠性为系统的可靠性为:算法设计与分析 第四讲 动态规划设系统的总投资成本设系统的总投资成本C,第第i级设备的单价为级设备的单价为ci,显然显然,每一级设每一级设备至少要配置一台备至少要配置一台,那么那么,至多可配置台数为至多可配置台数为求在总投资成本求在总投资成本C的约束条件下的约束条件下,使系统可靠性最大化的设备使系统可靠性最大化的设备配置方案。配置方案。算法设计与分析 第四讲

25、 动态规划用用RELI(1,i,X)表示在容许成本表示在容许成本X约束下对约束下对1i级设备的可靠性设级设备的可靠性设计问题计问题,即即整个系统的可靠性设计问题可用整个系统的可靠性设计问题可用RELI(1,n,C)表示表示,最优解是最优解是对对m1,m2,mn的取值一系列最优决策的结果的取值一系列最优决策的结果.算法设计与分析 第四讲 动态规划二、向后递推公式二、向后递推公式最优解的可靠性为：最优解的可靠性为：初始条件：初始条件：X1;成本邻接矩阵成本邻接矩阵C:E,C(i,j)0;E,C(i,j)=;C(i,i)=0.算法设计与分析 第四讲 动态规划递推关系递推关系:（1）一般化一般化:（2

26、 2）初始条件：初始条件：g(i,)=C(i,1),i=2n（3）算法设计与分析 第四讲 动态规划g(i,不为不为i和和1的任意的任意1个顶点个顶点),i=2n;g(i,不为不为i和和1的任意的任意2个顶点个顶点),i=2n;g(i,不为不为i和和1的任意的任意3个顶点个顶点),i=2n;g(i,不为不为i和和1的任意的任意n-2个顶点个顶点),i=2n;再由再由(1)式可推出式可推出g(1,V-1),即为所求即为所求.算法设计与分析 第四讲 动态规划本讲小结本讲小结 1)多级决策与动态规划多级决策与动态规划2)动态规划的解题关键动态规划的解题关键3)动态规划算法举例动态规划算法举例算法设计与分析 第四讲 动态规划本讲作业本讲作业 参考实验指导书中的实验四参考实验指导书中的实验四,设计并实现求解多段图问题的设计并实现求解多段图问题的动态规划算法动态规划算法,并将程序模块存盘备用。并将程序模块存盘备用。参考上机作业或实验报告格式文件，提交设计报告的参考上机作业或实验报告格式文件，提交设计报告的A4打印打印稿稿,由班干部收集后统一提交。由班干部收集后统一提交。算法设计与分析 第四讲 动态规划