2022年动态规划入门.docx

《2022年动态规划入门.docx》由会员分享，可在线阅读，更多相关《2022年动态规划入门.docx（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精品学习资源动态规划思想入门陈喻 2021 年 10 月 7 日关键字：动态规划，最优子结构，记忆化搜寻引言动态规划 dynamicprogramming是运筹学的一个分支，是求解决策过程decisionprocess最优 化的数学方法 ；20世纪 50岁月初美国数学家R.E.Bellman等人在讨论多阶段决策过程 multistep decision process的优化问题时，提出了闻名的最优化原理 principle of optimality，把多阶段过程转化为一系列单阶段问题，逐个求解，创立明白决这类过程优化问题的新方法 动态规划； 1957年出版了他的名著 Dynamic Prog

2、ramming，这是该领域的第一本著作；动态规划问世以来，在经济治理、生产调度、工程技术和最优掌握等方面得到了广泛的应用；例如最短路线、库存治理、资源安排、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为便利；虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划 如线性规划、非线性规划 ，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法便利地求解；动态规划的基本思想动态规划是：将待求的问题分解成假设干个相互联系的子问题，先求解子问题， 然后从这些子问题的解得到原问题的解； 对于重复显现的子问题， 只在第一次遇到的时候对它直接

3、求解，并把答案储存起来，让以后再次遇到是直接引用答案， 不必从新求解，其实质是分治思想和解决冗余；欢迎下载精品学习资源例 1：求 AB 的最短路径图 1这是一个利用动态规划思想的经典问题， 通过直接观看图 1 我们可以枚举出20 多条路径，并可以运算出其中最短的路径长度为16欢迎下载精品学习资源用动态规划的思想来分析，我们可以把这个问题转换成下面这个模型阶段状态决策图 2阶段：依据问题的特点和需要， 将问题按时间或空间特点分解为假设干相互联系的阶段；在本例中，我们依据空间特性将问题分成了6 个阶段；状态： 各阶段的开头条件，本例中， A,B,C P这些节点都属于状态，表示从该点到B的最短路径，

4、在这里我们计做 Si，表示从第 i个节点状态到 B的最短路径决策：某阶段状态确定后，从该状态到下阶段某状态的挑选；比方 SA，它可以挑选通过 C到达B，也可以挑选通过 D到达B；状态转移方程：系统由某阶段的一个状态转变到下一阶段的另一状态称状态转移，表达转移规律的方程称状态转移方程；在本例中，我们不难推出SA=MINSC+4,SD+3,SC=MINSE+5,SF+3 SB=0，由此我们可以得出状态转移方程 i=MINSj+Vijj 为与i相邻接的节点， Vij 表示邻接欢迎下载精品学习资源节点i， j之间的距离 ；一个动态规划模型应当满意以下几个性质：最优子结构可这样阐述： 一个最优化策略具有

5、这样的性质， 不管过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必需构成最优策略； 简而言之，一个最优化策略的子策略总是最优的；例如在图2 的模型中， SA 是 A 到 B 的最短路径 最优策略 ，而它所依靠的 SC 和 SD 作为 SA 的子策略分别是 C 到 B 的最短路径和 D 到 B 的最短路径，也是最优的；因此依据最优子结构性质我们得出了上面的状态转移方程；证明：如图 2 设路线 W1=A,C,C,F,F,JW2=J,M,M,O,O,B假设路线 W1 和 W2 是 A 到 B 的最优路径，就依据最优化原理，路线 W2 必是从 J 到 B 的最优路线；用反证法证明：假设

6、有另一路径 W2 是 J 到 B 的最优路径，就 A 到 B 的路线取 W1 和 W2 比 W1 和 W2 更优，冲突；从而证明 W2 必是 J 到 B 的最优路径 W2 ；最优子结构性质是动态规划的基础， 任何问题， 假如失去了最优子结构性质的支持，就不行能用动态规划方法运算； 依据最优子结构性质导出的动态规划状态转移方程是解决一切动态规划问题的基本方法；可以看出，图 2 的模型是满意最优子结构性质的；2子问题重叠性质在我们依据状态转移方程用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新的，而且某些子问题会被重复运算多次，比方，在求SC时需要递归求出 SF的值，而在求 SD时也

7、需要递归求出 SF的值，因此整个求解过程中 SF的值会被求解两次，假如我们能把这余外的一次重复运算剔除，将可以最大程度的提高程序执行效率；动态规划正是利用了这种子问题的重叠性质， 对每个子问题只运算一次， 然后将其结果储存在一个表格中， 当再次需要运算已经运算过的子问题时， 只是在表格中简洁的查询一下结果， 从而获得较高的解题效率， 这个方法就是我们常说的 记忆化搜寻 ；因此， 假如我们把第欢迎下载精品学习资源一次求解出的 SF的值用一种数据结构储存下来，下次再用到SF时，我们直接去查，这样能使程序的时间和空间效率将会大大提高；下面通过对详细实例的分析， 帮忙大家领悟动态规划的这两个性质和动态

8、规划的算法设计思想例：导弹拦截某国为了防备敌国的导弹突击 , 进展出一种导弹拦截系统 . 但是这种导弹拦截系统有一个缺陷 : 虽然它的第一发炮弹能够到达任意的高度, 但是以后每一发炮弹都不能高于前一发的高度 .某天, 雷达捕获到敌国的导弹来袭 .由于该系统仍在试用阶段, 所以只有一套系统 , 因此有可能不能拦截全部的导弹.输入导弹依次飞来的高度 雷达给出的高度数据是不大于30000的正整数 , 运算这套系统最多能拦截多少导弹 ,并依次输出被拦截的导弹飞来时候的高度.样例:INPUT389 207 155 300 299 170 158 65OUTPUT6 最多能拦截的导弹数 389 300 2

9、99 170 158 65分析:由于只有一套导弹拦截系统 ,并且这套系统除了第一发炮弹能到达任意高度外,以后的每一发炮弹都不能高于前一发炮弹的高度; 所以, 被拦截的导弹应当按飞来的高度组成一个非递增序列 .题目要求我们运算这套系统最多能拦截的导弹数,并依次输出被拦截导弹的高度 , 实际上就是要求我们在导弹依次飞来的高度序列中查找一个最长非递增子序列 .解决思路：设X=x 1 ,x 2 ,x n 为依次飞来的导弹序列 , Y=y 1 ,y2 , ,y k 为问题的最优解 即 X 的最长非递增子序列 , s为问题的状态 表示导弹拦截系统当前发送炮弹能够到达的最大高度, 初值为 s= 第一发炮弹能

10、够到达任意的高度 . 假如 y 1 =x 1 ,即飞来的第一枚导弹被胜利拦截. 那么,依据题意 每一发炮弹都不能高于前一发的高度 , 问题的状态将由 s= 变成 sx 1 x 1为第一枚导弹的高度 ; 在当前状态下 ,序列 Y 1 =y 2 ,y k 也应当是序列X 1 =x 2 ,x n 的最长非递增子序列 用反证法很简洁证 明. 也就是说 , 在当前状态 sx 1下, 问题的最优解 Y 所包含的子问题 序列X 1 的解 序列 Y 1 也是最优的 .这就是拦截导弹问题的最优子结构性质 .欢迎下载精品学习资源依据最优子结构性质推出状态转移方程：设Di为第 i 枚导弹被拦截之后 ,这套系统最多仍

11、能拦截的导弹数 包含被拦截的第 i 枚. 我们可以设想 , 当系统拦截了第 k 枚导弹 x k , 而 x k又是序列 X=xk ,xn 中的最小值 , 即第 k 枚导弹之后飞来的导弹高度都比它高 , 就有 Dk=1 ;当系统拦截了最终一枚导弹 x n , 那么,系统最多也只能拦截这一枚导弹了 , 即 Dn=1 ;其它情形下 , 也应当有 Di 1 . 依据以上分析 , 可归纳出问题的动态规划递归方程为 :欢迎下载精品学习资源Di=1i=n或者 xi=minxi XnMaxDj+1 ji且 j=n且 xj=xi欢迎下载精品学习资源假设系统最多能拦截的导弹数为dmax 即问题的最优值 , 就dm

12、ax i为被系统拦截的第一枚导弹的次序号 所以,要运算问题的最优值 dmax , 需要分别运算出 D1 , D2 , Dn 的值,然后将它们进行比较 , 找出其中的最大值 .即： dmax=maxDi1=i且i=n分析子问题重叠，解决冗余依据上面分析出来的递归方程 , 我们完全可以设计一个递归函数, 采纳自顶向下的方法运算 Di的值. 然后, 对 i 从 1 到 n分别调用这个递归函数 ,就可以运算出 D1 , D2 , Dn . 程序如下：int Dint iint j,max=0; ifi=n|minx,i,n=xi/minx,i,n返回数组 x 在下标 i n 之间的最小值return

13、1; else欢迎下载精品学习资源forj=i+1;j=n;j+ ifxjmax max=Dj+1;return max;从这个程序的递归模型中可以看出，会有大量的子问题被重复运算 . 比方在调用递归函数运算 D1 的时候, 可能需要先运算 D5 的值; 之后在分别调用递归函数运算 D2 , D3 , D4 的时候,都有可能需要先运算 D5 的值.如此一来,在整个问题的求解过程中 , D5 可能会被重复运算很多次 ,从而造成了冗余,降低了程序的效率 .其实,通过以上分析 , 我们已经知道 : Dn=1 . 假如将 n 作为阶段对问题进行划分,依据问题的动态规划递归方程 , 我们可以采纳自底向上

14、的方法依次运算出Dn-1 , Dn- 2 , D1的值. 这样,每个 Di 的值只运算一次 ,并在运算的同时把运算结果储存下来 ,程序如下：void Dint i,j;for i=1;i=1;i- forj=i+1;j=n;j+if xjdmaxdmax=di; xh=i;欢迎下载精品学习资源由此我们出了最大拦截数的第一枚导弹的次序号xh，即 dxh 为问题的解从而防止了有些子问题被重复运算的情形发生,提高了程序的效率 .在实际应用中， 很多问题的阶段划分并不明显， 这时假如刻意地划分阶段反而麻烦；一般来说， 只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解 即满

15、意最优子化原理 ，就可以考虑用动态规划解决， 也就是分治算法的思想；例 2：传球嬉戏 NOIP2021 普及组第三题【问题描述】上体育课的时候，小蛮的老师常常带着同学们一起做嬉戏；这次，老师带着同学们一起做传球嬉戏；嬉戏规章是这样的： n 个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开头传球， 每个同学可以把球传给自己左右的两个同学中的一个左右任意，当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目；聪慧的小蛮提出一个好玩的问题： 有多少种不同的传球方法可以使得从小蛮手里开头传的球，传了m 次以后，又回到小蛮手里；两种传球的方法被视作

16、不同的方法， 当且仅当这两种方法中， 接到球的同学按接球次序组成的序列是不同的；比方有 3 个同学 1 号、2 号、3 号，并假设小蛮为 1 号，球传了 3 次回到小蛮手里的方式有 1-2-3-1 和 1-3-2-1 ，共 2 种；【输入】输入文件 ball.in 共一行，有两个用空格隔开的整数n，m3=n=30 ，1=m=30 ；【输出】输出文件 ball.out 共一行，有一个整数，表示符合题意的方法数；【输入输出样例】欢迎下载精品学习资源3 3ball.out 2【限制】40% 的数据满意： 3=n=30 ， 1=m=20100% 的数据满意： 3=n=30 ，1=m=30解决思路：给

17、n 个同学从 1n 编号，设状态 Fp,t 表示传了 t 次球后，球在 p 手中，在剩下的 m-t 次传球中共有多少种方案到达 1，由于在问题的求解中，球是从 1 号开头传，并最终回到 1 号，明显我们所求的目标状态就是是F1,0 ；由于球只能传递给左右的两个同学， 也只能通过左右的两个同学传递给自己， 如以下图：F1,0向左传向右传F2,1Fn,1由此，我们分析出 F1,0 的解只与 F1,1 和 Fn,1 有关，而 F1,1 和 Fn,1 也是最优问题解，因此，该问题符合最优子结构性质；依据最优性原理我们可以得到以下状态转移方程：1t=m， p=1Fp,t=0t=m， p.=1FRp,t+

18、1+FLp,t+1 1=p=n，0=tmRp： p 右边同学的编号Lp： p 左边同学的编号欢迎下载精品学习资源通过以上分析， 依据状态转移方程， 运用记忆化搜寻策略， 采纳自顶向下的过程可递归求出 F1,0 ，程序如下：#include #include#define maxn 31/最大人数，编号从1 n#define maxm 30/最大传球次数long fmaxnmaxm;/表示传了 T 次球以后球在P 号手里，包括在剩下的M-T 次传球中有多少种方法走到 1long m,n;void findlong p,long tift=m/ 传了 M 次球了ifp=1/ 传到了 1 fpt=1

19、;else/ 没传到 1fpt=0; return;iffpt.=-1 return;/假如这个状态搜到过了，没必要再搜fpt=0;/ 标记该状态被搜过了findp%n+1,t+1;/搜把球传给 P 右边的同学的状态fpt+=fp%n+1t+1; int p1=p-1; ifp1=0p1=n;findp1,t+1;/搜把球传给 P 左边的同学的状态fpt+=fp1t+1;mainint i,j;/ 一开头全部状态都没到过fori=0;imaxn;i+forj=0;jmaxm;j+ fij=-1;scanf%d%d,&n,&m; find1,0;欢迎下载精品学习资源printf%ld,f10;代

20、入数据测算 例： input ：33 数据模型如下：F1,0=2F2,1=1F3,1=1F1,2=0F3,2=1F1,2=0F2,2=1F3,3=0F2,3=0F1,3=1F2,3=0F1,3=1F3,3=0：可以从记忆数组中直接猎取；：需搜寻记忆的状态；由于采纳了记忆化搜寻， 处于不同位置的相同状态不会被多次搜寻，因此可以在Om n的时间复杂度内完成任务，同样防止了子问题被重复运算的情形；由此可知， 动态规划法与分治法和贪心法类似， 它们都是将问题实例归纳为更小的、相像的子问题，并通过求解子问题产生一个全局最优解；贪心法：当前挑选可能要依靠已经作出的全部挑选， 但不依靠于有待于做出的挑选和子

21、问题；因此贪心法自顶向下，一步一步地作出贪心挑选；分治法：各个子问题是独立的即不包含公共的子子问题 ，因此一旦递归地求出各子问题的解后， 便可自下而上地将子问题的解合并成问题的解； 但不足的是， 假如各子问题是不独立的， 就分治法要做很多不必要的工作， 重复地解公共的子问题；欢迎下载精品学习资源动态规划： 利用分治思想把问题划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解；动态规划答应这些子问题不独立，亦即各子问题可包含公共的子子问题 也答应其通过自身子问题的解作出挑选，该方法对每一个子问题只解一次， 并将结果储存起来， 防止每次遇到时都要重复运算， 从而解决解决冗余因此，动态规划法所针对的问题有一个显著的特点， 即它所对应的子问题树中的子问题出现大量的重复； 动态规划法的关键就在于， 对于重复显现的子问题， 只在第一次遇到时加以求解，并把答案储存起来，让以后再遇到时直接引用，不必重新求解；总结：任何思想方法都有肯定的局限性， 超出了特定条件， 它就失去了作用； 同样，动态规划也并不是万能的；适用动态规划的问题必需满意最优化子结构性质；特点：1. 以长远利益为目标的一些列决策，一般用来求解最优的问题解2. 符合最优化原理，可归结为一个递推式3. 也成为多阶段规划，特点表达在多阶段性欢迎下载