动态规划一PPT

什么是动态规划？（一）动态规划是解决多阶段决策问题的一种方法。多阶段决策问题对于整个问题，可以根据其时间或其他顺序分成若干个前后相关联的子问题，问题的全局最优包含其子问题的局部最优，即满足最优子结构性质，并且无后效性，有边界条件，且一般划分为很明显的阶段，存在一条或多条状态转移方程。“最优性原理”可陈述为：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。最优决策序列的子序列，一定是局部最优决策子序列。包含有非局部最优的决策子序列，一定不是最优决策序列。最优性原理如图，已知一个有向图，求一条从最左边的点走到最右边点的方案（只能从左往右走），使得所经过的权值和除以4的余数最小。231312MOD4余数最小问题设所有点从左至右编号为1…4，MIN（i）表示前I个点的最优值，很容易得出一个方程：Min(i)=min{(Min(I-1)+num[I-1,1])mod4,Min(I-1)+num[I-1,2])mod4}通过这个方程可以求出一条路径为（2+3+1）MOD4=2但最优值实际上是（2+1+1）MOD4=0。为什么会出错呢？分析观察以上数据发现取Min(３)的时候，动态规划求出来的最优值为１，而正确的值应该为0，由此可知本题对应于一条最优路径，并不是这条路径上的所有点的最优值都是从点１到该点可得的最优值，对于每一个阶段都取最优值并不能保证求出最优解，即不满足最优化原理，因此这种规划方法在本题行不通。让我们来换一个思路思考本题，因为本题是要求总和除以４余数最小的一条路径，我们先撇开最小余数不去管它，而是将本题改为从点1到点４的所有路径中，求出每条路上权值和除以４的不同余数的个数。我们设一个数组can[I,j]表示从点1至点Ｉ可不可以求出一条路径是该路径的权值总和除以４的余数为Ｊ，那么又可以得出一个方程：can[I,j]:=can[I-1,k]and((k+num[I,p])mod4=j)(0=k=3,1=p=2)can[1,0]=truecan[1,1]=falsecan[1,2]=falsecan[1,3]=false通过这个方程我们可以求出从点1至点Ｉ可以达到的所有余数，我们只要从这些余数中选出一个值最小的输出就行。什么是动态规划？（二）动态规划实际上就是一种排除重复计算的算法，更具体的说，动态规划就是用空间换取时间。问题：给定一个具有N层的数字三角形如下图，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最大路径得分。738810274445265初看此题不难想到本题可以用递归算法来解决：FunctionMax(I,J:integer):longint;{从当前位置开始的可得的最优值}Vars1,s2:Longint;{记录从左右斜线向下走的可达的最优值}BeginIf(In)Or(JI)ThenMax:=-1{当前位置不存在，最优值为-1}ElseBeginS1:=Max(I+1,j)+triangle[I,j];{沿左斜线向下走}S2:=Max(I+1,j+1)+triangle[I,j];{沿右斜线向下走}Ifs1s2thenMax:=s1Elsemax:=s2;{选取最优走法}End;End;由以上算法不难算出其时间复杂度为2^n，而本题N最大为100，显然当N比较大时是无法在规定时间内出解的，但本题又很难找出理想的剪枝方法。通过以下搜索树可以看出在求Max(2,1),Max(2,2)的时候两次调用函数Max(3,2)，也就是说，函数Max(3,2)被重复计算了两次，其实在这棵搜索树中有很多结点都被重复计算了多次，程序时效显然就会大打折扣了，实际上这也是搜索之所以会效率低下的一大原因。既然知道了上述搜索算法效率低的原因。对于同一个函数值搜索多次是没有必要的，因此我们可以每求出一个函数的值便可将其用数组保存下来，到了下次要用的时候直接从数组里调出来用就可以了。这样时间复杂度一下子降成了O(N*N){函数个数最多不超过N*N个。}Max(1,1)=max{Max(2,1),Max(2,2)}Max(2,1)=max{Max(3,1),Max(3,2)}Max(2,2)=max{Max(3,2),Max(3,3)}FunctionMax(I,J:integer):longint;{从当前位置开始的可得的最优值}Vars1,s2:Longint;{记录从左右斜线向下走的可达的最优值}BeginIfA[I,j]-1ThenBegin{函数I，J已求出，直接赋值即可}Max:=A[I,j];Exit;End;If(In)Or(JI)ThenMax:=0{当前位置不存在，最优值为0}ElseBeginS1:=Max(I+1,j)+triangle[I,j];{沿左斜线向下走}S2:=Max(I+1,j+1)+triangle[I,j];{沿右斜线向下走}Ifs1s2thenA[I,j]:=s1ElseA[I,j]:=s2;{选取最优走法}Max:=A[I,j];{记录该函数值}End;End;矩阵分割问题（cuts)给你一个矩阵，其边长均为整数。你想把矩阵切割成总数最少的正方形，其边长也为整数。切割工作由一台切割机器完成，它能沿平行于矩形任一边的方向，从一边开始一直切割到另一边。对得到的矩形再分别进行切割。输入数据：输入文件中包含两个正整数，代表矩形的边长，每边长均在1—100之间。输出数据：输出文件包含一行，显示出你的程序得到的最理想的正方形数目。输入输出示例：CUTS.IN：56CUTS.OUT:5分析记忆化搜索与动态规划（见解题报告）动态规划问题具有以下基本特征：1、问题具有多阶段决策的特征。2、每一阶段都有相应的“状态”与之对应，描述状态的量称为“状态变量”。3、每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态。4、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。动态规划的基本模型阶段：据空间顺序或时间顺序对问题的求解划分阶段。状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。决策：根据题意要求，对每个阶段所做出的某种选择性操作。状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。动态规划的几个概念动态规划问题的一般解题步骤1、判断问题是否具有最优子结构性质，若不具备则不能用动态规划。2、把问题分成若干个子问题（分阶段）。3、建立状态转移方程（递推公式）。4、找出边界条件。5、将已知边界值带入方程。6、递推求解。线性规划模型例1：机器分配问题。总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M=150，N=100。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个N*M的矩阵，表明了第I个公司分配J台机器的盈利。分析用机器数来做状态，数组F[I，J]表示前I个公司分配J台机器的最大盈利。则状态转移方程为:F[I，J]=Max{F[I-1，K]+Value[I，J-K]}(1=I=N,1=J=M,0=K=J)初始值:F(0,0)=0时间复杂度O(N*M2)有一条河从东向西将某地区分为南北2个部分。河的两岸各有N个城市。北岸的每个城市都与南岸的某个城市是友好城市，而且关系是一一对应的。现在要求在2个友好城市之间建立一条航线，但由于天气的缘故，所有的航线都不能相交，因此，就不能给所有的友好城市建立友好航线。请设计一个修建航线的方案，能建最多的航线而且不相交。输入：第一行为一个正整数N(N=1000)以下N行，记第i行有一个正整数j，表示北岸的城市i与南岸的城市j互为友好城市。其中城市编号是按从东到西排列的。输出：仅一行，即最多的航线数。船(ceoi)首先我们需要判定对于给定的两条航线是否相交，设北岸城市i1，j1(i1j1)分别与南岸城市i2，j2互为友好城市，那么这两条航线不相交(以下简称为i1，j1相容)的充要条件是I2=J2。(结论1)由下图就可以很容易地得到这个结论。i1j2i2j1j2i2j1i1北岸：南岸：图一图二分析从上面的结论可以看出，最优的选择方案中，如果将所有航线按北岸村庄号从小到大排序，序列中每一个北岸村庄对应的南岸村庄号必然满足B1B2B3……Bn（n为选出来的航线数）。同样，对于任一个方案，如果北岸村庄排好序后，与之对应的南岸村庄也是按升序排列，那么该方案必然不存在相交的两条航线；相反，如果南岸村庄不是按升序排列，必存在两条相交的航线。因此，我们可以先将各航线按北岸村庄号排一个序，那么最优的方案必然是从相对应的南岸村庄中找出一个最长不下降序列，该序列的长度即为问题的解。凸多边形三角划分给定一个具有N（N50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？输入文件：第一行顶点数N第二行N个顶点（从1到N）的权值输出格式：最小的和的值各三角形组成的方式输入示例：5122123245231输出示例：Theminimumis：12214884Theformationof3triangle:345,153,123分析设F[I,J]（IJ）表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}(0IKJ=N)初始条件:F[1，2]=0目标状态:F[1,N]但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算在数字串中插入若干(K个)乘号使总的乘积最大。分析：定义从l到r加入k个乘号的最大乘积值为p(l,r,k)。p(l,r,k)=max{d(l,q)*p(q+1,r,k-1)}数字最大乘积解题思路定义:从l到r加入k个乘号的最大乘积值p(l,r,k)。p(l,r,k)=max{d(l,q)*p(q+1,r,k-1)}楼梯问题一个小孩有N块小砖头(5=N=500).这些小砖头能彻成不同的楼梯。这些楼梯包含着不同高度的梯级（严格按照递减顺序），不允许有（高度）相同的梯级。每一个楼梯至少包含2个梯级，每个梯级至少一块砖。输入N输出不同的楼梯方案数如N=5,则输出2（4+1，3+2)从样例数据不难看出方案总数可能会达到很大，因此本题用搜索是行不通的，我们可以用动态规划来解决它。设f[I,j,k]表示用j块砖来组建共I个台阶的楼梯，楼梯的最后一级台阶由k块砖组成的方案总数f[I,j,k]=∑f[I–1,j–k,k1](1=k1k)而总方案数为：∑f[I，n，k](1=I=最大台阶数,1=k=n)该算法的时间复杂度为：o(n^4)空间复杂度为：o(n^3),即便是用滚动数组也要n^2的空间。无论从时间还是空间上来看，本算法都要进行优化。其实我们可以将f数组降一维。设f[I，J]表示用I块砖组建楼梯，楼梯最后一级由j块砖组成的方案数。F[I，J]=∑f[I-j,j1](1=j1j)最后的方案总数为：∑f[n,I](1=I=n-1)经过重新定义后的时间复杂度为：o(n^3)空间复杂度为：o(n^2)虽然本算法已经比较高效了，但当n=500时，还是要耗很多时间，我们还要作进一步优化。优化动态规划的方法一般为降维和减少重复计算，本算法如果要再降一维比较困难，看