动态规划初步

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,动态规划初步,JSOI2007夏令营B层次（泰州）,1,问题：城市交通,有n个城市，编号1n，有些城市之间有路相连，有些则没有，有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市，问你从编号为1的城市走到编号为n的城市要花费的最短距离是多少？,输入格式：,先输入一个n，表示城市数，n100。,下面的n行，是一个n*n的邻接矩阵map1.n,1.n。,mapi,j=0，表示城市i和城市j之间没有路相连，否则为两者之间的距离。,输出格式：,一个数，表示从城市1走到城市n的最短距离。,输入数据保证可以从城市1走到城市n。,动态规划的引入,2,输入样例：,11,0 5 3 0 0 0 0 0 0 0 0,5 0 0 1 6 3 0 0 0 0 0,3 0 0 0 8 0 4 0 0 0 0,0 1 0 0 0 0 0 5 6 0 0,0 6 8 0 0 0 0 5 0 0 0,0 3 0 0 0 0 0 0 0 8 0,0 0 4 0 0 0 0 0 0 3 0,0 0 0 5 5 0 0 0 0 0 3,0 0 0 6 0 0 0 0 0 0 4,0 0 0 0 0 8 3 0 0 0 3,0 0 0 0 0 0 0 3 4 3 0,动态规划的引入,3,设一个数组dis1.n，disi表示城市1到城市i的最短距离。题目就是要求disn。,根据题目的限制条件：只能从编号小的城市到编号大的城市。显然，我们可以从城市1、城市2、城市n-1到城市n，前提是城市i与城市n之间有路，其中i=1，2，3，n-1。,所以，disn就应该取disi+mapi，n中的最小值，且要求mapi，n0，i=1，2，3，n-1。,也就是说要求disn，就必须先求出dis1disn-1，类似于递推算法中的“倒推法”，那么如何求disn-1呢？,disn-1 = min disi + mapi，n-1 ,且要求mapi，n-10，in-1。,城市交通分析,4,现在我们把问题一般化，如何求disi呢？其中，i=1.n。,Disi = min disj + mapj，i,要满足：mapj，i0，j=1.i-1,这是一个类似于递归的公式，意思为：要求disn就要先求disn-1 dis1，要求disn-1就要先求disn-2 dis1，而要求disi，就要先求disi-1 dis1，而dis1=0。在具体计算的时候，只要从dis1开始“顺推”下去，依次求出dis2、 dis3、 disn-1 、disn即可。,城市交通分析,5,dis1:=0;,for i:=2 to n do,begin,min:=maxint; 用打擂台的方法求出最小值,for j:=1 to i-1 do,if mapj,i0 then,if disj+mapj,i1，j=1.i-1，且hj=hi,第一问的答案就是a1a8中的最大值。,“拦截导弹”问题分析,12,longest1:=1;,for i:=2 to n do 分阶段求出每步的最优值,begin,maxlong:=1;,for j:=1 to i-1 do,if himaxlong then maxlong:=longestj+1;,longesti:=maxlong,end;,maxlong:=longest1; 以下打擂台求出最大值,for i:=2 to n do,if longestimaxlong then maxlong:=longesti;,writeln(max=,maxlong);,这种解题方法就称为“动态规划”,“拦截导弹”问题分析,13,“拦截导弹”问题分析,关于第二问：,由于它紧接着第一问，所以很容易受前面的影响，多次采用第一问的办法，然后得出总次数，其实这是不对的。要举反例并不难，比如长为7的高度序列“7 5 4 1 6 3 2”， 最长不上升序列为“7 5 4 3 2”，用多次求最长不上升序列的结果为3套系统；但其实只要2套，分别击落“7 5 4 1”与“6 3 2”。所以不能用多次“动态规划”的方法做，那么，正确的做法又是什么呢？,我们的目标是用最少的系统击落所有导弹，至于系统之间怎么分配导弹数目则无关紧要，上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势，忽视了最优解中各个系统拦截数较为平均的情况，本质上是一种贪心算法，但贪心的策略不对。如果从每套系统拦截的导弹方面来想行不通的话，我们就应该换一个思路，从拦截某个导弹所选的系统入手。,14,“拦截导弹”问题分析,题目告诉我们，已有系统目前的瞄准高度必须不低于来犯导弹高度，所以，当已有的系统均无法拦截该导弹时，就不得不启用新系统。如果已有系统中有一个能拦截该导弹，我们是应该继续使用它，还是另起炉灶呢？事实是：无论用哪套系统，只要拦截了这枚导弹，那么系统的瞄准高度就等于导弹高度，这一点对旧的或新的系统都适用。而新系统能拦截的导弹高度最高，即新系统的性能优于任意一套已使用的系统。既然如此，我们当然应该选择已有的系统。如果已有系统中有多个可以拦截该导弹，究竟选哪一个呢？当前瞄准高度较高的系统的“潜力”较大，而瞄准高度较低的系统则不同，它能打下的导弹别的系统也能打下，它够不到的导弹却未必是别的系统所够不到的。所以，当有多个系统供选择时，要选瞄准高度最低的使用，当然瞄准高度同时也要大于等于来犯导弹高度。,15,“拦截导弹”问题分析,解题时用一个数组sys记下当前已有系统的各个当前瞄准高度，该数组中实际元素的个数就是第二问的解答。,sys1:=h1; tail:=1;,for i:=2 to n do,begin,minheight:=maxint;,for j:=1 to tail do 找一套最适合的系统,if sysjhi then,if sysjminheight then,begin minheight:=sysj; select:=j end;,if minheight=maxint 开一套新系统,then begin tail:=tail+1; systail:=hi end,else sysselect:=hi,end;,writeln(total=,tail);,16,动态规划简介,数字三角形（IOI1994）,问题描述,如下所示为一个数字三角形：,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。规定：, 每一步可沿直线向下或右斜线向下走；, 1三角形行数100；, 三角形中的数字为整数0，1，99；,样例输出：,30,17,动态规划简介,分析数字三角形,1、穷举法：最多100行，有2,99,条路径，超时；,2、贪心法：不正确；,3、动态规划：,假设从顶至数字三角形的某一位置的所有路径中，所经过的数字的总和最大的那条路径，我们称之为该位置的最大路径。由于问题规定每一步只能沿直线向下或沿斜线向右下走，若要走到该位置，则其前一位置必为其左上方或正上方两个位置之一，由此可知，当前位置的最优路径必定与其左上方或正上方两个位置的最优路径有关，且来自于其中更优的一个。,18,动态规划简介,设ai，j表示数字三角形中第i行第j列的数，再设一个二维数组sum记录每个位置的最优路径的数字总和，则：,sumi，j=maxsumi-1，j，sumi-1，j-1 + ai，j,其中：2=i=n，2=jsumi-1,j,then sumi,j:=sumi-1,j-1+ai,j,else sumi,j:=sumi-1,j+ai,j;,ans:=0; 打擂台求最优值,for j:=1 to n do,if sumn,jans then ans:=sumn,j;,writeln(ans);,Var sum:array1.maxn,0.maxn of longint;,程序中为什么没考虑j=1或j=i的情况？,20,思考题,假如本题还要你输出最大值的那条路径，即不仅要求出最优值、还要你构造出最优方案，你怎么办呢？,用1个三维数组 sum1.maxn,0.maxn,1.2来记忆最优值及最优值的来源，在递推的同时记下路径，即：sumx,y,1表示第x行、y列能够取得的最大值，sumx,y,2表示该最大值是从上一行的哪个位置得来的（如-1表示从左上方得到的，0表示从正上方得到的）。最后输出时，从下往上倒过来推即可！,动态规划简介,21,动态规划的基本概念,1、阶段,用动态规划求解一个问题时，需要将问题的全过程恰当地划分成若干个相互联系的阶段，以便按一定的次序去求解。阶段的划分一般是根据时间和空间的自然特征来定的，一般要便于把问题转化成多阶段决策的过程。,2、状态,状态表示的是事物某一阶段的性质，状态通过一个变量来描述，这个变量称为状态变量。各个状态之间是可以相互转换的。,3、决策,对问题的处理中做出某种选择性的行动就是决策。一个实际问题可能要有多次决策，在每一个阶段中都需要有一次决策。,一次决策就会从一个阶段进入另一个阶段，状态也就发生了转移。,22,动态规划的基本概念,4、策略和最优策略,所有阶段按照约定的决策方法，依次排列构成问题的求解全过程。这些决策的总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略称为最优策略。,5、状态转移方程,前一阶段的终点就是后一阶段的起点，这种关系描述了由K阶段到K+1阶段状态的演变规律，是关于两个相邻阶段状态的方程，称为状态转移方程，是动态规划的核心。,6、指标函数和最优化概念,用来衡量多阶段决策过程优劣的一种数量指标，称为指标函数。它应该在全过程和所有子过程中有定义、并且可度量。指标函数的最优值，称为最优值函数。,23,动态规划的基本概念,动态规划所处理的问题是一个“多阶段决策问题”,目的是得到一个最优解（方案）,大概思想如下图所示：,24,运用动态规划的条件,1、最优化原理,作为整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为：子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质。也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。,比如前面的数字三角形问题，如果我们想求走到某一位置的最优路径，我们只需要知道其左上方或正上方两个位置之一的最优值，而不用考虑其它的路径，因为其它的非最优路径肯定对当前位置的结果没有影响。,25,运用动态规划的条件,1、最优化原理,在数字三角形问题中，如果我们把问题稍微改变一下：将三角形中的数字改为-100100之间的整数，计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最接近于零。,这个问题就不具有最优子结构性质了，因为子问题最优，即最接近于零，反而可能造成问题的解远离零，这样的反例是不难构造的，本问题就不能用动态规划的方法解决了。,因此，并不是所有的“决策问题”都可以用“动态规划”来解决。只有当一个问题呈现出最优子结构时，“动态规划”才可能是一个合适的侯选方法。,26,运用动态规划的条件,2、无后效性原则,1、最优化原理,所谓无后效性原则，指的是这样一种性质：某一阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说“未来与过去无关”。当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。,具体地说，如果一个问题被划分各个阶段之后，阶段I中的状态只能由阶段I+1中的状态转移方程得来，与其他没有关系，特别是与未发生的状态没有关系，这就是无后效性。,27,运用动态规划的条件,2、无后效性原则,1、最优化原理,例如：给定一个平面上的n个点的坐标，规定必须从最左边一个点开始，严格地从左至右访问到最右边的点，再严格地由右向左访问到出发点，编程确定一条连接各个点的闭合的游历路线，要求整个路程最短的路径长度。,分析：,本题可以根据起点，终点划分阶段，且满足无后效性原则，可以考虑用动态规划做。,但如果把“规定必须从最左边一个点开始，严格地从左至右访问到最右边的点，再严格地由右向左访问到出发点”这个限制条件去掉，则阶段与阶段之间没有什么必然的“顺序”，而且把各个阶段画成一个图后会出现“环路”，所以有“后效性”，就不能用动态规划做了。,28,动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）解。若存在多个最优解的话，它只取其中的一个。,动态规划的基本概念,29,动态规划应用举例,例1、挖地雷（NOIP1996 ）,在一个地图上有N个地窖（N=200），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。,输入,N 地窖的个数,W,1,W,2,W,N,每个地窖中的地雷数,X,1,Y,1,表示可从X,1,到Y,1,X,2,Y,2,0 0 表示输入结束,输出,K1K2Kv,挖地雷的顺序,MAX 最多挖出的地雷数,30,输入：,6,5 10 20 5 4 5,1 2,1 4,2 4,3 4,4 5,4 6,5 6,0 0,输出：,3-4-5-6,34,31,挖地雷问题分析,设W（i）为第i个地窖所藏有的地雷数，A（i,j）表示第i个地窖与第j个地窖之间是否有通路，F（i）为从第i个地窖开始最多可以挖出的地雷数。,动态规划应用举例,F（i）= MAX F(j) + W(i) ,(ij=n , A(i,j)=1),边界：F（n）=W(n),于是就可以通过递推的方法，从后（即F（n）往前逐个找出所有的F（i），再从中找一个最大的即为第2问的解。,对于具体所走的路径（第2问），可以通过一个向后的链接来实现。,32,动态规划应用举例,例2、接苹果(apples),农场的夏季是收获的好季节。在John的农场，他们用一种特别的方式来收苹果：Bessie摇苹果树，苹果落下，然后John尽力接到尽可能多的苹果。作为一个有经验的农夫，John将这个过程坐标化。他清楚地知道什么时候(1=t=1,000,000)什么位置(用二维坐标表示，-1000=x,y=1000)会有苹果落下。他只有提前到达那个位置，才能接到那个位置掉下的苹果。一个单位时间，John能走s(1=s=1000)个单位。假设他开始时(t=0)站在(0,0)点，他最多能接到多少个苹果？,输入：第一行是两个整数N(苹果个数，N=5000)和S(速度)；,第2.N+1行：每行3个整数Xi,Yi,Ti，表示每个苹果掉下,的位置和落下的时间。,输出：仅一行，一个数，表示最多能接到几个苹果。,33,动态规划应用举例,样例,apples.in,5 3,0 0 1,0 3 2,-5 12 6,-1 0 3,-1 1 2,apples.out,3,说明：John可以接到第1,5,4个苹果。,34,动态规划应用举例,接苹果问题分析,首先划分阶段，很明显，按照苹果掉落的时间先后顺序来划分阶段，所以有必要按时间从小到大给各个苹果排个序，并按顺序标上1.n的编号。,假如John现在正站在某个位置上接苹果，为了使他到当前为止接到的苹果数最大，我们想要知道的是他前一步在哪个位置接苹果，并且要知道到那个位置为止接到的苹果最多是多少。,假设dis(i，j)表示第i个苹果与第j个苹果之间的直线距离。time(i)表示第i个苹果掉落的时刻。F(i)表示John当前站在第i个苹果的位置上最多能接到的苹果总数（包括他以前接的）。,F(i) = max F(j) + 1 ,其中0=j=i-1，且dis(i,j)=(time(i)-time(j)*S,初始条件：F(0)=0,表示John站在出发点(0,0)时一个苹果也没接到。,35,动态规划应用举例,例3、低价购买（buylow）,“低价购买”这条建议是在股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的购买建议：低价购买，再低价购买。每次你购买一支股票，你必须用低于你上次购买它的价格购买它。买的次数越多越好!,你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。,你将被给出一段时间内一支股票每天的出售价(216范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买，再低价购买”的原则。,写一个程序计算最大购买次数。,这里是某支股票的价格清单：,日期 1 2 3 4 5 6 7 8 9 10 11 12,价格 68 69 54 64 68 64 70 67 78 62 98 87,最优秀的投资者可以购买最多4次股票，可行方案中的一种是：,日期 2 5 6 10,价格 69 68 64 62,36,动态规划应用举例,输入,输入共两行，第1行为 N (1 = N = 5000)，表示股票发行天数；,第2行: N个数，是每天的股票价格。,输出,输出两个数:最大购买次数和拥有最大购买次数的方案数(=2,31,),当两种方案“看起来一样”时（就是说它们构成的价格队列一样时），这,两,种方案被认为是相同的。,样例,BUYLOW.IN,12,69 68 54 70 68 64 70 67 78 62 98 87,BUYLOW.OUT,4 4,先探索一下样例，最大购买次数为4次，共有4种方案，分别为：,69、68、64、62,69、68、67、62,70、68、64、62,70、68、67、62,37,动态规划应用举例,我们发现，这道题和“导弹问题”的几乎完全相同！实际上是在一个数列中选出一个序列，使得这个序列是一个下降序列（即序列中的任意一个数必须大于它后面的任何一个数），且要使这个序列的长度最长。但是这道题要输出总的方案数，这就需要对原有的求解过程作一些变动。求方案总数最主要的是要剔除重复方案。在样例中，第2和第5个数都是68。以第一个68结尾的最长下降序列的方案为69、68；以第二个68结尾的最长下降序列的方案为69、68 和70、68这时候就产生了方案的重复，即产生了两个69、68。显然后面的68要比前面一个更优，因为后面的68位置更靠后，以这个68结尾的最长下降序列的总数肯定要比前面一个多，而且其方案必定囊括了前面一个68的所有方案。因此，在解题过程中，我们就可以只考虑后面一个68。推广开来，如果当前状态之前存在重复的状态，我们只要考虑离当前状态位置最近的那一个即可。,38,动态规划应用举例,设F（i）表示到第i天，能够购买的最大次数。,其中：1=j=i-1，且OKj=true,OKj=true表示相同价格时，该位置更优。,F（1）=1,F（i）= max F(j) + 1 ,39,总 结,1、递推的边界条件一般很明显，而动态规划的边界条件比较隐蔽，容易被忽视；,2、递推的数学性一般较强，而动态规划的数学性相对较弱；,3、递推一般不划分阶段，而动态规划一般有较为明显的阶段；,4、动态规划往往是用来求一个最优值，而一般的递推往往是用来计数或是求一个值。,动态规划和一般递推的不同点？,动态规划和一般递推的相同点？,无后效性和有边界条件。,40,小结及作业,上机调试所有课堂上的例题。,41,