《第四讲动态规划优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第四讲动态规划优秀PPT.ppt（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一页，本课件共有59页n 主要内容主要内容 动态规划的基本原理动态规划的基本原理动态规划的基本原理动态规划的基本原理动态规划的递推方法动态规划的递推方法动态规划的递推方法动态规划的递推方法 经典问题的动态规划算法设计实例经典问题的动态规划算法设计实例经典问题的动态规划算法设计实例经典问题的动态规划算法设计实例n 重点重点 最优性原理，动态规划的递推方法最优性原理，动态规划的递推方法最优性原理，动态规划的递推方法最优性原理，动态规划的递推方法n 难点难点具体问题的动态规划算法具体问题的动态规划算法具体问题的动态规划算法具体问题的动态规划算法第二页，本课件共有59页一、多段图问题一、多段图问题k
2、 段有向图段有向图G=(V,E),|V|=n;V=V1,V2,Vk;uVi,vVi+1,1ik-1,E:c(u,v)求求s到到t的成本最小的路径的成本最小的路径s,v2,v3,v4,t，其中其中,viVi。132546879111012stV1V2V3V4V54.1 基本原理基本原理第三页，本课件共有59页求解方案初探求解方案初探1)1)穷举穷举穷举穷举2)2)多级决策多级决策多级决策多级决策:分三个阶段确定最小成本路径上的节点分三个阶段确定最小成本路径上的节点分三个阶段确定最小成本路径上的节点分三个阶段确定最小成本路径上的节点v2,v3,v4v2,v3,v4132546879111012st
3、V1V2V3V4V5第四页，本课件共有59页二、动态规划二、动态规划任务：任务：决策序列：决策序列：v1,v2,v3,v4,v5；v1=s,v5=t,viVi,i=2,3,4132546879111012stV1V2V3V4V5最优决策序列为路径长度最短的节点序列最优决策序列为路径长度最短的节点序列 s,v2,v3,v4,t确定一个多级决策问题的最优决策序列确定一个多级决策问题的最优决策序列第五页，本课件共有59页状态转移过程状态转移过程状态序列状态序列s0s1sksn状态序列状态序列s0 x1xkxn决策序列决策序列第六页，本课件共有59页最优性原理最优性原理最优性原理最优性原理(最优子结构
4、性质最优子结构性质)2)2)一个一个一个一个 n n 级级级级决策是最优的，则以第决策是最优的，则以第决策是最优的，则以第决策是最优的，则以第 k(kn)k(kn)级决策形成的状态作为级决策形成的状态作为级决策形成的状态作为级决策形成的状态作为初态的任何一个初态的任何一个初态的任何一个初态的任何一个 n-k n-k 级级级级的子决策也必然是最优的。的子决策也必然是最优的。的子决策也必然是最优的。的子决策也必然是最优的。三种表述三种表述1)1)对于一个多级决策问题的对于一个多级决策问题的对于一个多级决策问题的对于一个多级决策问题的最优决策最优决策最优决策最优决策来说，无论过程的初始状态和来说，无
5、论过程的初始状态和来说，无论过程的初始状态和来说，无论过程的初始状态和初始决策是什么初始决策是什么初始决策是什么初始决策是什么,其余的决策相对于初始决策所产生的状态必然构成一其余的决策相对于初始决策所产生的状态必然构成一其余的决策相对于初始决策所产生的状态必然构成一其余的决策相对于初始决策所产生的状态必然构成一个个个个最优决策子序列最优决策子序列最优决策子序列最优决策子序列。3)D(i,j)=D(i,k),D(k+1,j)3)D(i,j)=D(i,k),D(k+1,j)第七页，本课件共有59页例：例：k段图问题的最优性原理说明段图问题的最优性原理说明假设：假设：v1 vq vk是最短路径，是最
6、短路径，那么：那么：v1 vq,vq vk也是最短路径。也是最短路径。第八页，本课件共有59页递推方法递推方法递推方法递推方法1)1)递推的任务递推的任务递推的任务递推的任务3)3)向后递推向后递推向后递推向后递推确定决策向量 X=(x1,x2,xn)各分量的值2)2)向前递推向前递推向前递推向前递推第九页，本课件共有59页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 V
7、i Vi+1 vi,k vi+1,jc(i,k)c(i+1,j)c一、递推公式一、递推公式第十页，本课件共有59页二、递推算法二、递推算法节点编号节点编号0 n-1,s.t.,k|kVik|kVi+1dn:各各节节点到点到t最小成本路径上的后向最小成本路径上的后向邻邻接接节节点点Cn:各节点到汇点的最短路径，各节点到汇点的最短路径，向前递推算法向前递推算法cii=n:E,cij0;pk:存存储储s到到t最小成本路径上的最小成本路径上的节节点点编编号号.第十一页，本课件共有59页ForwardShortestPath(float cn,int k,int n)ForwardShortestPat
8、h(float cn,int k,int n)float Cn;int dn,pk;C0:n-2=MAX;Cn-1=0;float Cn;int dn,pk;C0:n-2=MAX;Cn-1=0;for(i=n-2;i=0;i-)for(i=n-2;i=0;i-)for(j=i+1;j=n-1;j+)for(j=i+1;j0)&(cij+Cj0)&(cij+CjCi)Ci=cij+Cj;Ci=cij+Cj;di=j;di=j;for(p0=0,pk-1=n-1,i=1;ik-1;k+)pi=dpi-1;for(p0=0,pk-1=n-1,i=1;ik-1;k+)pi=dpi-1;时间复杂度时间复
9、杂度:O(n2)O(n+e)邻接表邻接表 邻接矩阵邻接矩阵第十二页，本课件共有59页向后递推算法向后递推算法ForwardShortestPath(float cn,int k,int n)ForwardShortestPath(float cn,int k,int n)float Cn;int dn,pk;C0=0;C1:n-1=MAX;float Cn;int dn,pk;C0=0;C1:n-1=MAX;for(i=1;i=n-1;i+)for(i=1;i=0;j-)for(j=i-1;j=0;j-)if(cji0)&(Cj+cji0)&(Cj+cji0;k-)pi=dpi+1;i=k-2
10、;i0;k-)pi=dpi+1;第十三页，本课件共有59页例例4.1 把把 n 个资源分配给个资源分配给 r 个项目的问题个项目的问题,如果把如果把 0jn 个资源分个资源分配给项目配给项目 i,所获得的利润为所获得的利润为 N(i,j),要求使总利润最大化的分配方要求使总利润最大化的分配方法。法。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)第
11、十四页，本课件共有59页4.3 每对节点之间的最短路径长度每对节点之间的最短路径长度 一、问题描述一、问题描述cnn是是G的成本邻接矩阵的成本邻接矩阵求每对节点之间的最短路径长度求每对节点之间的最短路径长度A(i,j).G=(V,E)为为n节点的有向图节点的有向图123462113第十五页，本课件共有59页二、递推公式二、递推公式k:k:编号最大的中间节点编号最大的中间节点编号最大的中间节点编号最大的中间节点Ak(i,j):最短路径长度最短路径长度令：令：递推公式递推公式向后逐级递推：向后逐级递推：A1(i,j),A2(i,j),An-1(i,j),An(i,j)最短路径长度：最短路径长度：A
12、(i,j)=An(i,j)123462113第十六页，本课件共有59页 三、算法实现时需考虑的问题三、算法实现时需考虑的问题 1)1)怎样表示怎样表示怎样表示怎样表示“”“”2)2)怎样判断怎样判断怎样判断怎样判断 i i 到到到到 j j 是否存在最短路径是否存在最短路径是否存在最短路径是否存在最短路径3)3)怎样表示怎样表示怎样表示怎样表示 i i 到到到到 j j 最短路径上的节点序列最短路径上的节点序列最短路径上的节点序列最短路径上的节点序列第十七页，本课件共有59页用动态规划法设计一个算法用动态规划法设计一个算法用动态规划法设计一个算法用动态规划法设计一个算法,对对对对page123
13、page123的图的图的图的图5.12,5.12,编程并上机实现编程并上机实现编程并上机实现编程并上机实现求每对节点间的最短路径长度求每对节点间的最短路径长度求每对节点间的最短路径长度求每对节点间的最短路径长度,输出路径上的节点序列输出路径上的节点序列输出路径上的节点序列输出路径上的节点序列.课外练习：课外练习：第十八页，本课件共有59页4.4 最优二分检索树最优二分检索树(optimal binary search tree)(optimal binary search tree)第十九页，本课件共有59页ifforwhilerepeatloop图(a)ifforrepeatloopwhil
14、e图(b)一、问题描述一、问题描述成功检索的平均比较次数成功检索的平均比较次数:图图(a)图图(b)12/511/54.4 最优二分检索树最优二分检索树(optimal binary search tree)(optimal binary search tree)第二十页，本课件共有59页已知已知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第二十一页，本课件共有59页a2a1a5a4a3x0
15、 x1x5x4x2x3检索的预期成本检索的预期成本最优二分检索树最优二分检索树使使cost(T)最小的二分检索树最小的二分检索树 第二十二页，本课件共有59页二、递推方法二、递推方法最优二分检索树模型最优二分检索树模型akLR第二十三页，本课件共有59页预期检索成本预期检索成本令：第二十四页，本课件共有59页递推公式递推公式c(0,k-1)=cost(TL)c(k,n)=cost(TR)c(0,n)=cost(T)akLR第二十五页，本课件共有59页构造步骤构造步骤1)1)令令令令 j-i=1j-i=1，求，求，求，求c(i,j),W(i,j),r(i,j)c(i,j),W(i,j),r(i,
16、j)r(i,j)：包含：包含Xi,ai+1,Xi+1,aj,Xj等节点的最优二分检索树的根等节点的最优二分检索树的根2)2)令令令令 j-i=2,3,nj-i=2,3,n，递推地求出所有，递推地求出所有，递推地求出所有，递推地求出所有c(i,j),W(i,j),r(i,j)c(i,j),W(i,j),r(i,j)3)3)根据根据根据根据 r(i,j)r(i,j)构造最优二分检索树构造最优二分检索树构造最优二分检索树构造最优二分检索树第二十六页，本课件共有59页三、递推算法三、递推算法已知已知 an:a0a1a2an-1;pn,qn.初始条件为初始条件为 wii=qi;cii=0,rii=0.计
17、算所有的计算所有的 wij,cij,rij.第二十七页，本课件共有59页OptRecursion(float*p,float*q,float cn+1,int rn+1)OptRecursion(float*p,float*q,float cn+1,int rn+1)float wn+1n+1;float wn+1n+1;for(i=0;i=n;i+)wii=qi;cii=0;rii=0;for(i=0;i=n;i+)wii=qi;cii=0;rii=0;for(i=0;i=n-1;i+)for(i=0;i=n-1;i+)wii+1=qi+pi+1+qi+1;cii+1=wii+1;rii+1
18、=i+1;wii+1=qi+pi+1+qi+1;cii+1=wii+1;rii+1=i+1;for(m=2;m=n;m+)for(m=2;m=n;m+)for(i=0;i=n-m;i+)for(i=0;i=n-m;i+)for(j=i+m,wij=qi,k=i+1;k=j;k+)wij+=pk+qk;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;k=i+1;cij=cik-1+ckj+wij;rij=k;for(k+;k=j;k+)for(k+;k=j;k+)if(t=cik-1+ckj+wij)c
19、ij)cij=t;rij=k;if(t=cik-1+ckj+wij)cij)cij=t;rij=k;时间时间复复杂杂度：度：第二十八页，本课件共有59页四、由四、由 r(i,j)构造最优二分检索树构造最优二分检索树struct NODE KEYWORD key;struct NODE*lch,*rch;struct NODE*OptBinTree(i,j)struct NODE*T;if(j-ikey=arij;T-lch=OptBinTree(i,rij-1);T-rch=OptBinTree(rij,j);return T;第二十九页，本课件共有59页例例 已知 n=4,(a1,a2,a3
20、,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 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第三十页，本课件共有59页4.5 0/1背包问题背包问题(0/1 knapsack problem)一、问题描述一、问题描述
21、已知已知 M,n,wi,pi其中，其中，X=x1,x2,xn,xi0,1,pi0,wi0,0in.第三十一页，本课件共有59页二、最优性原理二、最优性原理m(l,j,X)表示表示，xi0,1,pi0,wi0,lij.,s.t.,max0/1背包问题背包问题:最优性原理表述：设最优性原理表述：设 y1,y2,yn是是 m(1,n,M)的最优解，的最优解，那么，那么，y2,y3,yn必定是子问题必定是子问题 m(2,n,M-y1w1)的最优解。的最优解。m(1,n,M).第三十二页，本课件共有59页三、向后递推三、向后递推任务：任务：fi(X)：m(1,i,X)的最优解的最优解X0,f0(X)=-
22、;X0,f0(X)=0.初始条件：初始条件：fi(X)=max fi-1(X),fi-1(X-wi)+pi 递推公式：递推公式：递推公式递推公式第三十三页，本课件共有59页例例 n=3,W=(2,3,4),P=(1,2,5),M=6.f0(X)=-0X0X0f1(X)=-max0,-+1=0max0,0+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)第三十四页，本课件共有59页
23、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第三十五页，本课件共有59页 1 2 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
24、=3X00X22X33X5X5第三十六页，本课件共有59页 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,-+2=1max1,0+2=2max1,1+2=3X00X22X33XM 的的(Pj,Wj).第四十一页，本课件共有59页例例 n=3,W=(2,3,4),P=(1,2,5),M=6。第四十二页，本课件共有59页回溯求最优决策序列回溯求最优决策序列已知最末序偶已知最末序偶已知最末序偶已知最末序偶 (P(P
25、l l,W,Wl l)S Sn n,回溯求回溯求回溯求回溯求 x x1 1,x,x2 2,x,xn n 的步的步的步的步骤骤骤骤:n n然后再判断留在然后再判断留在然后再判断留在然后再判断留在 S Sn-1n-1中的中的中的中的 (P(Pl l,W,Wl l)或或或或 (P(Pl l-p-pn n,W,Wl l-w-wn n)是否属于是否属于是否属于是否属于S Sn-2n-2以确定以确定以确定以确定 x xn-1n-1 的的的的值值值值,依此依此依此依此类类类类推推推推,直到推出直到推出直到推出直到推出 x x1 1.n n如果如果如果如果 (P(Pl l,W,Wl l)Sn-1,xn=0;S
26、n-1,则则(Pl-pn,Wl-wn)Sn-1,xn=1;n n如果如果如果如果 (P(Pl l,W,Wl l)第四十三页，本课件共有59页四、递推算法四、递推算法几个变量几个变量位置位置012345678910Pm00101230125Wm00202350234Si-1l h l h l k,j h l hFn+1F0F1F2F3Fi:Si第一第一对对序偶存序偶存储储位置位置,next:P,W下一个空位下一个空位S Si-1i-1的序偶按的序偶按的序偶按的序偶按(P(Pj j,W,Wj j)的升序顺序产生并存储的升序顺序产生并存储的升序顺序产生并存储的升序顺序产生并存储;S S1 1i i不
27、分配存储不分配存储不分配存储不分配存储,每生成一对序偶即与每生成一对序偶即与每生成一对序偶即与每生成一对序偶即与S Si-1i-1的序偶按支配的序偶按支配的序偶按支配的序偶按支配-清除规则归并到清除规则归并到清除规则归并到清除规则归并到S Si i.第四十四页，本课件共有59页Knapsack01(float*p,float*w,float*P,float*W,int*X)Knapsack01(float*p,float*w,float*P,float*W,int*X)int Fn+1;F0=P0=W0=0;l=h=0;next=h+1;int Fn+1;F0=P0=W0=0;l=h=0;ne
28、xt=h+1;for(i=1;i=n-1;i+)for(i=1;i=n-1;i+)Fi=next;k=j=l;Fi=next;k=j=l;while(k=h)&(Wk+wi-1)=M)while(k=h)&(Wk+wi-1)=M)pp=Pk+pi-1;ww=Wk+wi-1;pp=Pk+pi-1;ww=Wk+wi-1;while(j=h)&(Wjww)Pnext=Pj;Wnext=Wj;next+;j+;while(j=h)&(Wjww)Pnext=Pj;Wnext=Wj;next+;j+;if(j=h)&(Wj=ww)pp=max(pp,Pj);j+;if(jPnext-1)Pnext=pp;
29、Wnext=ww;next+;if(ppPnext-1)Pnext=pp;Wnext=ww;next+;while(j=h)&(Pj=Pnext-1)j+;k+;while(j=h)&(Pj=Pnext-1)j+;k+;while(j=h)Pnext=Pj;Wnext=Wj;next+;j+;while(j0;i-)for(j=Fi-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)的
30、附加存储空间的附加存储空间第四十六页，本课件共有59页4.6 可靠性设计问题可靠性设计问题 一、问题描述一、问题描述该系统的可靠性为该系统的可靠性为:n台设备串联在一起构造一个系统台设备串联在一起构造一个系统:D1r1D2r2Dnrn缺点缺点:即使每一台设备的可靠性很高，系统的可靠性不一定很高即使每一台设备的可靠性很高，系统的可靠性不一定很高 第四十七页，本课件共有59页解决方案解决方案:同类设备并联的多级串联系统同类设备并联的多级串联系统 D11.D1m1r1 D21.D2m2r2 Dn1.Dnmnrn第第i级的可靠性级的可靠性:系统的可靠性为系统的可靠性为系统的可靠性为系统的可靠性为:第四
31、十八页，本课件共有59页设系统的总投资成本设系统的总投资成本设系统的总投资成本设系统的总投资成本C,C,第第第第i i级设备的单价为级设备的单价为级设备的单价为级设备的单价为c ci i,显然显然显然显然,每一级设备至少每一级设备至少每一级设备至少每一级设备至少要配置一台要配置一台要配置一台要配置一台,那么那么那么那么,至多可配置台数为至多可配置台数为至多可配置台数为至多可配置台数为求在总投资成本求在总投资成本求在总投资成本求在总投资成本C C的约束条件下的约束条件下的约束条件下的约束条件下,使系统可靠性最大化的设备配置使系统可靠性最大化的设备配置使系统可靠性最大化的设备配置使系统可靠性最大化
32、的设备配置方案。方案。方案。方案。第四十九页，本课件共有59页用用用用RELI(1,i,X)RELI(1,i,X)表示在容许成本表示在容许成本表示在容许成本表示在容许成本X X约束下对约束下对约束下对约束下对1i1i级设备的可靠性设计问级设备的可靠性设计问级设备的可靠性设计问级设备的可靠性设计问题题题题,即即即即整个系统的可靠性设计问题可用整个系统的可靠性设计问题可用整个系统的可靠性设计问题可用整个系统的可靠性设计问题可用RELI(1,n,C)RELI(1,n,C)表示表示表示表示,最优解是对最优解是对最优解是对最优解是对mm1 1,m,m2 2,m,mn n的取值一系列最优决策的结果的取值一
33、系列最优决策的结果的取值一系列最优决策的结果的取值一系列最优决策的结果.第五十页，本课件共有59页二、向后递推公式二、向后递推公式最优解的可靠性为：最优解的可靠性为：初始条件：初始条件：X1;成本邻接矩阵成本邻接矩阵C:E,C(i,j)0;E,C(i,j)=;C(i,i)=0.第五十五页，本课件共有59页递推关系递推关系:（1）一般化一般化:（2 2）初始条件：初始条件：g(i,)=C(i,1),i=2n（3）第五十六页，本课件共有59页g g(i i,不为不为不为不为i i和和和和1 1的任意的任意的任意的任意1 1个顶点个顶点个顶点个顶点),i=2n;),i=2n;g g(i i,不为不为
34、不为不为i i和和和和1 1的任意的任意的任意的任意2 2个顶点个顶点个顶点个顶点),i=2n;),i=2n;g g(i i,不为不为不为不为i i和和和和1 1的任意的任意的任意的任意3 3个顶点个顶点个顶点个顶点),i=2n;),i=2n;g g(i i,不为不为不为不为i i和和和和1 1的任意的任意的任意的任意n-2n-2个顶点个顶点个顶点个顶点),i=2n;),i=2n;再由再由(1)式可推出式可推出g(1,V-1),即为所求即为所求.第五十七页，本课件共有59页本讲小结本讲小结 1)多级决策与动态规划多级决策与动态规划2)动态规划的解题关键动态规划的解题关键3)动态规划算法举例动态
35、规划算法举例第五十八页，本课件共有59页本讲作业本讲作业 参考实验指导书中的实验四参考实验指导书中的实验四参考实验指导书中的实验四参考实验指导书中的实验四,设计并实现求解多段图问题的动态设计并实现求解多段图问题的动态设计并实现求解多段图问题的动态设计并实现求解多段图问题的动态规划算法规划算法规划算法规划算法 ,并将程序模块存盘备用。并将程序模块存盘备用。并将程序模块存盘备用。并将程序模块存盘备用。参考上机作业或实验报告格式文件，提交设计报告的参考上机作业或实验报告格式文件，提交设计报告的参考上机作业或实验报告格式文件，提交设计报告的参考上机作业或实验报告格式文件，提交设计报告的A4A4打印稿打印稿打印稿打印稿,由由由由班干部收集后统一提交。班干部收集后统一提交。班干部收集后统一提交。班干部收集后统一提交。第五十九页，本课件共有59页