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

《第四讲-动态规划专题讲座.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、算法设计与分析第四讲动态规划算法设计与分析第四讲动态规划主要内容动态规划的基本原理动态规划的递推方法经典问题的动态规划算法设计实例重点最优性原理，动态规划的递推方法难点具体问题的动态规划算法算法设计与分析第四讲动态规划一、多段图问题k段有向图G=(V,E),

2、V

3、=n;V={V1,V2,…,Vk};u∈Vi,v∈Vi+1,1≤i∈E:c(u,v)求s到t的成本最小的路径s,v2,v3,v4,t，其中,vi∈Vi。132546879111012stV1V2V3V4V54.1基本原理算

4、法设计与分析第四讲动态规划求解方案初探1)穷举2)多级决策:分三个阶段确定最小成本路径上的节点v2,v3,v4132546879111012stV1V2V3V4V5算法设计与分析第四讲动态规划二、动态规划任务：决策序列：v1,v2,v3,v4,v5；v1=s,v5=t,vi∈Vi,i=2,3,4132546879111012stV1V2V3V4V5最优决策序列为路径长度最短的节点序列s,v2,v3,v4,t确定一个多级决策问题的最优决策序列算法设计与分析第四讲动态规划状态转移过程状态序列s0s1…sk

5、…sn状态序列s0x1xkxn决策序列算法设计与分析第四讲动态规划最优性原理(最优子结构性质)2)一个n级决策是最优的，则以第k(k≤n)级决策形成的状态作为初态的任何一个n-k级的子决策也必然是最优的。三种表述1)对于一个多级决策问题的最优决策来说，无论过程的初始状态和初始决策是什么,其余的决策相对于初始决策所产生的状态必然构成一个最优决策子序列。3)D(i,j)=D(i,k),D(k+1,j)算法设计与分析第四讲动态规划例：k段图问题的最优性原理说明假设：v1…vq…vk是最短路径，那么：v1…v

6、q,vq…vk也是最短路径。算法设计与分析第四讲动态规划递推方法1)递推的任务3)向后递推确定决策向量X=(x1,x2,…,xn)各分量的值2)向前递推算法设计与分析第四讲动态规划4.2多段图(multistagegraph)向前递推c(i,k)=argmin{c+c(i+1,j)}1≤i≤K-1,1≤k≤

7、Vi

8、,1≤j≤

9、Vi+1

10、向后递推c(i,k)=argmin{c(i-1,j)+c}2≤i≤K,1≤j≤

11、Vi-1

12、,1≤k≤

13、Vi

14、kjtViVi+1vi,kvi+1,jc

15、(i,k)c(i+1,j)c一、递推公式算法设计与分析第四讲动态规划二、递推算法节点编号0~n-1,s.t.,k

16、k∈Vi

17、k∈Vi+1d[n]:各节点到t最小成本路径上的后向邻接节点C[n]:各节点到汇点的最短路径，向前递推算法c[i][i]=0.c[n][n]:∈E,c[i][j]>0;p[k]:存储s到t最小成本路径上的节点编号.算法设计与分析第四讲动态规划ForwardShortestPath(floatc[][n],intk,intn){floatC[n];intd[

18、n],p[k];C[0:n-2]=MAX;C[n-1]=0;for(i=n-2;i>=0;i--)for(j=i+1;j<=n-1;j++)if((c[i][j]>0)&&(c[i][j]+C[j]

19、tc[][n],intk,intn){floatC[n];intd[n],p[k];C[0]=0;C[1:n-1]=MAX;for(i=1;i<=n-1;i++)for(j=i-1;j>=0;j--)if((c[j][i]>0)&&(C[j]+c[j][i]0;k--)p[i]=d[p[i+1]];}算法设计与分析第四讲动态规划例4.1把n个资源分配给r个项目的问题,如果把0

20、≤j≤n个资源分配给项目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)算法设计与分析第四讲动态规划4.3每对节点之间的最短路径长度一、问题描述c[n][n]是G的成本邻