动态规划(普及组-)课件

动态规划（普及组）绍兴柯桥中学吴建锋动态规划（普及组）绍兴柯桥中学认识动态规划动态规划在运筹学等领域都得到很大的运用，它是求解最优化分阶段决策问题的一种数学方法，大约产生于50年代。1951年美国数学家Bellman等人根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新的方法―――动态规划。认识动态规划动态规划在运筹学等领域都得到很大的运用，它是求解多阶段决策过程123n多阶段决策过程123n“动态”的内涵在分阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的改变（转移），一个决策序列就是在变化的状态中产生出来的，所以有“动态”的含义。因此，把处理它的方法称为动态规划方法。“动态”的内涵在分阶段决策问题中，各个阶段采取的决策，一般来问题1：求最短路径长度假如有下图所示的交通示意图，有向边上的数值表示边的长度，求A到D的最短路径的长度。ABCD13192815问题1：求最短路径长度假如有下图所示的交通示意图，有向边上的解法1：从初始阶段出发的顺推求解1、用f[i]表示A到结点i的最短距离2、我们可以求得f[A]=13，f[B]＝19（第一阶段）3、第二阶段求解过程如下：f[B]+28=41{f[D]的候选最优解}f[C]+15=34{f[D]的候选最优解}4、保存较优解：f[D]=min{f[B]+28,f[C]+15}解法1：从初始阶段出发的顺推求解1、用f[i]表示A到结点i解法2：目标阶段出发的逆推求解1、如果用f[i]表示编号为i的结点到终点d的最短距离，那么动态规划分阶段求解的过程如下所示：（1）f[D]:=0{初始化}（2）f[B]:=28+f[D];f[C]:=15+f[D]{第一阶段求解}（3）f[A]:=min{13+f[B],19+f[C]}{状态转移方程的体现，第二阶段求解}解法2：目标阶段出发的逆推求解1、如果用f[i]表示编号为i什么叫状态转移方程对于当前阶段的某个状态，必定有有上个阶段的子问题的某一批状态通过对应的决策变换而来，这些子问题的一批状态通过对应的决策应用，就导致了状态转移，新的状态就是当前阶段的某个状态。由于这个新状态的子状态可能不止一个，所以决策后的对应局部解也可能不止一个，在这些解中取一个最优解，就是当前阶段当前状态的最优解，这个求最优解的过程可用一个表达式来描述，这个表达式就是状态转移方程。什么叫状态转移方程对于当前阶段的某个状态，必定有有上个阶段的状态转移方程应用举例在下列交通路线中，求节点1到节点10的最短路径的长度。14326598710132191517324527111381916251120状态转移方程应用举例在下列交通路线中，求节点1到节点10的分阶段决策的手工计算第一阶段：f[2]=f[1]+13=13;f[3]=f[1]+21=21;f[4]=f[1]+9=9第二阶段：f[5]=min{f[2]+15,f[3]+17,f[4]+24}=28;f[6]=min{f[2]+3,f[3]+5,f[4]+27}=16第三阶段：f[7]=min{f[5]+11,f[6]+8}=24;f[8]=min{f[5]+13,f[6]+19}=35;f[9]=min{f[6]+16}=32

分阶段决策的手工计算第一阶段：目标阶段求解第四阶段：f[10]=min{f[7]+25,f[8]+11,f[9]+20}=46目标阶段求解第四阶段：具体化的状态转移方程1、f[5]=min{f[j]+x,……}，f[6]=min{f[k]+y,……}2、f[j]+x中的f[j]就是上阶段子问题各状态的最优解；而x则是某个子状态转移到当前状态产生的决策效应（或者是代价）具体化的状态转移方程1、f[5]=min{f[j]+x,……一般化的状态转移方程实际编程实现时，状态转移方程往往是一个通用计算式，在这个通用计算式中往往会包含各种子状态、子状态对应子问题的最优解、决策等参数。一般化的状态转移方程实际编程实现时，状态转移方程往往是一个通动态规划的算法设计如果用i表示当前需求解的阶段号（有时为了描述的方便，i也可表示当前阶段的前一个阶段），j表示当前阶段各个状态（或者说是阶段的各个节点编号），k表示前一阶段各个子状态能选择的策略，用f[I,j]表示起点1到第i阶段编号为j的结点（也可理解为状态）的最短距离，那么上面问题用动态规划求解的大致程序结构如下：动态规划的算法设计如果用i表示当前需求解的阶段号（有时为了描穷举所有的阶段（fori:=1to4do）穷举当前阶段i所有可能的状态j穷举j状态所有对应的子状态的所有可选择的策略kF[I,j]:=min{f[i-1,j1]+x[j1,k]|j1表示状态j所有可能的子状态}穷举所有的阶段（fori:=1to4do）程序代码实现输入数据：23405607890100013219maxintmaxintmaxintmaxintmaxintmaxintmaxint0maxintmaxint153maxintmaxintmaxintmaxintmaxintmaxint0maxint175maxintmaxintmaxintmaxintmaxintmaxintmaxint02427maxintmaxintmaxintmaxint……程序代码实现输入数据：数据结构A[I,j]=k表示第i阶段的第j个决策点（后继节点）是k；D[I,j]=k表示i和j节点之间的直接联边长度是k，如果是maxint则表示没有直接联边。如果是0则表示节点本身。数据结构A[I,j]=k表示第i阶段的第j个决策点（后继节点程序框架fori:=1to4dobeginj:=1;repeatj2:=a[I,j];k:=1;repeatj1:=a[i-1,k];ifd[j1,j2]<>maxintthenf[I,j2]:=min{f[I,j2],f[i-1,j1]+d[j1,j2]}inc(k);untila[i-1,k]=0;inc(j);untila[I,j]=0;end;程序框架fori:=1to4do一些关键的要素1、阶段每个阶段的处理是相同的。2、状态每个抽象化的节点所共有的特性值。3、决策所选择的处理。一些关键的要素1、阶段分析动态规划1、何时可考虑动态规划2、阶段、状态、决策如何提炼3、如何抽象出状态转移方程分析动态规划1、何时可考虑动态规划问题2：数字三角形下图所示为一个数字三角形，其中三角形中的数值为不超过100的整数，现规定从最顶层往下走到底层，每一步可沿左斜线向下或右斜线向下走。738810274445265

假设三角形行数<=100，编程计算从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字之和最大，输出最大值。问题2：数字三角形下图所示为一个数字三角形，其中三角形中的数输入和输出trigon.in738810274445265trigon.out30输入和输出trigon.in为什么可用动态规划738810274445265为什么可用动态规划算法设计1、阶段就是行号2、状态就是每行上的某个数字（位置号表示）3、决策就是向右（还是向左）的走法。算法设计1、阶段就是行号状态转移方程若用f[I,j]表示起点到i阶段第j个数字的最优解，用j1表示j对应的子状态，x[j1,k]表示j1子状态变换到j状态中的第k个决策所产生的决策效应，则可写出状态转移方程如下：f[I,j]=max{f[i-1,j1]+x[j1,k]|j1和k最多取二个值}状态转移方程若用f[I,j]表示起点到i阶段第j个数字的最优结合数据结构调整方程根据输入数据特点，考虑用a[I,j]保存第i行第j个位置上的数字，那么前面方程中j1可取的值为j-1和j，所以状态转移方程可细化为：f[I,j]=max{f[i-1,j]+a[I,j],f[i-1,j+1]+a[I,j]}其中1<=i<=n，1<=j<=i，初始化时f[1,1]=7。结合数据结构调整方程根据输入数据特点，考虑用a[I,j]保存写出核心程序段fillchar(f,sizeof(f),0);f[1,1]:=a[1,1];fori:=2tondo{枚举阶段}forj:=1toIdo{枚举状态}fork:=j-1tojdo{枚举决策}iff[I,j]<f[i-1,k]+a[I,j]thenf[I,j]:=f[i-1,k]+a[I,j];写出核心程序段fillchar(f,sizeof(f),0)这样最后求得的f[n,n]是否是本问题的最优解？动态规划(普及组-)课件问题3：彩石运输阿强是一个汽车运输工，他正在给一项装饰工程运输所需的彩色石头。这些石头的颜色各异，价格也各不相同。有一天阿强突发奇想，他想在一堆彩石中有选择地把彩石装上他的卡车，使得卡车上装载的石头总价值是所有装载方案中最大的。现在有一堆彩石堆放在阿强面前，他知道任何两块石头的颜色都是不同的，但两块颜色不同的石头的重量和价格可能相同。阿强的卡车总共可装载的重量是W，而且他知道总的彩石的块数，请你帮助阿强确定一个方案，满足阿强的奇想。输入文件stone.in的第一行是二个整数，依次表示卡车的载重量W和总的彩石块数n，下面共有n行，每行包含二个用空格分隔的整数，依次表示某种颜色彩石的重量和价值。输出文件stone.out只包含一行一个整数，表示卡车最终装载彩石的最大总价值。问题3：彩石运输阿强是一个汽车运输工，他正在给一项装饰工程运输入输出stone.in305205010301544514413stone.out88输入输出stone.in问题分析1、有些选手会陷入二种错误的贪心算法中2、为什么可用动态规划3、3个要素的分析（1）阶段（2）状态（3）决策问题分析1、有些选手会陷入二种错误的贪心算法中提炼出状态转移方程用w[i]保存第i种彩石的重量，用p[i]表示它的价值，用j表示状态，则状态转移方程如下：f[I,j]=max{f[i-1,j-w[i]]+p[i],f[i-1,j]}提炼出状态转移方程用w[i]保存第i种彩石的重量，用p[i]核心程序代码fillchar(f,sizeof(f),0);fori:=1tondoforj:=1towdobeginf[I,j]:=f[i-1,j];if(w[i]<=w)and(f[I,j]<f[i-1,j-w[i]]+p[i])thenf[I,j]:=f[i-1,j-w[i]]+p[i];end;write(f[n,w]);核心程序代码fillchar(f,sizeof(f),0);问题4：joy的工具箱Joy是一位非常出色的汽车维修工，而且他的创业能力也很强，这不，最近他成立了自己的汽车维修110公司，一旦汽车在半途抛锚，只要一个电话，joy就会立刻带着他的工具箱赶到事故地点，为驾驶员朋友维修汽车，由于抢修及时以及维修技术高，汽车维修110公司的生意越来越红火。但joy是一个追求无止境的人，在生意越做越大的同时，他又动开了新脑筋。他发现无论维修工具箱买得如何大，肯定不能把他公司里所有的维修工具装进去，100％的故障排除率不仅需要精湛的维修技术，如何选择并把最为合适的维修工具装入工具箱，并把工具箱带到故障现场，也是一个非常重要的技巧。由于工具众多，joy无法根据驾驶员报告的故障现象确定最为合适的一些工具，作为朋友的你决定通过程序来帮助joy选择最为合适的工具转入到工具箱中。

问题4：joy的工具箱Joy是一位非常出色的汽车维修工，而且当然，joy会事先告诉你一些必要的信息。比如，他的每个工具都是不同的，工具箱的总体积，joy还会告诉你他根据故障特点给每个工具合适程度的效率分数，你的程序必须能确定哪些工具被装入工具箱，并输出总的最大效率分。当然，joy会事先告诉你一些必要的信息。比如，他的每个工具都输入文件joy.in第一行包含二个整数v和n，分别表示工具箱总体积和所有可供选择的工具的数量。下面共有n行，每行有二个用空格分隔的整数，依次分别表示每个工具的体积大小和joy给定的效率分。输出文件joy.out包含一个整数，表示在工具箱有限的空间内，所装入的所有工具的效率分数的最大值。输入文件joy.in第一行包含二个整数v和n，分别表示工具箱输入和输出joy.in23511209191015714815joy.out39输入和输出joy.in关键要素分析1、阶段2、状态3、决策关键要素分析1、阶段分析状态转移方程F[I,j]表示前i个工具选择部分装入占用容量为j的工具箱中的最大效率分：f[i,j]:=max{f[i-1,j-v1[i]]+p[i]|}分析状态转移方程F[I,j]表示前i个工具选择部分装入占用容核心程序段fillchar(f,sizeof(f),0);fori:=1tondoforj:=1tovdobeginf[i,j]:=f[i-1,j];if(v1[i]<=j)and(f[i,j]<f[i-1,j-v1[i]]+p[i])thenf[i,j]:=f[i-1,j-v1[i]]+p[i];end;write(f[n,v]);核心程序段fillchar(f,sizeof(f),0);动态规划的应用（问题5）导弹拦截。某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹？如果要拦截所有导弹最少要配备多少套这种导弹拦截系统？动态规划的应用（问题5）导弹拦截。某国为了防御敌国的导弹袭击输入和输出missile.in38920715530029917015865

missile.out6（最多能拦截的导弹数）

2（要拦截所有导弹最少要配备的系统数）输入和输出missile.in顺推求解1、用f[i]表示从第1枚导弹到第i枚导弹这个子问题的最优解（包含这枚导弹的决策序列），a[j]表示第j枚导弹的高度。2、开始时所有的f[i]都初始化为13、i从2开始直到n进行顺推计算所有的f[i]4、最后输出最大的f[i]顺推求解1、用f[i]表示从第1枚导弹到第i枚导弹这个子问题某个阶段i的f[i]求解1、f[i]的子问题是哪些？2、f[i]子问题的最优解保存在哪里？3、如何根据子问题的最优解推算父问题的最优解？某个阶段i的f[i]求解1、f[i]的子问题是哪些？状态转移方程F[i]=max{f[j]+1|必须满足的是所有的a[j]都必须不小于a[i]}状态转移方程F[i]=max{f[j]+1|必须满足的是核心程序段fillchar(f,sizeof(f),1);best:=1;fori:=2tondobeginforj:=1toi-1doif(a[j]>=a[i])and(f[j]+1>f[i])thenf[i]:=f[j]+1;ifbest<f[i]thenbest:=f[i];end;write(best);核心程序段fillchar(f,sizeof(f),1);逆推求解如何进行？逆推求解问题6：乘积最大在一次数学智力竞赛中，主持人给所有参加活动的选手出了一道题目：设有一个长度为N的数字串，要求选手使用M个乘号将它分成M＋1部分，求出一种分法，使得这M+1个部分的乘积最大。同时，为了帮助选手能够理解题意，主持人还举了如下一个例子：有一个数字串：312，当N=3,M=1时有二种分法：（1）3×12＝36；（2）31×2＝62

这时，符合题意要求的结果是：31×2＝62。现在要求设计一个程序，以求得正确的答案。输入文件product.in第一行包含二个整数，分别表示N，M（2<=N<=10，1<=M<=5），第二行是一个长度为N的数字串。输出文件product.out包含一行一个自然数，表示求得的最大乘积。问题6：乘积最大在一次数学智力竞赛中，主持人给所有参加活动的输入和输出product.in421231product.out62输入和输出product.in算法分析1、本来用搜索也可2、n，m扩大时，必须用动态规划3、用f[I,j]表示在前i个数字中插入j个乘号可以获得的最大值，那么f[n,m]就是问题的最优解。算法分析1、本来用搜索也可特殊到一般抽象出转移方程1、显然f[I,j]这个最优解肯定是在下列情形中产生的：f[j,j-1]*Aj+1…Aif[j+1,j-1]*Aj+2…Ai……f[i-1,j-1]*Ai特殊到一般抽象出转移方程1、显然f[I,j]这个最优解肯定是2、提炼出初步的转移方程：f[I,j]=max{f[i1,j-1]*(a[i1+1]…a[i])|j<=i1<=i-1}3、其中的(a[i1+1]…a[i])表示第i1+1位到第i位数字串所组成的整数。2、提炼出初步的转移方程：勾画出初步的代码Fori:=1tondoForj:=0tomdoIfj<=i-1thenFori1:=jtoi-1doIff[I,j]<f[i1,j-1]*num(a[i1+1]…a[i]);*开始时所有的f[I,j]初始化为0勾画出初步的代码Fori:=1tondo思考1、有没有发现算法中的漏洞？2、分析边界、确定递推初始值中完善算法思考1、有没有发现算法中的漏洞？完善后的算法所有的f[I,j]初始化为0；fori:=1ton-mdof[I,0]:=num(a[1]…a[i]);Fori:=2tondoForj:=1tomdoIfj<=i-1thenFori1:=jtoi-1doIff[I,j]<f[i1,j-1]*num(a[i1+1]…a[i]);完善后的算法所有的f[I,j]初始化为0；注意的细节实际编程时还须使用高精度算法，由于这里着重介绍动态规划，故本过程省略。注意的细节问题7：校庆100周年在柯中建校100周年之际，学校决定举办校庆活动，发出校庆通告和邀请后，学校收到了k多的祝贺条幅，在把这些条幅挂起来的时候，学校负责人要考虑到祝贺单位和个人的知名度和发送祝贺的先后顺序，觉得有必要统筹地安排位置来挂这些条幅。在柯中校门口的正面，有一座气势雄伟的综合楼，前面有n（1<=k<=n<=100）多的位置可以用来挂条幅，如何把这k条条幅挂到这n个位置上使之总体效果最大呢？学校负责人是这样考虑的：首先给所有条幅按照送来的顺序从1开始编号，然后给综合楼可挂条幅的位置也从1开始编号，无论怎么考虑最大效果，编号小的条幅必须挂在编号大的条幅的前面（即所在位置的编号较小）；但考虑到送条幅单位或个人知名度的问题，负责人又给每个条幅挂在每个位置上的效果打了分。最终希望挂条幅的效果分到达最大。问题7：校庆100周年在柯中建校100周年之际，学校决定举办输入文件aniversary.in第一行包含二个空格分隔的整数k和n，分别表示总条幅数量和总的可挂条幅的数量。下面一共有k行，每行有n个空格分隔的整数，输入文件第i+1行第j列的整数表示编号为i的条幅挂在编号为j的位置上的效果分（在－50到50之间）。输出文件aniversary.out包含一行一个整数，表示可能获得的最大的效果分。输入文件aniversary.in第一行包含二个空格分隔的整输入和输出aniversary.in35723-5-2416521-41023-215-4-2020aniversary.out53输入和输出aniversary.in三要素分析1、横幅作为阶段I2、前i个横幅放置所占的前j个位置作为状态3、决策就是第i个横幅放置在前j个位置的哪个位置上三要素分析1、横幅作为阶段I状态转移方程用ans[I,j]表示前i个横幅放入前j个位置，并且第i个横幅放置于第j个位置上的最优解。Ans[I,j]=max{ans[i-1,t]+a[I,j]|i<=j<=n-(k-i),i-1<=t<=j-1}状态转移方程用ans[