第四章5(贪心、动态)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第 四 章 基本的算法策略,4.5,动态规划,4.5.1,认识动态规划,4.5.2,算法框架,4.5.3,突出阶段性的动态规划应用,4.5.4,突出递推的动态规划应用,在动态规划算法策略中，体现在它的决策不是线性的而是全面考虑不同的情况分别进行决策,并通过多阶段决策来最终解决问题。在各个阶段采取决策后,会不断决策出新的数据,直到找到最优解,.,每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，故有,“,动态,”,的含义。所以，这种多阶段决策最优化的解决问题的过程称为,动态规划,。,上节,下节,4.5,动态规划,我们通过一个简单的例子来说明动态规划的多阶段决策与贪婪算法有什么区别。,【,例,1,】,数塔问题,上节,下节,4.5.1,认识动态规划,【,例,1】,数塔问题,有形如图,4-11,所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。,问题分析,算法设计,算法,小结,问题分析,这个问题用贪婪算法有可能会找不到真正的最大和。以图,4-11,为例就是如此。用贪婪的策略，则路径和分别为：,9+15+8+9+10=51,（自上而下），,19+2+10+12+9=52,（自下而上）。,都得不到最优解，真正的最大和是：,9+12+10+18+10=59,。,在知道数塔的全貌的前提下，可以用,枚举法,或下一章将学习的搜索算法来完成。,上节,下节,算法设计,动态规划设计过程如下：,1.,阶段划分：,第一步对于第五层的数据，我们做如下五次决策：,对经过第四层,2,的路径选择第五层的,19,，,对经过第四层,18,的路径选择第五层的,10,，,对经过第四层,9,的路径也选择第五层的,10,，,对经过第四层,5,的路径选择第五层的,16,。,上节,下节,以上的决策结果将五阶数塔问题变为,4,阶子问题，递推,出第四层与第五层的和为,:,21(2+19),28(18+10),19(9+10),21(5+16),。,用同样的方法还可以将,4,阶数塔问题,变为,3,阶数塔问题。,最后得到的,1,阶数塔问题，就是整个问题的最优解。,上节,下节,2,存储、求解：,1),原始信息存储,原始信息有层数和数塔中的数据，层数用一个整型,变量,n,存储，数塔中的数据用二维数组,data,，,存储成如,下的下三角阵,:,9,12 15,10 6 8,2 18 9 5,19 7 10 4 16,上节,下节,2),动态规划过程存储,必需用二维数组,a,存储各阶段的决策结果。二维数组,a,的存储内容如下：,dnj=datanj j=1,2,n,；,i=n-1,n-2,1,，,j=1,2,i,；,时,dij=max(di+1j,，,di+1j+1)+dataij,最后,a11,存储的就是问题的结果。,上节,下节,3),最优解路径求解及存储,仅有数组,data,和数组,a,可以找到最优解的路径， 但需要自顶向下比较数组,data,和数组,a,是可以找到。如图,4.5.2,求解和输出过程如下：,上节,下节,输出,a119,b=d11-data11=59-9=50,b,与,d21,d22,比较,b,与,d21,相等输出,data2112,b=d21-data21=50-12=38,b,与,d31,d32,比较,b,与,d31,相等输出,data3110,b=a31-data31=38-10=28,b,与,d41,d42,比较,b,与,d42,相等输出,data4218,b=d42-data42=28-18=10 b,与,d52,d53,比较,b,与,d53,相等输出,data5310“,上节,下节,数组,data,数组,d,9 59,12 15 50 49,10 6 8 38 34 29,2 18 9 5 21 28 19 21,19 7 10 4 16 19 7 10 4 16,图,4-12,数塔及动态规划过程数据,上节,下节,为了设计简洁的算法，我们最后用三维数组,a50503,存储以上确定的三个数组的信息。,a50501,代替数组,data,，,a50502,代替数组,d,a50503,记录解路径。,上节,下节,数塔问题的算法,main( ),int,a50503,i,j,n; print( please input the number of rows:); input(n);,for( i=1 ;i=1;i-) for (j=1 ;j= i ;j+),if (ai+1j2ai+1j+12), aij2=aij2+ai+1j2; aij3=0;,else, aij2=aij2+ai+1j+12; aij3=1;print(max=,a112);j=1;for( i=1 ;i);,j=j+aij3; print (anj1);,上节,下节,从例子中可以看到：,动态规划,=,贪婪策略,+,递推,(,降阶,)+,存储递推结果,贪婪策略、递推算法都是在“线性”地解决问题，而动态规划则是全面分阶段地解决问题。可以通俗地说动态规划是“,带决策的多阶段、多方位的递推算法,”。,上节,下节,1.,适合动态规划的问题特征,动态规划算法的问题及决策应该具有三个性质：最优,化原理、无后向性、子问题重叠性质。,1),最优化原理,(,或称为最佳原则、,最优子结构,),。,2),无后向性,(,无后效性,),。,3),有,重叠子问题,。,上节,下节,4.5.2,算法框架,2.,动态规划的基本思想,动态规划方法的基本思想是，把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。,最后一个子问题就是初始问题的解,。,由于动态规划的问题有,重叠子问题,的特点，为了减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。,上节,下节,3.,设计动态规划算法的基本步骤,设计一个标准的动态规划算法的步骤：,1),划分阶段,2),选择状态,3),确定决策并写出状态转移方程,但是,实际应用当中的简化步骤：,1),分析最优解的性质，并刻划其结构特征。,2),递推地定义最优值。,3),以自底向上的方式或自顶向下的记忆化方法,(,备忘录,法,),计算出最优值,.,4),根据计算最优值时得到的信息，构造问题的最优解。,上节,下节,4.,标准动态规划的基本框架,for( j=1 ;j=1;i=i-1) /,其它,n-1,个阶段,for (j=1 ;j=f(i) ;j=j+1)/ f(i),与,i,有关的表达式,x,i,j,=max(,或,min)g(x,i-1,j,1,j,2,),，,，,g(x,i-1,j,k,j,k+1,),；,t=g(x,1,j,1,j,2,); /,由最优解求解最优解的方案,print(x,1,j,1,);for( i=2 ;i=f(i) ;j=j+1),if(t=,x,i,j,i,) break;,上节,下节,【,例,2】,资源分配问题。,【,例,3】,n,个矩阵连乘的问题。,上节,下节,4.5.3,突出阶段性的动态规划应用,【,例,2】,资源分配问题。,设有资源,a,分配给,n,个项目,gi(x,),为第,i,个项目分得资源,x,所得到的利润。求总利润最大的资源分配方案，也就是解下列问题：,max z=g1(x1)+ g2(x2)+,gn(xn,),x1+xx2+x3+,xn,=a, xi0,i=1,，,2,3,n,函数,gi(x,),以数据表的形式给出,.,例如：现有,7,万元投资到,A,，,B,，,C,三个项目，利润见表,求问题总利润最大的资源分配方案。,上节,下节,算法设计,1,阶段划分及决策,比较直观的阶段划分就是,逐步,考虑,每一个项目,在不,同投资额下的利润情况。,3.,数据结构设计：,1),开辟一维数组,q,来存储原始数据。,2),另开辟一维数组,f,存储当前最大收益情况。,3),开辟记录中间结果的一维数组数组,temp,，,记录正在计,算的最大收益。,4),开辟二维数组,a,。,5),数组,gain,存储第,i,个工程投资数的最后结果。,上节,下节,对于一般问题设计,算法,如下,：,main( ) ,int,i,j,k,m,n,rest;,int,a100100,，,gain100; float q100,f100,temp100; print(“How,mang,item? ”); input (m);,print(“How,mang,money? ”); input (n);,print(“input gain table:”);,for( j=0;j= n;j+) input(qj); fj=qj; for( j=0;j= n;j+) a1,j=j;,上节,下节,for( k=2;k=m;k+) for( j=0;j= n;j+) tempj=qj; input(qj); akj=0; for( j=0 ;j= n;j+),for( i=0 ;itempj,）, tempj=fj-i+qi; ak,j=i; ,for(j=0;j=1;i-), gaini=airest; rest=rest-gaini;,for(i=1;i=m;i+) print(gaini,” ”); print(fn); ,【,例,3】,n,个矩阵连乘的问题,。,问题分析,算法设计,算法,1,(,递归算法,),算法,1,说明,算法,2,(,递归算法,),算法,3,(,非递归算法,),输出算法,上节,下节,问题分析,多个矩阵连乘,运算是满足结合律的。,例,:,M15*20 * M220*50 * M350*1 * M41*100,分别按,(M1*M2)*M3)*M4,，,M1*(M2*(M3*M4),，,(M1*(M2*M3)*M4,的次序相乘,各需进行,5750, 115000, 1600,次乘法。,这个问题要用,“,动态规划,”,算法来完成,:,首先,从两个矩阵相乘的情况开始；,然后,尝试三个矩阵相乘的情况；,最后,等到,n,个矩阵相乘所用的最少的乘法次数及结合方式。,上节,下节,算法设计,1.,阶段划分,1,）初始状态为一个矩阵相乘的计算量为,0;,2,）第二阶段,计算两个相邻矩阵相乘的计算量,共,n-1,组,3,）第三阶段,计算两个相邻矩阵相乘的计算量,共,n-2,组,4,）最后一个阶段,是,n,个相邻矩阵相乘的计算量,共,1,组,是问题解。,上节,下节,2.,阶段决策,一般地，计算,M1*M2*M3*,Mn,其中,M1,，,M2,，,Mi,分别是,r1*r2,，,r2*r3,，,ri,*ri+1,阶矩阵，,i=1,2,3,n,。,设,mi,j,是计算,Mi*Mi+1*,Mj,的最少乘法次数,(1ijn),对,mi,j,有公式：,0,当,i=j,时,ri-1*,ri,*ri+1,当,j=i+1,时,min(mi,k+mk+1,j+rirk+1rj+1) ikj,当,ij,时,以上动态规划方法是按,s=0,1,2,3,.,n-1,的顺序计算,mi,i+s,的。,3.,记录最佳期方案,用二维矩阵,comij(n,*n),来存储使,mij,为最小值时的,k,值。,上节,下节,算法,1,(,递归算法,),int,r100,com100100;,main,（ ）,int,n,i;,print(“How,mang,matrixes?”); input (n);,peint(“How,size every,matrixe,?”);,for (i=1;i=n+1;i+) input (ri);,print (“The least calculate quantity,：”, course (1,n);,for (i=1;i=n;i+), print(“,换行符”,);,for (j=1;j=n;j+),print(comij); ,上节,下节,int,course(int,i,int,j),int,u,t;,if (i=j) return 0;,if (i=j-1), comii+1=i; return,（,ri*ri+1*rr+2,）,;,u= course(i,i) + course(i+1,j)+ ri*ri+1*rj+1;,comij = i;,for (,int,k = i+1; k j; k+), t = course(i,k) + course(k+1,j)+ri*rk+1*rj+1;,if (tu) u= t; comij = k; ,return u;,上节,下节,算法,1,说明,以上的递归算法虽然解决了问题，但效率很低，有,子问题重叠,，,n=4,时的递归过程如下图：,上节,下节,算法,2,(,改进后递归算法,),int,m100100,com100100,r100;,matrix2,（ ）,int,n,;,print(“How,mang,matrixes?”); input (n);,print(“How size every,matrixe,?”);,for (i=1;i=n+1;i+) input (ri);,for (i=1;i=n;i+) /,初始化化数组,com,和,m,。,/,for (j=1;j=n;j+), comij=0; mij=0; ,course (1,n),；,print (“The least calculate quantity,：”,m1n);,for (i=1;i=n;i+), print(“,换行符”,);,for (j=1;j0,）,return mij;,if(i=j) return 0;,if(i=j-1), comii+1=i; mij= ri*ri+1*ri+2; return mij; ,int,u= course (i,i)+ course (i+1,j)+ri*ri+1*rj+1;,comij=i ;,for (,int,k=i+1; kj;k+),int,t= course (i,k)+ course (k+1,j)+ri*rk+1*rj+1;,if (tu) u=t ; comij=k; ,mij=u;,return u;,上节,下节,算法,3,(,非递归算法,),main,（ ）,int,n,r100,m100100,com100100;,peint(“How,mang,matrixes?”); input (n);,peint(“How,size every,matrixe,?”);,for (i=1;i=n+1;i+) input (ri);,for (i=1;i=n;i+) /,初始化化数组,com,和,m,。,/,for (j=1;j=n;j+) comij=0;,for (i=1;in;i+), mii=0; s=0,mii+1= ri*ri+1*ri+2; s=1,comii+1 = i+1;,上节,下节,mnn= 0;,for ( s =2; s=n-1; s+) /,动态规划过程,/,for (i=1;in-s+1;i+), j=i+s; mij =mii +mi+1j + ri*ri+1*rj+1;,comij = i;,for (k=i+1;kj;k+), t=mik+mk+1j+ ri*rk+1*rj+1;,if (t mij) mij = t; comij= k; ,print (“The least calculate quantity,：”,m1n);,for (i=1;i=n;i+), print(“,换行符”,);,for (j=1;j=n;j+) print(comij); ,上节,下节,输出部分的算法设计,以上算法中关于矩阵相乘的结合方式，只是简单的输出了数组,com,的内容，不容易直观地被利用，还需要继续进行必要的人工处理，才能真正找到矩阵相乘的结合方式。怎么样更直观、合理地输出结合过程？即算法的输出能使用户直接了解计算矩阵的过程。,首先看一下,com,数组存储的信息意义，它是一个二维数组，元素,comij,存储的是,M,i,M,j,相乘的组合点,k1,，,也就是说：,M,i,*M,i+1,*,*,M,j,是由,M,i,*M,i+1,*,M,k,和,M,k+1,*,M,j,同样，在数组,com,中我们也能找到,M,i,M,k,相乘的组合点,k2,，,M,k+1,M,j,相乘的组合点,k3,，,。,从数组信息中找到了大规模问题与小规模问题的递归关系：,输出算法,记,k1=com1n,，,则最后一次运算的结合过程是,M1*,*Mk1,和,Mk1+1*,*,Mn,记,k2=com1k1,，,M1*,*Mk1,的结合过程是,M1*,*Mk2,和,Mk2+1*,*Mk1,combine(int,i,int,j), if ( i=j) return;,combine (i, comij);,combine (comij+1, j);,print,（,M,i ,“*M”,，,comij,）,;,print,（, and M,comij+1, “*M”,，,j,）,;,上节,下节,这一节问题的,设计角度是从递推思想进行,的,设计中只要找出大规模问题与小规模问题,(,子问题,),之间的递推关系,最后一个子问题所得最优解就是原问题的最优解。,【,例,4】,求两个字符序列的最长公共字符子序列,。,【,例,5】,最长不降子序列,。,上节,下节,4.5.4,突出递推的动态规划应用,【,例,4】,求两个,字符序列,的,最长,公共字符子序,列。,问题分析,算法设计,算法,(,递归形式,),算法,(,非递归,),上节,下节,问题分析,若,A,的长度为,n,，若,B,的长度为,m,，,则,A,的子序列共有：,Cn1+Cn2+ Cn3+,Cnn,=2n-1,B,的子序列共有：,Cm1+Cm2+ Cm3+,Cmm,=2m-1,如采用枚举策略，当,m=n,时，共进行串比较：,Cn1*Cm1+Cn2*Cm2+Cn3*Cm3+,Cnn,*,Cnn,0,且,ai-1=bj-1,；,3,）,cij=max(cij-1,ci-1j),如果,i,j0,且,ai-1bj-1,。,上节,下节,算法,(,递归形式,),int,Num=100char,aNum,bNum,strNum,;,main( ) ,int,m,n,k;,print(“Entertwostring”); input(a,b);,m=,strlen(a,);,n=,strlen(b,), k=,lcs_len(n,m,);,buile_lcs,(k, n,m);,print(str,); ,上节,下节,lcs_len(int,i,，,j) /,计算最优值, if ( i=0 or j=0) cij=0;,else if (ai-1=bj-1) cij=lcs_len(i-1,，,j-1)+1;,else cij=max,（,lcs_len(i,，,j-1),，,lcs_len(i-1,，,j);,buile_lcs,(k,i,j); /,构造最长公共子序列, if,（,i=0 or j=0,）,return; if,（,cij=ci-1j,）,buile_lcs,(k,i-1,j);,else if,（,cij=cij-1,）,buile_lcs,(k,i,j-1);,else ,strk,= ai-1;,buile_lcs,(k-1, i-1,j-1); ,上节,下节,算法,(,非递归,),n=100char,an,bn,strn,;,lcs_len(char,a,charb,int,cn) /,计算最优值,int,m,n,i,j; print(“Entertwostring”); input(a,b);,m=,strlen(a,); n=,strlen(b,);,for(i=0;i=cij-1)cij=ci-1j; else cij=cij-1; ,buile_lcs,( ) /,构造最长公共子序列,int,k,i=,strlen(a,),j=,strlen(b,);k=,lcs_len,( );,strk,=,;while(k0)if(cij=ci-1j) i=i-1;elseif(cij=cij-1) j=j-1; else,k=k-1;,strk,=ai-1; j=j-1;,上节,下节,【,例,5】,最长不降子序列,设有由,n,个不相同的整数组成的数列，记为,:,a(1),、,a(2),、,、,a(n),且,a(i)a(j) (ij),若存在,i1i2i3,ik,且有,a(i1)a(i2),a(ik,),，,则称为长度为,k,的不下降序列。请求出一个数列的最长不下降序列。,算法设计,算法,(,逆推法,),上节,下节,算法设计,1.,递推关系,1),对,a(n),来说，由于它是最后一个数，所以当从,a(n),开始查找,时,只存在长度为,1,的不下降序列；,2),若从,a(n-1),开始查找，则存在下面的两种可能性：,(1),若,a(n-1)a(n),则存在长度为,1,的不下降序列,a(n-1),或,a(n),。,3),一般若从,a(i),开始,此时最长不下降序列应该按下列方法求出,:,在,a(i+1),a(i+2),a(n),中，找出一个比,a(i),大的且最,长的不下降序列，作为它的后继。,上节,下节,算法,(,逆推法,),int,maxn,=100;,int,amaxn,bmaxn,cmaxn,;main(),int,n,i,j,max,p; input(n); for (i = 1;i =1; i=i-1) max=0; p=0; for(j=i+1; jmax),max=bj; p=j; if( p0 ) bi=bp+1; ci=p ;,max=0; p=0;for (i = 1;i max) max:=bi; p:=i ; ,print(maxlong,=,max); print (result is:);while (p0 ) print(ap); p:=cp; ,上节,下节,算法策略和算法是有区别的,它们是算法设计中的两个方面，,算法策略,是面向问题的,算法,是面向实现的；但二者又是不可分的,首先是通过算法策略才找出解决问题的算法，其次对于用不同算法求解的问题算法策略是自然不同的。,本章共介绍了五种算法策略,它们互相有着一定的差别，适应的问题也有所差异。,上节,下节,4.6,算法策略间的比较,“,贪婪算法,”,“,递推法,”,“,递归法,”,“,枚举法,”,“,递归回朔法,”,“,分治法,”,“,动态规划法,”,上节,下节,4.6.1,不同算法策略特点小结,“,贪婪算法,”,这些策略求解的是最简单的一类问题，或者说是对问题要求最严格的算法策略。,“,贪婪算法,”,解决这类问题是按一定顺序（从前向后或从后向前等）一定的策略，只需考虑当前局部信息就能做出决策，即所谓局部最优就是全局最优。,上节,下节,“,递推法,”,“,递推法,”,和贪婪算法一样也是由当前问题的逐步解决从而得到整个问题的解，只是依赖的是信息间本身的递推关系，每一步不需要策略参与到算法中，它们更多地用于计算。,上节,下节,“,递归法,”,和递推法类似，递归法是利用大问题与其子问题间的递归关系来解决问题的。能采用递归描述的算法通常有这样的特征：为求解规模为,N,的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模,N=1,时，能直接得解。,上节,下节,“,枚举法,”,枚举法既是一个策略，也是一个算法，也是一个分析问题的手段。枚举法的求解思路很简单,就是对所有可能的解逐一尝试，从而找出问题的真正解。当然这就要求所解的问题可能的解是,有限的、固定的,，不会产生组合爆炸、容易枚举的。多用于决策类问题。这类问题都不易进行问题的分解，只能,整体来求解,。,上节,下节,“,递归回朔法,”,类似于枚举法的思想,递归回朔法通过递归尝试遍问题各个可能解的通路，发现此路不通时回朔到上一步继续尝试别的通路。在下一章中对其应用做详细介绍。,上节,下节,“,分治法,”,求解的则是较复杂的问题，这类问题是可以被分解成,独立的子问题,来解决的，将两个或两个以上的独立子问题的解,“,合成,”,，就得到较大的子问题的解，最后合成为总问题的解。,上节,下节,“,动态规划法,”,动态规划法与贪心法类似,，是通过多阶段决策过程来解决问题的。但每个阶段决策的结果是一个决策结果序列，这个结果序列中最后采用哪一个结果取决于以后每个阶段决策，因此称为,“,动态,”,规划法。当然每一次的决策结果序列都必须进行存储。因此，可以说,“,动态规划是高效率、高消费的算法,”,。,另一方面，,动态规划法与分治法类似,，当问题不能分解为独立的子问题,但又符合最优化原理,(,最优子结构性质,),时,用动态规划，通过多阶段决策过程从逐步找出子问题的最优解，从而决策出问题的结果。,上节,下节,1.,对问题进行分解的算法策略,-,分治法,与,动态规划法,2.,多阶段过程,贪婪算法,、,递推法,、,递归法,和,动态规划法,3.,全面逐一尝试、比较,蛮力法,、,枚举法,、,递归回溯法,4,算法策略的中心思想,上节,下节,4.6.2,算法策略间的关联,1.,对问题进行分解的算法策略,-,“,分治法,”,与,“,动态规划法,”,“,分治法,”,与,“,动态规划法,”,都是,递归思想,的应用之一，是找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。区别在于：,上节,下节,分治法,所能解决的问题一般具有以下几个特征：,1),该问题的规模缩小到一定的程度就可以容易地解决；,2),该问题可以分解为若干个规模较小的相同问题，即该问,题具有。,3),利用该问题分解出的子问题的解可以合并为该问题的解,;,4),该问题所分解出的各个子问题是相互独立的，即子问题,之间不包含公共的子问题。,上节,下节,第一条特征是绝大多数问题都可以满足的,;,第二条特征是应用分治法的前提,它也是大多数问题可以满足的,;,第三条特征是关键。,第四条特征涉及到分治法的效率。,动态规划的,实质,是分治思想和解决冗余。,上节,下节,2,多阶段过程,“,贪婪算法,”,、,“,递推法,”,、,“,递归法,”,和,“,动态规划法,”,多阶段过程就是按一定顺序,(,从前向后或从后向前等,),一定的策略,逐步解决问题的方法。,“,贪婪算法,”,每一步根据策略得到一个结果传递到下一步，自顶向下，一步一步地作出贪心选择。,上节,下节,“,动态规划法,”,则根据一定的决策,每一步决策出的不是一个结果，而只是使问题的规模不断的缩小，如果决策比较简单,是一般的算法运算,则可找到不同规模问题间的关系，使算法演变成,“,递推法,”,、,“,递归法,”,算法,所以说动态规划更侧重算法设计策略，而不是算法。,“,递推法,”,、,“,递归法,”,更注重每一步之间的关系,决策的因素较少。,“,递推法,”,根据关系从前向后推,由小规模的结论,推解出问题的解。,“,递归法,”,根据关系先从后向前使大问题，转化为小问题，最后同样由小规模结论，推解出问题的解。,上节,下节,3,全面逐一尝试、比较,“,蛮力法,”,、,“,枚举法,”,、,“,递归回溯法,”,考虑到有这样一类问题，问题中不易找到信息间的相互关系，也不能分解为独立的子问题,似乎只有把各种可能情况都考虑到,并把全部解都列出来之后,才能判定和得到最优解。对于规模不大的问题，这些策略简单方便,;,而当问题的计算复杂度高且计算量很大时,还是考虑采用“动态规划法”这个更有效的算法策略,。,上节,下节,枚举法算法的实现,依赖于循环,通过循环嵌套枚举问题中各种可能的情况,如八皇后问题能用八重循环嵌套枚举。而对于规模,不固定,的问题就无法用固定重数的循环嵌套来枚举了,有的问题可能通过变换枚举对象也能用循环嵌套枚举实现,但更多的任意指定规模的问题是靠递归回朔法来,“,枚举,”,或,“,遍历,”,各种可能的情况。比如,n,皇后问题只能用,“,递归回朔法,”,通过递归实现（当然可以通过栈,而不用递归）。,上节,下节,4,算法策略的中心思想,所有算法策略的中心思想就是用算法的基本工具循环机制和递归机制实现算法。递推法自然不用多说，贪婪算法就是逐步决策解决问题，动态规划也是。,上节,下节,4.6.3,算法策略侧重的问题类型,一般我们在实际应用中遇到的问题主要分为四类,:,判定性问题、计算问题、最优化问题和构造性问题。,递推法,、,递归法,算法较适合解决判定性问题、计算问题。,“,贪婪算法,”、“,分治法,” 、“,动态规划法,” 与“,枚举法,”,较适合,解最优化问题。,构造性问题更多地依赖于人的经验和抽象能力，算法一般是,人类智能充分对问题解决步骤细化后才能得到算法，少有通用的,算法策略。当然也有一些问题在构造过程中使用通用的算法策略。,上节,下节,下面就最优化问题讨论如下：,在现实生活中，有这样的问题：他有,n,个输入,而他的解就由,n,个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。把那些必须满足的条件称为,约束条件,;,而把满足约定条件的子集称为该问题的,可行解,。显然,满足约束条件的子集可能不止一个,因此，可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也给出了一定的标准,这些标准一般以函数形式给出,这些函数称为,目标函数,。 那些使目标函数取极值的可行解， 称为,最优解,这一类需求取最优解的问题,又可根据描述约束条件和目标函数的 数学模型的特性或求借问题方法的不同,进行而细分为,线形规则,、,整数规则,、,非线形规则,、,动态规划,等,问题。,上节,下节,尽管各类规划问题都有一些相应的求解方法，但其中的某些问题，还可用一种更直接的方法来求解，这种方法就叫,贪心方法,。,动态规划法,是将问题实例归纳为更小的、 相似的子问题,并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题。 而,分治法,中的各个子问题是独立的,(,即不包含公共的子子问题,),因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是,如果当前选择可能要依赖子问题的解时,则难以通过局部的贪心策略达到全局最优解,;,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题。,上节,下节,动态规划在解决不独立子问题时，是分为若干个阶段进行的,而且在任一阶段后的行为都仅依赖,i,阶段的过程状态,而与,i,阶段之前的过程如何达到这种状态的方法无关,这样的过程就构成一个,多阶段决策过程,。 动态规划不仅求出了当前状态到目标状态的最优值,而且同时求出了到中间状态的最优值。,显然,用枚举的方法从所有可能的决策序列中选取最优决策序列是一种最笨的方法。,上节,下节,最优性原理,指出,过程的,最优序列,有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。,如果求解问题的最优性原理成立,则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获得各阶段间的递推关系式。因此,从某种意义上说,动态规划是一种找出子问题间递推或递归关系的方法,。,动态规划相比一般穷举也存在一定,缺点,:,空间占据过多,但对于空间需求量不大的题目来说,动态规划无疑是最佳方法！,上节,下节,