《动态规划算法教学PPT.ppt》由会员分享，可在线阅读，更多相关《动态规划算法教学PPT.ppt（21页珍藏版）》请在三一办公上搜索。
1、第八讲 动态规划算法Dynamic Programming,主要内容：什么是动态规划?它能解决哪些问题?解决的步骤又是什么样的?,-递推求解的扩充,2023/3/1,2,先回顾一下Fibnacci,递推求解：如Fibnacci：fn=fn-1+fn-2。或者增强型的fibnacci数列：每一项都是前面若干项的一个线性组合。如果夸张一点，会怎样？,例：最短路径问题,为了找到由A到E的最短路线，可以将该问题分成A-B-C-D-E 4各阶段，在每个阶段都需要作出决策，即在A点需要决策下一步到B1还是B2或B3；同样，若到达第二阶段某个状态，比如B1,需要决定走向C1还是C2；依次类推，可以看出：各个
2、阶段的决策不同，由A到E的路线就不同，当从某个阶段的某个状态发出一个决策，则这个决策不仅影响到下一各阶段的距离，而且直接影响后门各个阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策，使这些决策序列所决定的一条线路对应的线路最短。,动态规划（dynamic programming）作为一种多阶段决策优化过程的通用方法，它是在20世纪50年代由一位卓越的美国数学家Richard Bellman所发明的。他在研究多阶段决策过程(multistep decision process)的优化问题时，提出了把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优
3、化问题的新方法动态规划。规划（programming）的含义意味着一系列的决策，而动态（dynammic）的含义则传递着这样一种思想，就是所作的决策可能依赖于当前状态，而与此前所作的决策无关。,应用：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。如最短路线、库存管理、资源分配、设备更新、装载等问题，用动态规划方法比用其它方法求解更为方便。分类：动态规划：主要用于求解以时间划分阶段的动态过程的优化问题 静态规划：与时间无关的规划(如线性规划)可以人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划必须：具体问题具体分析处理 一题
4、一解,动态规划的应用,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,算法的条件,求fn和fn-1的时，都使用到了fn-2.,2023/3/1,7,算法框架：1）用一个集合（数组）记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。2）下次在使用某个子问题的时候，首先到集合中查看，如果已经存在就直接使用就可以了。,动态规划的算法框架,2023/3/1,8,Fn=Fn-1+Fn-2 特点：子问题不是独立的 数
5、量：不同的子问题的个数是线性的。步骤：用一个集合F=F1,F2,Fn记录所有已解决的子问题的答案，依次根据最后两项的状态将后继状态填入表中即可。Fi表示第i时间片的序列值。第1和第2时间序列是1，1,动态规划的例子：Fibnacci,算法：1）初始态设集合F=f1=1,f2=1;2)规划i=33）当前状态=前两个时间片状态的和Fi=Fi-1+Fi-2。4）下一时间太i=i+1,如果i=n转2,否则结束。,值：F1 f2 f3 f4 f5 fi fn时间片：1 2 3 4 5 I n,例：最短路径问题,S1=E=0S2=E=0,d1=7,d2=8,d3=6S3=E=0,d1=7,d2=8,d3=
6、6,c1=10,c2=13,c3=15S4=E=0,d1=7,d2=8,d3=6,c1=10,c2=13,c3=15,b1=16,b2=13,b3=19S4=E=0,d1=7,d2=8,d3=6,c1=10,c2=13,c3=15,b1=16,b2=13,b3=19,a=18最短路径：A B2 C1 D2 E,XE=minXY+YE|Y是X的后继,作业1：求A到D的最短路径,分别标记出每个结点到D点的最短路径,再一例：最短路径,2023/3/1,12,（1）【理解题目】找出最优解的性质，并刻画其结构特征。（2）【状态之间的关系】递归地定义最优值。（3）【规划的步骤和方式】以自底向上的方式计算出
7、最优值。理论上自底向上，形式上可有所变化。（4）【规划的详细过程再现】根据计算最优值时得到的信息，构造一个最优解。一般需要一个辅助的数组，保存状态之间的变迁线路。说明：其中（1）（3）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省去。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。,动态规划的基本步骤（完整）（选）,2023/3/1,13,数塔问题,有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左下走或是向右下走，一直走到底层，要求找出一条路径，
8、使路径上的值最大。,2023/3/1,14,【规划】每个结点的值是向左下或右下的小者。即总是左下角和右下角的状态确定当前状态【初始状态】最下方为初始状态 结论：自顶向下的分析，自底向上的计算。,考虑一下：,从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。,2023/3/1,15,数塔问题,
9、2023/3/1,16,数塔问题,912 1510 6 8 2 18 9 5 19 7 10 4 16,5950 4938 34 2921 28 19 2119 7 10 4 16,5950 4938 34 2921 28 19 2119 7 10 4 16,手工做法,计算机做法,作业2：求定点到底层的值最大的路径及值,分别标记出每个结点到底层结点的所有路径的最大和,2023/3/1,18,砝码称重,设有1g、2g、5g、10g、50g的砝码各2枚用他们能称出的重量的种类。算法步骤如下：T1开始状态：0T2 放入第一个1g 0+1=0，1T3 放入第二个1g 0，1+1，2=0，1，2T4 放
10、入第一个2g 0，1，2+2，3，4=0，1，2，3，4T5 放入第二个2g 0，1，2，3，4+2，3，4，5，6=0，1，2，3，4，5，6T6 放入第一个5g。,有N中砝码，每种砝码分别由Ai个。问它们能称量的重量的种类。如：1g的2个，可以称量的种类是1g和2g。,2023/3/1,19,滑雪-,滑雪是个很有趣的室外体育项目，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。如果能知道一个区域中最长底滑坡，就好了。区域由一个5*5二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 14 5 16 17
11、 18 19 6 2 24 25 20 7 14 23 22 21 8 13 12 11 18 9求最长的滑坡。算法：1）如果谷底设为1，否则2）从比自己小的周围（上下左右）选择最大的长度+1.3）重复2，直到所有格式都有数据。4）选取最大那个，就是最长滑坡的最高点,作业三：求这个区域的最长滑坡。1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9,2023/3/1,20,最大子段和：数列一段的和,Mi 以i为结尾子段的最大和 状态（子问题）：多少个？能否由其他状态推出Mi=Mi-10?Ni+Mi-1:Ni,最大的Mi，就是最大子段和了。,作业4：求下面数列的最大字段和。-2,11,-4,13,-5,-2,
