NOI导刊线型动态规划.ppt

线型动态规划,长沙市雅礼中学朱全民,带权有向的多段图问题,给定一个带权的有向图，要求从点A到点D的最短路径。,设F(i)表示从点A到达点i的最短距离，则有F(A)=0F(B1)=5,F(B2)=2F(C1)=minF(B1)+3=8F(C2)=minF(B1)+2,F(B2)+7=7F(C3)=minF(B2)+4=6F(D)=minF(C1)+4,F(C2)+3,F(C3)+5=10,多阶段最优化决策问题,由上例可以看出，整个问题分成了A、B、C、D四个阶段来做，每个阶段的数值的计算只会跟上一个阶段的数值相关，这样一直递推下去直到目标。即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线。,状态转移方程,设fk(i)k阶段状态i的最优权值，即初始状态至状态i的最优代价。fk+1(i)=minfk(j)+u(i,j),第k+1阶段状态,第k阶段状态,决策,动态规划的基本原理,最优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。无后效性原则给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。,第1题：关键子工程,有N个子工程，每一个子工程都有一个完成时间。子工程之间的有一些依赖关系，即某些子工程必须在一些子工程完成之后才开工。在满足子工程间的依赖关系前提下，可以有任何多个子工程同时在施工。求整个工程的完成的最短时间。求出所有关键子工程。N200,有向图的关键路径,分析,如果该图能够进行拓扑排序，证明有解，反之则无解。根据拓扑序列进行动态规划求解，得到工程所需的完成时间。设FI表示完成子工程I所需的最早时间。动态规划方程：FI=MAXFJ+AI，J根据的得到的F序列和拓扑序列，查找关键工程。初始时，最后完成的一个或多个工程为关键工程。如果FI=FJ-AI，J，且第I个子工程为关键工程，那么第J个子工程也是关键工程。时间复杂度为O(N2)。,拦截导弹,给定N个数求最长的不上升子序列长度求最少有多少个不上升序列能覆盖所有的数，即求最少覆盖序列。N=10000.,分析,设f(i)表示前i个数的最长不上升序列的长度。则,f(i)=maxf(j)+1,其中j=ai这里0j=k=p。(3)因此r=p，定理1得证。,解决,要求最少的覆盖，按照Dilworth定理最少链划分=最长反链长度所以最少多少套系统=最长导弹高度上升序列长度。知道了怎样求最长不上升算法，同样也就知道了怎样求最长上升序列。时间复杂度O(nn)。,青蛙过河(NOIP2005),在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。,【输入文件】输入文件river.in的第一行有一个正整数L（1=L=109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1=S=T=10，1=M=100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。【输出文件】输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。【样例输入】1023523567【样例输出】2【数据规模】对于30%的数据，L=10000；对于全部的数据，L=109。,分析,由于不能往回跳，很容易想到用动态规划解决这个题目。设f(i)表示跳到第i个点需要踩到的最少石子数，则很容易写出动态规划的状态转移方程:,时间复杂度是O(L*(T-S)，但本题的L高达109，根本无法承受!,进一步分析,我们先来考虑这样一个问题：长度为k的一段没有石子的独木桥，判断是否存在一种跳法从一端正好跳到另一端。若S=MaxK，都可以从一端正好跳到另一端。题设中1=S=T=10，经过简单推导或者程序验证就可以发现，取MaxK=100就能满足所有区间。,于是我们可以分两种情况讨论：1.S=T时：这时候由于每一步只能按固定步长跳，所以若第i个位置上有石子并且imodS=0那么这个石子就一定要被踩到。这是我们只需要统计石子的位置中哪些是S的倍数即可。复杂度O(M)2.SMaxK+2*T，我们就将这段区域缩短成长度为MaxK+2*T。可以证明处理之后的最优值和原先的最优值相同。,如上图所示，白色点表示连续的一长段长度大于MaxK+2*T的空地，黑色点表示石子。设原先的最优解中，白色段的第一个被跳到的位置a，最后一个被跳到的位置是b，则在做压缩处理之后，a和b的距离仍然大于MaxK，由上面的结论可知，必存在一种跳法从a正好跳到b，而且不经过任何石子。,所以原来的最优解必然在处理之后的最优解解集中。经过这样的压缩处理，独木桥的长度L最多为(M+1)*(MaxK+2*T)+M，大约12000左右。压缩之后再用先前的动态规划求解，复杂度就简化成了O(L*(T-S)，已经可以在时限内出解了。这样本题就得到了解决。,火车进站,给定N辆火车第i辆火车的进站时间arrive(i)第i辆火车的离站时间leave(i)车站只能容纳M辆火车求最多能接受多少辆火车？M=3,先看样第1，2，3辆分别进入（123）；第2辆离开，可以看出要离开时，被第1辆火车卡在前面，因此第1辆火车不能进入，队列为（23）第2辆离开，第4辆进入（34）第3，4辆离开，队列空第5，6辆进入（56）第5，6分别离开，队列空因此答案为5辆,分析,按到达时间排序和离开时间排序，这样每一辆火车用线段描述，有：排在前面的火车，其进站时间必须先于排在后面的火车；排在前面的火车，其出站时间必须先于排在后面的火车，否则该列火车就要先进后出，不满足队列特点。这样对于任一列排序后的火车i，只有排在其后的火车才有可能在它出站之后进站。接下来的任务便是采用动态规划方法求解了。,m=1时,设fi表示第i列火车进站时，其后的火车最多可以进站的数量，则有：fi=maxfj+1，（满足i比j先进站，且j在i出站之后进站）；,m=2,设fi,j表示车站停靠i,j两列火车(ij)时，其后的火车（包括i,j本身）最多可以进站的数量,则:fi,j=maxfj,k+1条件：必须满足按i,j,k顺序进站和出站，另外还要满足k在i出站后且j进站。,m=3,设fi,j,k表示车站停靠i,j,k三列火车(ijfj)then多增加一位的情况fj:=pfj-1+1;end;pf:=f;end;说明：pf是一个与f完全相同的数组，实现f(i)与f(i-1)的滚动,样例运行过程,S=“ABCBDAB.”T=“BABCBD.”初始：f(i,0)=0,f(0,i)=0;S1T1;f(1,1)=MAXf(1,0),f(0,1)=0S1=T2;f(1,2)=MAXf(1,0)+1=1S2=T1;f(2,1)=MAXf(1,0)+1=1S2T2;f(2,2)=MAXf(1,2),f(2,1)=1S2=T3;f(2,3)=MAXf(1,2)+1=2S3T1;f(3,1)=MAXf(3,0),f(2,1)=1S3T2;f(3,2)=MAXf(2,2),f(3,1)=1S3T3;f(3,3)=MAXf(3,2),f(2,3)=2一直求到f(8,7),ans=f(8,7)-1；减1是因为最后都有一个”.”,总结,线型动态规划问题，最典型的特征就是状态都在一条线上，并且位置固定，问题一般都规定只能从前往后取状态，解决的办法是根据前面的状态特征，选取最优状态作为决策进行转移。设前i个点的最优值，研究前i-1个点与前i个点的最优值，利用第i个点决策转移，如下图。状态转移方程一般可写成:fi(k)=minfi-1orj(k)+u(i,j)oru(i,i-1),