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

1、动态规划（普及组）绍兴柯桥中学吴建锋认识动态规划n动态规划在运筹学等领域都得到很大的运用，它是求解最优化分阶段决策问题的一种数学方法，大约产生于50年代。1951年美国数学家Bellman等人根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新的方法动态规划。多阶段决策过程123n“动态”的内涵n在分阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的改变（转移），一个决策序列就是在变化的状态中产生出来的

2、，所以有“动态”的含义。因此，把处理它的方法称为动态规划方法。问题1：求最短路径长度n假如有下图所示的交通示意图，有向边上的数值表示边的长度，求A到D的最短路径的长度。ABCD13192815解法1：从初始阶段出发的顺推求解n1、用fi表示A到结点i的最短距离 n2、我们可以求得fA=13，fB19（第一阶段）n3、第二阶段求解过程如下：nfB+28=41 fD的候选最优解nfC+15=34 fD的候选最优解 n4、保存较优解：fD=minfB+28,fC+15 解法2：目标阶段出发的逆推求解n1、如果用fi表示编号为i的结点到终点d的最短距离，那么动态规划分阶段求解的过程如下所示：n（1）f

3、D:=0 初始化n（2）fB:=28+fD;fC:=15+fD 第一阶段求解n（3）fA:=min13+fB,19+fC 状态转移方程的体现，第二阶段求解什么叫状态转移方程n对于当前阶段的某个状态，必定有有上个阶段的子问题的某一批状态通过对应的决策变换而来，这些子问题的一批状态通过对应的决策应用，就导致了状态转移，新的状态就是当前阶段的某个状态。由于这个新状态的子状态可能不止一个，所以决策后的对应局部解也可能不止一个，在这些解中取一个最优解，就是当前阶段当前状态的最优解，这个求最优解的过程可用一个表达式来描述，这个表达式就是状态转移方程。状态转移方程应用举例n在下列交通路线中，求节点1到节点1

4、0 的最短路径的长度。14326598710132191517324527111381916251120分阶段决策的手工计算n第一阶段：nf2=f1+13=13;f3=f1+21=21;f4=f1+9=9n第二阶段：nf5=minf2+15,f3+17,f4+24=28;nf6=minf2+3,f3+5,f4+27=16n第三阶段：nf7=minf5+11,f6+8=24;nf8=minf5+13,f6+19=35;nf9=minf6+16=32n 目标阶段求解n第四阶段：nf10=minf7+25,f8+11,f9+20=46具体化的状态转移方程n1、f5=minfj+x,，f6=minfk

5、+y,n2、fj+x中的fj就是上阶段子问题各状态的最优解；而x则是某个子状态转移到当前状态产生的决策效应（或者是代价）一般化的状态转移方程n实际编程实现时，状态转移方程往往是一个通用计算式，在这个通用计算式中往往会包含各种子状态、子状态对应子问题的最优解、决策等参数。动态规划的算法设计n如果用i表示当前需求解的阶段号（有时为了描述的方便，i也可表示当前阶段的前一个阶段），j表示当前阶段各个状态（或者说是阶段的各个节点编号），k表示前一阶段各个子状态能选择的策略，用fI,j表示起点1到第i阶段编号为j的结点（也可理解为状态）的最短距离，那么上面问题用动态规划求解的大致程序结构如下：n穷举所有的

6、阶段（for i:=1 to 4 do）n 穷举当前阶段i所有可能的状态jn 穷举j状态所有对应的子状态的所有可选择的策略kn FI,j:=minfi-1,j1+xj1,k|j1表示状态j所有可能的子状态程序代码实现n输入数据：n2 3 4 0n5 6 0n7 8 9 0n10 0n0 13 21 9 maxint maxint maxint maxint maxint maxintnmaxint 0 maxint maxint 15 3 maxint maxint maxint maxintnmaxint maxint 0 maxint 17 5 maxint maxint maxint m

7、axintnmaxint maxint maxint 0 24 27 maxint maxint maxint maxintn数据结构nAI,j=k表示第i阶段的第j个决策点（后继节点）是k；nDI,j=k表示i和j节点之间的直接联边长度是k，如果是maxint则表示没有直接联边。如果是0则表示节点本身。程序框架nfor i:=1 to 4 donbeginn j:=1;n repeatn j2:=aI,j;n k:=1;n repeatn j1:=ai-1,k;n if dj1,j2maxint then fI,j2:=minfI,j2,fi-1,j1+dj1,j2n inc(k);n un

8、til ai-1,k=0;n inc(j);n until aI,j=0;nend;一些关键的要素n1、阶段n每个阶段的处理是相同的。n2、状态n每个抽象化的节点所共有的特性值。n3、决策n所选择的处理。分析动态规划n1、何时可考虑动态规划n2、阶段、状态、决策如何提炼n3、如何抽象出状态转移方程问题2：数字三角形n下图所示为一个数字三角形，其中三角形中的数值为不超过100的整数，现规定从最顶层往下走到底层，每一步可沿左斜线向下或右斜线向下走。n 7n 3 8n 8 1 0n 2 7 4 4n4 5 2 6 5n 假设三角形行数=100，编程计算从最顶层走到最底层的一条路径，使得沿着该路径所经

9、过的数字之和最大，输出最大值。输入和输出ntrigon.inn7n3 8n8 1 0n2 7 4 4n4 5 2 6 5ntrigon.outn30为什么可用动态规划n 7n 3 8n 8 1 0n 2 7 4 4n4 5 2 6 5算法设计n1、阶段就是行号n2、状态就是每行上的某个数字（位置号表示）n3、决策就是向右（还是向左）的走法。状态转移方程n若用fI,j表示起点到i阶段第j个数字的最优解，用j1表示j对应的子状态，xj1,k表示j1子状态变换到j状态中的第k个决策所产生的决策效应，则可写出状态转移方程如下：nfI,j=maxfi-1,j1+xj1,k|j1和k最多取二个值结合数据结

10、构调整方程n根据输入数据特点，考虑用aI,j保存第i行第j个位置上的数字，那么前面方程中j1可取的值为j-1和j，所以状态转移方程可细化为：nfI,j=maxfi-1,j+aI,j,fi-1,j+1+aI,jn 其中1=i=n，1=j=i，初始化时f1,1=7。写出核心程序段nfillchar(f,sizeof(f),0);nf1,1:=a1,1;nfor i:=2 to n do 枚举阶段n for j:=1 to I do 枚举状态n for k:=j-1 to j do 枚举决策n if fI,jfi-1,k+aI,j then fI,j:=fi-1,k+aI,j;n这样最后求得的fn,

11、n是否是本问题的最优解？问题3：彩石运输n阿强是一个汽车运输工，他正在给一项装饰工程运输所需的彩色石头。这些石头的颜色各异，价格也各不相同。有一天阿强突发奇想，他想在一堆彩石中有选择地把彩石装上他的卡车，使得卡车上装载的石头总价值是所有装载方案中最大的。现在有一堆彩石堆放在阿强面前，他知道任何两块石头的颜色都是不同的，但两块颜色不同的石头的重量和价格可能相同。n 阿强的卡车总共可装载的重量是W，而且他知道总的彩石的块数，请你帮助阿强确定一个方案，满足阿强的奇想。n 输入文件stone.in的第一行是二个整数，依次表示卡车的载重量W和总的彩石块数n，下面共有n行，每行包含二个用空格分隔的整数，依

12、次表示某种颜色彩石的重量和价值。n 输出文件stone.out只包含一行一个整数，表示卡车最终装载彩石的最大总价值。输入输出nstone.inn30 5n20 50n10 30n15 44n5 14n4 13nstone.outn88问题分析n1、有些选手会陷入二种错误的贪心算法中n2、为什么可用动态规划n3、3个要素的分析n（1）阶段n（2）状态n（3）决策提炼出状态转移方程n用wi保存第i种彩石的重量，用pi表示它的价值，用j表示状态，则状态转移方程如下：nfI,j=maxfi-1,j-wi+pi,fi-1,j 核心程序代码nfillchar(f,sizeof(f),0);nfor i:=

13、1 to n donfor j:=1 to w donbeginn fI,j:=fi-1,j;n if(wi=w)and(fI,jfi-1,j-wi+pi)then fI,j:=fi-1,j-wi+pi;nend;nwrite(fn,w);问题4：joy的工具箱nJoy是一位非常出色的汽车维修工，而且他的创业能力也很强，这不，最近他成立了自己的汽车维修110公司，一旦汽车在半途抛锚，只要一个电话，joy就会立刻带着他的工具箱赶到事故地点，为驾驶员朋友维修汽车，由于抢修及时以及维修技术高，汽车维修110公司的生意越来越红火。n 但joy是一个追求无止境的人，在生意越做越大的同时，他又动开了新脑筋

14、。他发现无论维修工具箱买得如何大，肯定不能把他公司里所有的维修工具装进去，100的故障排除率不仅需要精湛的维修技术，如何选择并把最为合适的维修工具装入工具箱，并把工具箱带到故障现场，也是一个非常重要的技巧。由于工具众多，joy无法根据驾驶员报告的故障现象确定最为合适的一些工具，作为朋友的你决定通过程序来帮助joy选择最为合适的工具转入到工具箱中。n n当然，joy会事先告诉你一些必要的信息。比如，他的每个工具都是不同的，工具箱的总体积，joy还会告诉你他根据故障特点给每个工具合适程度的效率分数，你的程序必须能确定哪些工具被装入工具箱，并输出总的最大效率分。n输入文件joy.in第一行包含二个整

15、数v和n，分别表示工具箱总体积和所有可供选择的工具的数量。下面共有n行，每行有二个用空格分隔的整数，依次分别表示每个工具的体积大小和joy给定的效率分。n 输出文件joy.out包含一个整数，表示在工具箱有限的空间内，所装入的所有工具的效率分数的最大值。输入和输出njoy.inn23 5n11 20n9 19n10 15n7 14n8 15njoy.outn39关键要素分析n1、阶段n2、状态n3、决策分析状态转移方程nFI,j表示前i个工具选择部分装入占用容量为j的工具箱中的最大效率分：nfi,j:=maxfi-1,j-v1i+pi|核心程序段nfillchar(f,sizeof(f),0)

16、;n for i:=1 to n don for j:=1 to v don beginn fi,j:=fi-1,j;n if(v1i=j)and(fi,j=ai)and(fj+1fi)then fi:=fj+1;n if bestfi then best:=fi;nend;nwrite(best);逆推求解n如何进行？问题6：乘积最大n在一次数学智力竞赛中，主持人给所有参加活动的选手出了一道题目：设有一个长度为N的数字串，要求选手使用M个乘号将它分成M1部分，求出一种分法，使得这M+1个部分的乘积最大。n 同时，为了帮助选手能够理解题意，主持人还举了如下一个例子：n 有一个数字串：312，当

17、N=3,M=1时有二种分法：n （1）31236；n （2）31262n 这时，符合题意要求的结果是：31262。现在要求设计一个程序，以求得正确的答案。n 输入文件product.in第一行包含二个整数，分别表示N，M（2=N=10，1=M=5），第二行是一个长度为N的数字串。n 输出文件product.out包含一行一个自然数，表示求得的最大乘积。输入和输出nproduct.inn4 2n1231nproduct.outn62算法分析n1、本来用搜索也可n2、n，m扩大时，必须用动态规划n3、用fI,j表示在前i个数字中插入j个乘号可以获得的最大值，那么fn,m就是问题的最优解。特殊到一般

18、抽象出转移方程n1、显然fI,j这个最优解肯定是在下列情形中产生的：nfj,j-1*Aj+1Ainfj+1,j-1*Aj+2Ainnfi-1,j-1*Ain2、提炼出初步的转移方程：nfI,j=maxfi1,j-1*(ai1+1ai)|j=i1=i-1n3、其中的(ai1+1ai)表示第i1+1位到第i位数字串所组成的整数。勾画出初步的代码nFor i:=1 to n don For j:=0 to m don If j=i-1 then n For i1:=j to i-1 don If fI,jfi1,j-1*num(ai1+1ai);n*开始时所有的fI,j初始化为0思考n1、有没有发现

19、算法中的漏洞？n2、分析边界、确定递推初始值中完善算法完善后的算法n所有的fI,j初始化为0；nfor i:=1 to n-m do fI,0:=num(a1ai);n For i:=2 to n don For j:=1 to m don If j=i-1 then n For i1:=j to i-1 don If fI,jfi1,j-1*num(ai1+1ai);注意的细节n实际编程时还须使用高精度算法，由于这里着重介绍动态规划，故本过程省略。问题7：校庆100周年n在柯中建校100周年之际，学校决定举办校庆活动，发出校庆通告和邀请后，学校收到了k多的祝贺条幅，在把这些条幅挂起来的时候，

20、学校负责人要考虑到祝贺单位和个人的知名度和发送祝贺的先后顺序，觉得有必要统筹地安排位置来挂这些条幅。n在柯中校门口的正面，有一座气势雄伟的综合楼，前面有n（1=k=n=100）多的位置可以用来挂条幅，如何把这k条条幅挂到这n个位置上使之总体效果最大呢？学校负责人是这样考虑的：首先给所有条幅按照送来的顺序从1开始编号，然后给综合楼可挂条幅的位置也从1开始编号，无论怎么考虑最大效果，编号小的条幅必须挂在编号大的条幅的前面（即所在位置的编号较小）；但考虑到送条幅单位或个人知名度的问题，负责人又给每个条幅挂在每个位置上的效果打了分。最终希望挂条幅的效果分到达最大。n输入文件aniversary.in第

21、一行包含二个空格分隔的整数k和n，分别表示总条幅数量和总的可挂条幅的数量。下面一共有k行，每行有n个空格分隔的整数，输入文件第i+1行第j列的整数表示编号为i的条幅挂在编号为j的位置上的效果分（在50到50之间）。n 输出文件aniversary.out包含一行一个整数，表示可能获得的最大的效果分。输入和输出naniversary.inn3 5n7 23-5-24 16n5 21-4 10 23n-21 5-4-20 20naniversary.outn53三要素分析n1、横幅作为阶段In2、前i个横幅放置所占的前j个位置作为状态n3、决策就是第i个横幅放置在前j个位置的哪个位置上状态转移方程

22、n用ansI,j表示前i个横幅放入前j个位置，并且第i个横幅放置于第j个位置上的最优解。nAnsI,j=maxansi-1,t+aI,j|i=j=n-(k-i),i-1=t=j-1 算法框架nfor i:=1 to k do 以条幅作为阶段枚举n beginn for j:=i to n-(k-i)don beginn ansi,j:=low(ansi,j);设置一个较低的值，所有局部解中的最差解n for t:=i-1 to j-1 do 穷举决策，实际通过穷举子问题状态来实现n if ansi,jansi-1,t+ai,j then ansi,j:=ansi-1,t+ai,jn end;n

23、 end;数组的初始化n根据第一阶段求解分析出：nfillchar(ans0,sizeof(ans0),0);思考n最优解是否保存于ansk,n中？搞清ansk,n的实质n1、指的是最后一个横幅放置于第n个位置上的最优解n2、那么这个值一定大于最后一个横幅放置于k、k+1、k+2、n-1位置上的值吗？n3、所以，最后须对数组ans中最后一行的数值求最大值处理。产生全局最优解nm:=k;nfor j:=k+1 to n do if ansk,mansk,j then ansk,m:=ansk,j;解法2：改变阶段和状态的划分n1、阶段i。前i个位置n2、状态j。前j个横幅放置的位置n3、决策t。第j个横幅放置的位置新的状态转移方程n用ansI,j表示前i个位置放置了前j个横幅的最优解。nansI,j=maxanst,j-1+aj,t+1|1=i=n,1=j=I,j-1=ti-1算法框架nFor i:=1 to n don for j:=1 to i don for t:=j-1 to i-1 don if ansI,janst,j-1+aj,t+1 thenn ansI,j=anst,j-1+aj,t+1;思考n这样求得的ansn,k是否是问题的最终解？