【教学课件】第3章动态规划.ppt
《【教学课件】第3章动态规划.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第3章动态规划.ppt(136页珍藏版)》请在三一办公上搜索。
1、第3章 动态规划,3.1 动态规划法的基本概念3.2 动态规划法的应用专题,动态规划,动态规划(Dynamic Programming)20世纪50年代美国数学家贝尔曼(Richard Bellman)为研究最优控制问题而提出的。动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。应用:动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。,3.1 动态规划的基本概念,3.1.1 什么是动态规划例1:计算斐波那契数3.1.2 动态规划的求解方法例2:多段图的最短路径问题例3:街道问题例4:数字三角形问题3.1.3 动态规划小结3.1.4 矩阵连乘问题,3.1
2、.1 什么是动态规划,动态规划是求解包含重叠子问题的最优化方法基本思想:将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解(注意:不是简单分而治之)。,例1:计算斐波那契数,方法一:分治法long fib(int n)long p;if(n=0|n=1)return n;else p=fib(n-1)+fib(n-2);return p;,法1:分治法,计算斐波那契数的过程(n=5),冗余计算,法2:动态规划法,分析:计算f(n)是以计算它的两个重叠子问题 f(n1)和f(n2)的形式来表达的,所以,可以设计一张表填入n1个f(n)的值。动态规划法求解斐波那契数f(9)的填
3、表过程,3.1.1 什么是动态规划,动态规划法的设计思想:将待求解问题分解成若干个相互重叠的子问题,每个子问题对应决策过程的一个阶段。一般来说,子问题的重叠关系表现在对给定问题求解的递推关系(也就是动态规划函数)中。将子问题的解求解一次并填入表中,当需要再次求解此子问题时,可以通过查表获得该子问题的解而不用再次求解,从而避免了大量重复计算。,动态规划与分治法的异同点,相同点:动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题或分为若干级(阶段),然后顺序求出各个子问题。区别:动态规划法:经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。分治法:经分解
4、得到的子问题往往是互相独立的,在用分治法求解时,有些子问题被重复计算了许多次。,3.1.1 什么是动态规划,动态规划的基本要素重叠子问题性质能够分解为相互重叠的若干子问题;在用分治算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题可能被重复计算多次。动态规划算法利用此性质,对每个子问题只计算一次,然后将其结果保存起来以便高效重用。最优化子结构性质若问题的最优解所包含的子问题的解也是最优的,则称该问题具有最优子结构性质(即满足最优化原理),3.1.2 动态规划的求解方法,求解方法1.把问题分成许多个子问题(一般地每个子问题是互相关联和影响的)2.依次研究逐个问题的决策。常见
5、的处理方法:向前处理法(forward approach):向后处理法(backward approach),例2:多段图的最短路径,多段图,例2:多段图的最短路径,多段图多段图G(V,E)是一个有向图。它有如下特点:图中结点被分成 k 2个不相交的集合Vi(1 i k);其中:V1和Vk 分别只有一个结点s(源点)和t(终点)。图中的边(u,v)有如下性质:若u Vi,则v Vi+1,(1 i k-1)。多段图问题求多段图中由s(源点)到t(终点)的最小成本路径。,例2:多段图的最短路径,例如:,例2:多段图的最短路径,1.分解最优解的结构不难说明多段图问题具有最优子结构性质。2.建立递归关
6、系(1)向前处理法设c为图的代价矩阵设p(i,j)是一条从集合Vi中的结点j到终点t的最小成本路径;cost(i,j)是这条路径的成本。,例2:多段图的最短路径,显然有:,初始时,,例2:多段图的最短路径,3.计算最优值,V1 V2 V3 V4 V5,例2:多段图的最短路径,4.根据计算最优值时得到的信息,构造最优解。,例2:多段图的最短路径,当然也可以采用:向后处理法设BP(i,j)是一条从源点s到集合Vi中的结点j的最小成本路径;Bcost(i,j)是这条路径的成本。,例2:多段图的最短路径,显然有:,初始时,,例2:多段图的最短路径,V1 V2 V3 V4 V5,练习,最短路径:0358
7、9,长度为16。,应用实例,路径规划车辆卫星定位系统路径规划:基于具有拓扑结构的道路网络,在车辆驶前或行驶过程中寻找车辆从起始点到目的地的最佳行驶路线的过程,它是多段图最短路径问题。,例3:街道问题,问题描述:在一个如下图所示的正方形组成的矩形地图中中找出从左下角到右上角的最短路径,每步只能向右方或上方走。,状态转移方程(动态规划函数):,例4:数字三角形问题,数字三角形(P90)问题描述分析穷举法动态规划法,动态规划函数,3.1.3 动态规划小结,1.动态规划基本步骤找出最优解的性质,并刻划其结构特征递归地定义最优值计算最优值根据计算最优值时得到的信息,构造最优解,3.1.3 动态规划小结,
8、2.应用动态规划法要注意:阶段的划分是关键最优化原理应在子问题求解中体现,3.1.3 动态规划小结,动态规划与分治法 相同点不同点动态规划较之于穷举法的优势大大减少了计算量丰富了计算结果,矩阵连乘问题,两个矩阵相乘若A是pq矩阵,B是qr矩阵,则矩阵相乘运算共要:pqr次乘法.矩阵连乘给定n个矩阵A1,A2,An,其中Ai与Ai+1是可乘的,考察这n个矩阵的连乘积 A1 A2 An问题:如何确定最优计算顺序?,3.1.4 矩阵连乘问题,例1:设有三个矩阵A1,A2,A3,它们的维数分别是 A1 10100,A2 1005,A3 550,则:则:(1)计算(A1A2)A3)共需要:10*100*
9、5+10*5*507500 乘法(2)计算(A1(A2A3)共需要100*5*50+10*100*5075000 乘法,3.1.4 矩阵连乘问题,例2:设有四个矩阵ABCD,它们的维数分别是:,16000 1050036000 8750034500,3.1.4 矩阵连乘问题,因此:由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为:单个矩阵是完全加括号的;矩阵连乘积 A是完全加
10、括号的,则A可表示为2个完全加括号的矩阵连乘积 B和C 的乘积并加括号,即A(B C)。,矩阵连乘问题,问题提出:给定n个矩阵A1,A2,An,其中Ai与Ai+1是可乘的,考察这n个矩阵的连乘积A1 A2 An如何确定计算矩阵连乘积的计算次序(即确定矩阵的完全加括号方式),使得依此次序计算矩阵连乘积需要的数乘次数最少?,方法1:穷举法,穷举法基本思想列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。特点:计算量大,方法1:穷举法,分析对于n个矩阵的连乘积,设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题:(
11、A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下:,方法2:动态规划法,1.分析最优解的结构引入记号:将矩阵连乘积Ai Ai+1 Aj 记为Ai:j。特征:计算A1:n的最优次序所包含的计算矩阵子链 A1:k和Ak+1:n的次序也是最优的。即:矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。,2.建立递归关系计算Ai:j所需要的最少数乘次数mij,则原问题的最优值为m1n。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开,ikj,则其相应完全加括号方式为(Ai Ai+1 Ak)(Ak+1 Ak+2 Aj)则总的计算量 Ai:k的计算量 Ak+1:j
12、的计算量 Ai:kAk+1:j 的计算量。,方法2:动态规划法,2.建立递归关系可以递归地定义mij为:,这里 的维数为,方法2:动态规划法,方法2:动态规划法,3.计算最优值对于1ijn不同的有序对(i,j)对应于不同的子问题。因此,不同子问题的个数为:,4.构造最优解,一个实例,计算A1 A2 A3 A4 A5 A6的最优次序。,即:,例如:计算A1 A2 A3 A4 A5 A6的最优次序。,故:计算A1 A2 A3 A4 A5 A6的最优次序为,void MatrixChain(int*p,int n,int*m,int*s)for(int i=1;i=n;i+)mii=0;for(in
13、t r=2;r=n;r+)for(int i=1;i=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;/for k/for i,计算最优值的算法描述,构造最优解的算法描述,void Traceback(int i,int j,int*s)if(i=j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout“Multiply A”i“,”sij;cout“and A
14、”sij+1“,”j endl;,算法复杂度分析:时间复杂性算法matrixChain的主要计算量取决于算法中对r,i和k的3重循环,因此T(n)O(n3)。空间复杂性S(n)O(n2)。,方法3:递归分治求解,算法描述:(P54)int RecurMatrix(int i,int j)if(i=j)return 0;u=RecurMatrix(i,i)+RecurMatrix(i+1,j)+pi-1*pi*pj;sij=i;for(k=i+1;kj;k+)t=RecurMatrix(i,k)+RecurMatrix(k+1,j)+pi-1*pk*pj;if(tu)u=t;sij=k;/for
15、 return u;,(Ai Ai+1 Ak)(Ak+1 Ak+2 Aj),分析:,方法3:递归分治求解,小结,1.动态规划算法的基本要素最优子结构最优子结构是问题能用动态规划算法求解的前提。重叠子问题每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。(自底向上求解)通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。,小结,2.分治法自顶向下求解对重叠的子问题被反复计算多次,效率低。3.备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同(自顶向下)但备忘录方法为每个解过的子
16、问题建立了备忘录,以备需要时查看,避免了相同子问题的重复求解。,小结,例如:int LookupChain(int i,int j)if(mij 0)return mij;if(i=j)return 0;int u=LookupChain(i,i)+LookupChain(i+1,j)+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=LookupChain(i,k)+LookupChain(k+1,j)+pi-1*pk*pj;if(t u)u=t;sij=k;mij=u;return u;,3.2 动态规划法的应用专题,图问题中的动态规划法组合问题中的动
17、态规划法几何问题中的动态规划法查找问题中的动态规划法,应用专题一,图问题中的动态规划法多段图的最短路径问题每对结点间的最短路径TSP问题,每对结点间的最短路径,问题提出:G=(V,E)是一个有n个结点的有向图,C是G的成本邻接矩阵。其中C(i,i)=0,C(i,j)=(当边E)。要求:将每对结点间的最短路径值存入矩阵A:A(i,j):结点i到结点j的最短路径长度。,每对结点间的最短路径,1.问题的最优子结构性质假设i到j的最短路径有一个中间结点k,则由i到k和k到j的子路径分别是i到k和k到j的最短路径,否则i到j的路径就不具有最短路径。故:该问题具备最优子结构性质。,每对结点间的最短路径,2
18、.建立递归关系用符号Ak(i,j)表示从i到 j并且不经过比序号k还大的结点的最短路径长度,则显然i到k和k到j两条最短路径都不可能有比序号k1还大的中间结点。,3.计算最优值依次计算A1,A2,An 构造最优值An就记录了图中每对结点间的最短路径长度。,每对结点间的最短路径,例:求下图的各个结点间的最短路径长度。,每对结点间的最短路径,每对结点间的最短路径,每对结点间的最短路径,void All-paths(int n,int*cost,int*A)/cost-图的成本邻接矩阵,A-距离矩阵 for(int i=1;i=n;i+)/初始化Aij for(int j=1;j=n;j+)Aij=
19、costij;for(int k=1;k=n;k+)for(int i=1;i=n;i+)for(int j=1;j=n;j+)Aij=min(Aij,Aik+Akj);,TSP问题,问题描述:旅行商问题(Traveling Salesman Problem)问题抽象:可以用结点表示城市,城市间的交通路线用边表示,而城市间的交通线路距离可用附加于边的权表示。这样:上述问题可以归结为寻找一条权的总和为最短的哈密尔顿回路的问题。,TSP问题,分析:各个城市间的距离可以用代价矩阵来表示。,TSP问题,1.最优子结构性质设s,s1,s2,sp,s是从s出发的一条路径长度最短的简单回路,假设从s到下一个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教学课件 教学 课件 章动 规划
链接地址:https://www.31ppt.com/p-5658540.html