动态规划-曹利国

动态规划长沙市第一中学曹利国什么是动态规划？（一）动态规划是解决多阶段决策问题的一种方法。多阶段决策问题对于整个问题，可以根据其时间或其他顺序分成若干个前后相关联的子问题，问题的全局最优包含其子问题的局部最优，即满足最优子结构性质，并且无后效性，有边界条件，且一般划分为很明显的阶段，存在一条或多条状态转移方程。“最优性原理”可陈述为：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。最优决策序列的子序列，一定是局部最优决策子序列。包含有非局部最优的决策子序列，一定不是最优决策序列。最优性原理如图，已知一个有向图，求一条从最左边的点走到最右边点的方案（只能从左往右走），使得所经过的权值和除以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(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)}通过以下搜索树可以看出在求Max(2,1),Max(2,2)的时候两次调用函数Max(3,2)，也就是说，函数Max(3,2)被重复计算了两次，其实在这棵搜索树中有很多结点都被重复计算了多次，程序时效显然就会大打折扣了，实际上这也是搜索之所以会效率低下的一大原因。既然知道了上述搜索算法效率低的原因。对于同一个函数值搜索多次是没有必要的，因此我们可以每求出一个函数的值便可将其用数组保存下来，到了下次要用的时候直接从数组里调出来用就可以了。这样时间复杂度一下子降成了O(N*N){函数个数最多不超过N*N个。}记忆化搜索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;动态规划问题具有以下基本特征：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)最长不下降序列设有整数序列b1,b2,b3,…,bm，若存在下标i1i2i3…in，且bi1bi2bi3…bin，则称b1,b2,b3,…,bm中有长度为n的不下降序列bi1,bi2,bi3,…,bin。求序列b1,b2,b3,…,bm中所有长度(n)最大不下降子序列输入：整数序列。输出：最大长度n和所有长度为n的序列个数。分析（1）设f(i)为前i个数中的最大不下降序列长度,则f(i)=max{f(j)+1}(1=ji=m,bjbi)边界为F(1)=1(2)设t(i)为前i个数中最长不下降序列的个数,则t(i)=∑t(j)(1=ji=m,bjbi,f(i)=f(j)-1)初始为t(i)=1当f(i)=n时，将t(i)累加举例：1234658109f:123455677t:111111222答案：f=7时，边界为∑t=4进一步(3)求本质不同的最长不下降序列个数有多少个？如：1234658109有，12346810,12345810,1234689,1234589都是本质不同的。但对于1223354f1223344t1112244答案有8个，其中4个1235，4个1234改进算法上例显然对于相两个相同的数，重复算了多次因此，我们对算法进行改进：对原序列按b从小到大（当bi=bj时按F从大到小）排序，增设Order(i)记录新序列中的i个数在原序列中的位置。可见，求t(i)时，当f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)Order(i)时，便不累加t(j)。这样就避免了重复。上述算法的时间复杂度为O(n2)进一步(3)求本质不同的最长上升序列个数有多少个？如：1234658109有，12346810,12345810,1234689,1234589都是本质不同的。但对于1223354f1223344t1112244答案有8个，其中4个1235，4个1234改进算法上例显然对于两个相同的数，重复算了多次因此，我们对算法进行改进：对原序列按b从小到大（当bi=bj时按F从大到小）排序，增设Order(i)记录新序列中第i个数在原序列中的位置。可见，求t(i)时，当f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)Order(i)时，便不累加t(j)。这样就避免了重复。上述算法的时间复杂度为O(n2)有一条河从东向西将某地区分为南北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）的