第四章5(贪心、动态)

1、第第 四四 章章 基本的算法策略基本的算法策略4.5 4.5 动态规划动态规划 4.5.1 4.5.1 认识动态规划认识动态规划 4.5.2 4.5.2 算法框架算法框架 4.5.3 4.5.3 突出阶段性的动态规划应用突出阶段性的动态规划应用 4.5.4 4.5.4 突出递推的动态规划应用突出递推的动态规划应用 在动态规划算法策略中，体现在它的决策不是线性的而是在动态规划算法策略中，体现在它的决策不是线性的而是全面考虑不同的情况分别进行决策全面考虑不同的情况分别进行决策, , 并通过多阶段决策来最并通过多阶段决策来最终解决问题。在各个阶段采取决策后终解决问题。在各个阶段采取决策后, , 会不

2、断决策出新的数会不断决策出新的数据据, ,直到找到最优解直到找到最优解. .每次决策依赖于当前状态每次决策依赖于当前状态, , 又随即引起又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，状态的转移。一个决策序列就是在变化的状态中产生出来的，故有故有“动态动态”的含义。所以，这种多阶段决策最优化的解决的含义。所以，这种多阶段决策最优化的解决问题的过程称为问题的过程称为动态规划动态规划。 上节上节 下节下节4.5 4.5 动态规划动态规划 我们通过一个简单的例子来说明动态规划的多阶段决策与贪婪算法有什么区别。 【例【例1】 数塔问题数塔问题 上节 下节4.5.1 认识动态规划【例【

3、例1 1】数塔问题数塔问题 有形如图4-11所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。 问题分析算法设计算法小结 问题分析问题分析 这个问题用贪婪算法有可能会找不到真正的最大和。以图4-11为例就是如此。用贪婪的策略，则路径和分别为： 9+15+8+9+10=51 （自上而下）， 19+2+10+12+9=52（自下而上）。都得不到最优解，真正的最大和是： 9+12+10+18+10=59。 在知道数塔的全貌的前提下，可以用枚举法或下一章将学习的搜索算法来完成。 上节 下节 算法设计算法设计 动态规划设计过程如下：动态

4、规划设计过程如下： 1.1.阶段划分：阶段划分： 第一步对于第五层的数据，我们做如下五次决策：第一步对于第五层的数据，我们做如下五次决策： 对经过第四层对经过第四层2 2的路径选择第五层的的路径选择第五层的1919， 对经过第四层对经过第四层1818的路径选择第五层的的路径选择第五层的1010， 对经过第四层对经过第四层9 9的路径也选择第五层的的路径也选择第五层的1010， 对经过第四层对经过第四层5 5的路径选择第五层的的路径选择第五层的1616。 上节上节 下节下节 以上的决策结果将五阶数塔问题变为以上的决策结果将五阶数塔问题变为4 4阶子问题，递推阶子问题，递推出第四层与第五层的和为出

5、第四层与第五层的和为: : 21(2+19),28(18+10),19(9+10),21(5+16) 21(2+19),28(18+10),19(9+10),21(5+16)。 用同样的方法还可以将用同样的方法还可以将4 4阶数塔问题阶数塔问题, ,变为变为3 3阶数塔问题。阶数塔问题。 最后得到的最后得到的1 1阶数塔问题，就是整个问题的最优解。阶数塔问题，就是整个问题的最优解。 上节上节 下节下节 2 2存储、求解：存储、求解： 1) 1) 原始信息存储原始信息存储 原始信息有层数和数塔中的数据，层数用一个整型原始信息有层数和数塔中的数据，层数用一个整型 变量变量n n存储，数塔中的数据用

6、二维数组存储，数塔中的数据用二维数组datadata，存储成如，存储成如 下的下三角阵下的下三角阵: : 9 9 12 15 12 15 10 6 8 10 6 8 2 18 9 5 2 18 9 5 19 7 10 4 16 19 7 10 4 16 上节上节 下节下节 2) 2) 动态规划过程存储动态规划过程存储 必需用二维数组必需用二维数组a a存储各阶段的决策结果。二维数组存储各阶段的决策结果。二维数组a a的存储内容如下：的存储内容如下： dnj=datanj j=1,2,ndnj=datanj j=1,2,n； i=n-1,n-2,1i=n-1,n-2,1，j=1,2,ij=1,2

7、,i；时；时 dij=max(di+1jdij=max(di+1j，di+1j+1)+dataijdi+1j+1)+dataij 最后最后a11a11存储的就是问题的结果。存储的就是问题的结果。 上节上节 下节下节3) 3) 最优解路径求解及存储最优解路径求解及存储 仅有数组仅有数组datadata和数组和数组a a可以找到最优解的路径，可以找到最优解的路径， 但需要但需要自顶向下比较数组自顶向下比较数组datadata和数组和数组a a是可以找到。如图是可以找到。如图4.5.24.5.2求解求解和输出过程如下：和输出过程如下： 上节上节 下节下节 输出输出a119a119 b=d11-dat

8、a11=59-9=50 b=d11-data11=59-9=50 b b与与d21,d22 d21,d22 比较比较 b b与与d21d21相等输出相等输出data2112data2112 b=d21-data21=50-12=38 b=d21-data21=50-12=38 b b与与d31,d32 d31,d32 比较比较 b b与与d31d31相等输出相等输出data3110data3110 b=a31-data31=38-10=28 b=a31-data31=38-10=28 b b与与d41,d42 d41,d42 比较比较 b b与与d42d42相等输出相等输出data4218da

9、ta4218 b=d42-data42=28-18=10 b b=d42-data42=28-18=10 b与与d52,d53 d52,d53 比较比较 b b与与d53d53相等输出相等输出data5310“data5310“ 上节上节 下节下节 数组数组datadata 数组数组d d 9 59 9 59 12 15 50 49 12 15 50 49 10 6 8 38 34 29 10 6 8 38 34 29 2 18 9 5 21 28 19 21 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 10 4 16 19 7 10 4 16 19 7 10

10、 4 16 图图4-12 4-12 数塔及动态规划过程数据数塔及动态规划过程数据 上节上节 下节下节 为了设计简洁的算法，我们最后用三维数组为了设计简洁的算法，我们最后用三维数组a50503a50503存储以上确定的三个数组的信息。存储以上确定的三个数组的信息。 a50501a50501代替数组代替数组datadata， a50502a50502代替数组代替数组d, d, a50503 a50503记录解路径。记录解路径。 上节上节 下节下节 数塔问题的算法数塔问题的算法main( )main( ) int a50503,i,j,n; int a50503,i,j,n; print( plea

11、se input the number of rows:); print( please input the number of rows:); input(n); input(n);for( i=1 ;i=n;i+)for( i=1 ;i=1;i-)for (i=n-1 ; i=1;i-) for (j=1 ;j= i ;j+) for (j=1 ;j= i ;j+)if (ai+1j2ai+1j+12) if (ai+1j2ai+1j+12) aij2=aij2+ai+1j2; aij2=aij2+ai+1j2; aij3=0; aij3=0; elseelse aij2=aij2+ai+

12、1j+12; aij2=aij2+ai+1j+12; aij3=1; aij3=1;print(max=,a112);print(max=,a112);j=1;j=1;for( i=1 ;i= n-1;i+)for( i=1 ;i); print(aij1,-); j=j+aij3; j=j+aij3; print (anj1);print (anj1); 上节上节 下节下节从例子中可以看到：从例子中可以看到： 动态规划动态规划= =贪婪策略贪婪策略+ +递推递推( (降阶降阶)+)+存储递推结果存储递推结果 贪婪策略、递推算法都是在贪婪策略、递推算法都是在“线性线性”地解决问题，而动态地解决

13、问题，而动态规划则是全面分阶段地解决问题。可以通俗地说动态规划是规划则是全面分阶段地解决问题。可以通俗地说动态规划是“带决策的多阶段、多方位的递推算法带决策的多阶段、多方位的递推算法”。 上节上节 下节下节 1.适合动态规划的问题特征 动态规划算法的问题及决策应该具有三个性质：最优 化原理、无后向性、子问题重叠性质。1) 最优化原理(或称为最佳原则、最优子结构)。 2) 无后向性(无后效性)。 3) 有重叠子问题。 上节 下节4.5.2 算法框架2. 动态规划的基本思想 动态规划方法的基本思想是，把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。最后一个子问题就是初始问题的解。 由

14、于动态规划的问题有重叠子问题的特点，为了减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。 上节 下节3. 设计动态规划算法的基本步骤 设计一个标准的动态规划算法的步骤： 1) 划分阶段 2) 选择状态 3) 确定决策并写出状态转移方程 但是,实际应用当中的简化步骤： 1) 分析最优解的性质，并刻划其结构特征。 2) 递推地定义最优值。 3) 以自底向上的方式或自顶向下的记忆化方法(备忘录 法)计算出最优值. 4) 根据计算最优值时得到的信息，构造问题的最优解。 上节 下节4. 标准动态规划的基本框架for( j=1 ;j=1;i=i-1) /其它其它n-1个阶

15、段个阶段 for (j=1 ;j=f(i) ;j=j+1)/ f(i)与与 i有关的表达式有关的表达式 xij=max(或或min)g(xi-1j1j2)， g(xi-1jkjk+1)；t=g(x1j1j2); /由最优解求解最优解的方案由最优解求解最优解的方案print(x1j1);for( i=2 ;i=f(i) ;j=j+1) if(t= xiji) break; 上节 下节 【例【例2 2】 资源分配问题。 【例【例3 3】 n个矩阵连乘的问题。 上节 下节4.5.3 突出阶段性的动态规划应用【例【例2 2】资源分配问题。资源分配问题。 设有资源设有资源a,a,分配给分配给n n个项目

16、个项目,gi(x),gi(x)为第为第i i个项目分得资源个项目分得资源x x所得到的利润。求总利润最大的资源分配方案，也就是解下所得到的利润。求总利润最大的资源分配方案，也就是解下列问题：列问题： max z=g1(x1)+ g2(x2)+gn(xn)max z=g1(x1)+ g2(x2)+gn(xn) x1+xx2+x3+xn=a, xi0,i=1 x1+xx2+x3+xn=a, xi0,i=1，2,3,n2,3,n函数函数gi(x)gi(x)以数据表的形式给出以数据表的形式给出. .例如：现有例如：现有7 7万元投资到万元投资到A A，B B，C C 三个项目，利润见表三个项目，利润见

17、表, ,求问求问题总利润最大的资源分配方案。题总利润最大的资源分配方案。 上节上节 下节下节 算法设计算法设计1 1阶段划分及决策阶段划分及决策 比较直观的阶段划分就是比较直观的阶段划分就是逐步逐步考虑考虑每一个项目每一个项目在不在不 同投资额下的利润情况。同投资额下的利润情况。3. 3. 数据结构设计：数据结构设计： 1) 1) 开辟一维数组开辟一维数组q q来存储原始数据。来存储原始数据。 2) 2) 另开辟一维数组另开辟一维数组f f存储当前最大收益情况。存储当前最大收益情况。 3) 3) 开辟记录中间结果的一维数组数组开辟记录中间结果的一维数组数组temptemp，记录正在计，记录正在

18、计 算的最大收益。算的最大收益。 4) 4) 开辟二维数组开辟二维数组a a。 5) 5) 数组数组gaingain存储第存储第i i个工程投资数的最后结果。个工程投资数的最后结果。 上节上节 下节下节对于一般问题设计对于一般问题设计算法算法如下如下：main( ) main( ) int i,j,k,m,n,rest; int i,j,k,m,n,rest; int a100100 int a100100，gain100;gain100; float q100,f100,temp100; float q100,f100,temp100; print(“How mang item? ”); i

19、nput (m); print(“How mang item? ”); input (m); print(“How mang money? ”); input (n); print(“How mang money? ”); input (n); print(“input gain table:”); print(“input gain table:”); for( j=0;j= n;j+) for( j=0;j= n;j+) input(qj); fj=qj; input(qj); fj=qj; for( j=0;j= n;j+) for( j=0;j= n;j+) a1,j=j; a1,j=

20、j; 上节上节 下节下节for( k=2;k=m;k+)for( k=2;k=m;k+) for( j=0;j= n;j+) for( j=0;j= n;j+) tempj=qj; input(qj); akj=0; tempj=qj; input(qj); akj=0; for( j=0 ;j= n;j+) for( j=0 ;j= n;j+) for( i=0 ;i=j;i+)for( i=0 ;itempjfj-i+qitempj） tempj=fj-i+qi; ak,j=i; tempj=fj-i+qi; ak,j=i; for(j=0;j= n;j+) for(j=0;j=1;i-)

21、 for(i=m;i=1;i-) gaini=airest; rest=rest-gaini; gaini=airest; rest=rest-gaini; for(i=1;i=m;i+) print(gaini,” ”); for(i=1;i=m;i+) print(gaini,” ”); print(fn); print(fn); 【例3】n个矩阵连乘的问题。 问题分析 算法设计 算法1(递归算法) 算法1说明 算法2(递归算法) 算法3(非递归算法) 输出算法 上节 下节 问题分析问题分析 多个矩阵连乘多个矩阵连乘运算是满足结合律的。运算是满足结合律的。例例: : M15 M15* *2

22、0 20 * * M220 M220* *50 50 * * M350 M350* *1 1 * * M41 M41* *100100分别按分别按 (M1(M1* *M2)M2)* *M3)M3)* *M4M4，M1M1* *(M2(M2* *(M3(M3* *M4)M4)，(M1(M1* *(M2(M2* *M3)M3)* *M4M4 的次序相乘的次序相乘, ,各需进行各需进行 5750, 115000, 16005750, 115000, 1600次乘法。次乘法。 这个问题要用这个问题要用“动态规划动态规划”算法来完成算法来完成: : 首先首先, ,从两个矩阵相乘的情况开始；从两个矩阵相乘

23、的情况开始； 然后然后, ,尝试三个矩阵相乘的情况；尝试三个矩阵相乘的情况； 最后最后, ,等到等到n n个矩阵相乘所用的最少的乘法次数及结合方式。个矩阵相乘所用的最少的乘法次数及结合方式。 上节上节 下节下节 算法设计算法设计 1. 1. 阶段划分阶段划分 1 1）初始状态为一个矩阵相乘的计算量为）初始状态为一个矩阵相乘的计算量为0;0;2 2）第二阶段）第二阶段, ,计算两个相邻矩阵相乘的计算量计算两个相邻矩阵相乘的计算量, , 共共n-1n-1组组3 3）第三阶段）第三阶段, ,计算两个相邻矩阵相乘的计算量计算两个相邻矩阵相乘的计算量, , 共共n-2n-2组组 4 4）最后一个阶段）最

24、后一个阶段, ,是是n n个相邻矩阵相乘的计算量个相邻矩阵相乘的计算量, ,共共1 1组组, , 是问题解。是问题解。 上节上节 下节下节2. 2. 阶段决策阶段决策 一般地，计算一般地，计算M1M1* *M2M2* *M3M3* * *Mn Mn 其中其中M1M1，M2M2，,Mi,Mi分别是分别是 r1r1* *r2r2，r2r2* *r3r3，,ri,ri* *ri+1ri+1阶矩阵，阶矩阵，i=1,2,3,ni=1,2,3,n。 设设mi,jmi,j是计算是计算MiMi* *Mi+1Mi+1* *MjMj的最少乘法次数的最少乘法次数(1ijn),(1ijn),对对 mi,jmi,j有公

25、式：有公式： 0 0 当当i=ji=j时时 ri-1ri-1* *riri* *ri+1 ri+1 当当j=i+1j=i+1时时 min(mi,k+mk+1,j+rirk+1rj+1) ikj min(mi,k+mk+1,j+rirk+1rj+1) ikj 当当ijij时时 以上动态规划方法是按以上动态规划方法是按s=0,1,2,3,.,n-1s=0,1,2,3,.,n-1的顺序计算的顺序计算mi,i+smi,i+s的。的。3.3.记录最佳期方案记录最佳期方案 用二维矩阵用二维矩阵comij(ncomij(n* *n)n)来存储使来存储使mijmij为最小值时的为最小值时的 k k 值。值。

26、上节上节 下节下节 算法算法1 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 cou

27、rse(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 1说明说明 以上的递归算法虽然解决了问题，但效率很低，有子问题重

28、叠，n=4时的递归过程如下图： 上节 下节 算法算法2 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 le

29、ast 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)

30、u=t ; comij=k; mij=u; return u; 上节 下节 算法算法3 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*r

31、i+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(“换行符换行符”);

32、 for (j=1;j=n;j+) print(comij); 上节 下节输出部分的算法设计以上算法中关于矩阵相乘的结合方式，只是简单的输出了数组com的内容，不容易直观地被利用，还需要继续进行必要的人工处理，才能真正找到矩阵相乘的结合方式。怎么样更直观、合理地输出结合过程？即算法的输出能使用户直接了解计算矩阵的过程。首先看一下com数组存储的信息意义，它是一个二维数组，元素comij存储的是MiMj相乘的组合点k1，也就是说：Mi*Mi+1*Mj是由 Mi*Mi+1*Mk和Mk+1*Mj同样，在数组com中我们也能找到MiMk相乘的组合点k2，Mk+1Mj相乘的组合点k3，。从数组信息中找到

33、了大规模问题与小规模问题的递归关系： 输出算法输出算法 记记k1=com1nk1=com1n，则最后一次运算的结合过程是，则最后一次运算的结合过程是 M1M1* * *Mk1Mk1和和Mk1+1Mk1+1* * *MnMn 记记k2=com1k1k2=com1k1，M1M1* * *Mk1Mk1的结合过程是的结合过程是 M1M1* * *Mk2Mk2和和Mk2+1Mk2+1* * *Mk1Mk1 combine(int i, int j) if ( i=j) return; combine (i, comij); combine (comij+1, j); print（M,i ,“*M”，co

34、mij）; print（ and M,comij+1, “*M”，j ）; 上节 下节 这一节问题的这一节问题的设计角度是从递推思想进行设计角度是从递推思想进行的的, ,设计中只要找设计中只要找出大规模问题与小规模问题出大规模问题与小规模问题( (子问题子问题) )之间的递推关系之间的递推关系, ,最后一个最后一个子问题所得最优解就是原问题的最优解。子问题所得最优解就是原问题的最优解。 【例【例4 4】求两个字符序列的最长公共字符子序列求两个字符序列的最长公共字符子序列。 【例【例5 5】最长不降子序列最长不降子序列。 上节上节 下节下节4.5.4 4.5.4 突出递推的动态规划应用突出递推的

35、动态规划应用【例【例4】求两个字符序列的最长公共字符子序 列。 问题分析 算法设计 算法(递归形式) 算法(非递归) 上节 下节 问题分析问题分析 若若A A的长度为的长度为n n，若，若B B的长度为的长度为m m，则，则 A A的子序列共有：的子序列共有： Cn1+Cn2+ Cn3+Cnn=2n-1Cn1+Cn2+ Cn3+Cnn=2n-1 B B的子序列共有：的子序列共有： Cm1+Cm2+ Cm3+Cmm=2m-1Cm1+Cm2+ Cm3+Cmm=2m-1 如采用枚举策略，当如采用枚举策略，当m=nm=n时，共进行串比较：时，共进行串比较：Cn1Cn1* *Cm1+Cn2Cm1+Cn2

36、* *Cm2+Cn3Cm2+Cn3* *Cm3+CnnCm3+Cnn* *Cnn22n Cnn0,i,j0,且且ai-1=bj-1ai-1=bj-1； 3 3）cij=max(cij-1,ci-1j)cij=max(cij-1,ci-1j) 如果如果i,j0,i,j0,且且ai-1bj-1ai-1bj-1。 上节上节 下节下节 算法算法( (递归形式递归形式) )int Num=100char aNum,bNum,strNum; main( ) int m,n,k; print (“Enter two string”); input(a,b); m=strlen(a); n=strlen(b)

37、, 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

38、); 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, char b, int c n) /计算最优值计算最优值 int m,n,i,j; print (“Enter two string”); input(a,b); m=strlen(a); n=strlen(b); for (i=0;i=m;i+) ci0=0; for (i=0;i=n;i+)

39、 c0i=0; for (i=1;i=m;i+) for (j=1;j=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; else if (cij=cij-1) j=j-1; else k=k-1; strk=ai-1; j=j-1; 上节上节 下节下节【例【例5】最长不降子序列最长不降子序列 设有由设有由n n个不相同的整数组成的数列，记

40、为个不相同的整数组成的数列，记为: : a(1) a(1)、a(2)a(2)、a(n)a(n)且且a(i)a(j) (ij)a(i)a(j) (ij) 若存在若存在i1i2i3 ik i1i2i3 ik 且有且有a(i1)a(i2) a(ik)a(i1)a(i2) a(ik)，则称为长度为则称为长度为k k的不下降序列。请求出一个数列的最长不下降序列。的不下降序列。请求出一个数列的最长不下降序列。 算法设计算法设计 算法算法( (逆推法逆推法) ) 上节上节 下节下节 算法设计算法设计1. 1. 递推关系递推关系 1) 1) 对对a(n)a(n)来说，由于它是最后一个数，所以当从来说，由于它是

41、最后一个数，所以当从a(n)a(n)开始查找开始查找 时时, ,只存在长度为只存在长度为1 1的不下降序列；的不下降序列； 2) 2) 若从若从a(n-1)a(n-1)开始查找，则存在下面的两种可能性：开始查找，则存在下面的两种可能性： (1)(1)若若a(n-1)a(n)a(n-1)a(n)a(n-1)a(n)则存在长度为则存在长度为1 1的不下降序列的不下降序列a(n-1)a(n-1)或或a(n)a(n)。 3) 3) 一般若从一般若从a(i)a(i)开始开始, ,此时最长不下降序列应该按下列方法求出此时最长不下降序列应该按下列方法求出: : 在在a(i+1),a(i+2),a(n)a(i

42、+1),a(i+2),a(n)中，找出一个比中，找出一个比a(i)a(i)大的且最大的且最 长的不下降序列，作为它的后继。长的不下降序列，作为它的后继。 上节上节 下节下节算法算法( (逆推法逆推法) )int maxn=100;int maxn=100;int amaxn,bmaxn,cmaxn;int amaxn,bmaxn,cmaxn;main() main() int n,i,j,max,p; int n,i,j,max,p; input(n); input(n); for (i = 1;i n;i+) for (i = 1;i =1; i=i-1) max=0; p=0; for(j

43、=i+1; j=n; j=j+1) if (aimax) 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; 上节 下节 算法策略和算法是有区别的算法策略和算法是有区别的, ,它们是算法设计中的两个方它们是算法设计中的两个方面，面，算法策略算法策略是面向问题的是面向问题的, ,算法算法是面向实现的；但二者又是是面向实现的；但二者又是不可分的

44、不可分的, ,首先是通过算法策略才找出解决问题的算法，其次首先是通过算法策略才找出解决问题的算法，其次对于用不同算法求解的问题算法策略是自然不同的。对于用不同算法求解的问题算法策略是自然不同的。 本章共介绍了五种算法策略本章共介绍了五种算法策略, ,它们互相有着一定的差别，它们互相有着一定的差别，适应的问题也有所差异。适应的问题也有所差异。 上节上节 下节下节4.6 4.6 算法策略间的比较算法策略间的比较 “贪婪算法贪婪算法” “ “递推法递推法” “ “递归法递归法” “ “枚举法枚举法” “ “递归回朔法递归回朔法” “ “分治法分治法” “ “动态规划法动态规划法” 上节上节 下节下节

45、4.6.1 4.6.1 不同算法策略特点小结不同算法策略特点小结 “贪婪算法贪婪算法” 这些策略求解的是最简单的一类问题，或者说是对问这些策略求解的是最简单的一类问题，或者说是对问题要求最严格的算法策略。题要求最严格的算法策略。“贪婪算法贪婪算法”解决这类问题是解决这类问题是按一定顺序（从前向后或从后向前等）一定的策略，只需按一定顺序（从前向后或从后向前等）一定的策略，只需考虑当前局部信息就能做出决策，即所谓局部最优就是全考虑当前局部信息就能做出决策，即所谓局部最优就是全局最优。局最优。 上节上节 下节下节 “递推法递推法” “ “递推法递推法”和贪婪算法一样也是由当前问题的逐步解决和贪婪算法

46、一样也是由当前问题的逐步解决从而得到整个问题的解，只是依赖的是信息间本身的递推关从而得到整个问题的解，只是依赖的是信息间本身的递推关系，每一步不需要策略参与到算法中，它们更多地用于计算。系，每一步不需要策略参与到算法中，它们更多地用于计算。 上节上节 下节下节 “递归法递归法” 和递推法类似，递归法是利用大问题与其子问题间的递和递推法类似，递归法是利用大问题与其子问题间的递归关系来解决问题的。能采用递归描述的算法通常有这样的归关系来解决问题的。能采用递归描述的算法通常有这样的特征：为求解规模为特征：为求解规模为N N的问题，设法将它分解成规模较小的的问题，设法将它分解成规模较小的问题，然后从这

47、些小问题的解方便地构造出大问题的解，并问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模大问题的解。特别地，当规模N=1N=1时，能直接得解。时，能直接得解。 上节上节 下节下节 “枚举法枚举法” 枚举法既是一个策略，也是一个算法，也是一个分析问枚举法既是一个策略，也是一个算法，也是一个分析问题的手段。枚举法的求解思路很简单题的手段。枚举法的求解思路很简单, ,

48、就是对所有可能的解逐就是对所有可能的解逐一尝试，从而找出问题的真正解。当然这就要求所解的问题一尝试，从而找出问题的真正解。当然这就要求所解的问题可能的解是可能的解是有限的、固定的有限的、固定的，不会产生组合爆炸、容易枚举，不会产生组合爆炸、容易枚举的。多用于决策类问题。这类问题都不易进行问题的分解，的。多用于决策类问题。这类问题都不易进行问题的分解，只能只能整体来求解整体来求解。 上节上节 下节下节 “递归回朔法递归回朔法” 类似于枚举法的思想类似于枚举法的思想, ,递归回朔法通过递归尝试遍问题递归回朔法通过递归尝试遍问题各个可能解的通路，发现此路不通时回朔到上一步继续尝试各个可能解的通路，发

49、现此路不通时回朔到上一步继续尝试别的通路。在下一章中对其应用做详细介绍。别的通路。在下一章中对其应用做详细介绍。 上节上节 下节下节 “分治法分治法” 求解的则是较复杂的问题，这类问题是可以被分解成求解的则是较复杂的问题，这类问题是可以被分解成独独立的子问题立的子问题来解决的，将两个或两个以上的独立子问题的解来解决的，将两个或两个以上的独立子问题的解“合成合成”，就得到较大的子问题的解，最后合成为总问题的，就得到较大的子问题的解，最后合成为总问题的解。解。 上节上节 下节下节 “动态规划法动态规划法” 动态规划法与贪心法类似动态规划法与贪心法类似，是通过多阶段决策过程来解，是通过多阶段决策过程

50、来解决问题的。但每个阶段决策的结果是一个决策结果序列，这决问题的。但每个阶段决策的结果是一个决策结果序列，这个结果序列中最后采用哪一个结果取决于以后每个阶段决策，个结果序列中最后采用哪一个结果取决于以后每个阶段决策，因此称为因此称为“动态动态”规划法。当然每一次的决策结果序列都必规划法。当然每一次的决策结果序列都必须进行存储。因此，可以说须进行存储。因此，可以说“动态规划是高效率、高消费的动态规划是高效率、高消费的算法算法”。 另一方面，另一方面，动态规划法与分治法类似动态规划法与分治法类似，当问题不能分解，当问题不能分解为独立的子问题为独立的子问题, ,但又符合最优化原理但又符合最优化原理(

51、 (最优子结构性质最优子结构性质) )时时, ,用动态规划，通过多阶段决策过程从逐步找出子问题的最优用动态规划，通过多阶段决策过程从逐步找出子问题的最优解，从而决策出问题的结果。解，从而决策出问题的结果。 上节上节 下节下节 1. 1. 对问题进行分解的算法策略对问题进行分解的算法策略-分治法分治法 与与 动态规划法动态规划法 2. 2. 多阶段过程多阶段过程 贪婪算法贪婪算法 、 递推法递推法 、 递归法递归法 和和 动态规划法动态规划法 3. 3. 全面逐一尝试、比较全面逐一尝试、比较 蛮力法蛮力法 、 枚举法枚举法 、 递归回溯法递归回溯法 4 4算法策略的中心思想算法策略的中心思想 上

52、节上节 下节下节4.6.2 4.6.2 算法策略间的关联算法策略间的关联1.对问题进行分解的算法策略 -“分治法”与“动态规划法” “分治法”与“动态规划法”都是递归思想的应用之一，是找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。区别在于： 上节 下节 分治法分治法所能解决的问题一般具有以下几个特征：所能解决的问题一般具有以下几个特征： 1) 1) 该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决； 2) 2) 该问题可以分解为若干个规模较小的相同问题，即该问该问题可以分解为若干个规模较小的相同问题，即该

53、问 题具有。题具有。 3) 3) 利用该问题分解出的子问题的解可以合并为该问题的解利用该问题分解出的子问题的解可以合并为该问题的解; ; 4) 4) 该问题所分解出的各个子问题是相互独立的，即子问题该问题所分解出的各个子问题是相互独立的，即子问题 之间不包含公共的子问题。之间不包含公共的子问题。 上节上节 下节下节 第一条特征是绝大多数问题都可以满足的第一条特征是绝大多数问题都可以满足的; ; 第二条特征是应用分治法的前提第二条特征是应用分治法的前提, ,它也是大多数问题可以满足的它也是大多数问题可以满足的; ; 第三条特征是关键。第三条特征是关键。 第四条特征涉及到分治法的效率。第四条特征涉

54、及到分治法的效率。 动态规划的动态规划的实质实质是分治思想和解决冗余。是分治思想和解决冗余。 上节上节 下节下节2 2多阶段过程多阶段过程“贪婪算法贪婪算法”、“递推法递推法”、 “递归法递归法”和和“动态规划法动态规划法” 多阶段过程就是按一定顺序多阶段过程就是按一定顺序( (从前向后或从后向前等从前向后或从后向前等) )一一定的策略定的策略, , 逐步解决问题的方法。逐步解决问题的方法。 “ “贪婪算法贪婪算法”每一步根据策略得到一个结果传递到下一每一步根据策略得到一个结果传递到下一步，自顶向下，一步一步地作出贪心选择。步，自顶向下，一步一步地作出贪心选择。 上节上节 下节下节 “动态规划

55、法动态规划法”则根据一定的决策则根据一定的决策, , 每一步决策出的不每一步决策出的不是一个结果，而只是使问题的规模不断的缩小，如果决策比是一个结果，而只是使问题的规模不断的缩小，如果决策比较简单较简单, ,是一般的算法运算是一般的算法运算, ,则可找到不同规模问题间的关系，则可找到不同规模问题间的关系，使算法演变成使算法演变成“递推法递推法”、“递归法递归法”算法算法, ,所以说动态规划所以说动态规划更侧重算法设计策略，而不是算法。更侧重算法设计策略，而不是算法。 “ “递推法递推法”、“递归法递归法”更注重每一步之间的关系更注重每一步之间的关系, ,决策决策的因素较少。的因素较少。“递推法

56、递推法”根据关系从前向后推根据关系从前向后推, ,由小规模的结由小规模的结论论, ,推解出问题的解。推解出问题的解。“递归法递归法”根据关系先从后向前使大问根据关系先从后向前使大问题，转化为小问题，最后同样由小规模结论，推解出问题的题，转化为小问题，最后同样由小规模结论，推解出问题的解。解。 上节上节 下节下节3 3全面逐一尝试、比较全面逐一尝试、比较“蛮力法蛮力法”、 “枚举法枚举法”、“递归回溯法递归回溯法” 考虑到有这样一类问题，问题中不易找到信息间的相互考虑到有这样一类问题，问题中不易找到信息间的相互关系，也不能分解为独立的子问题关系，也不能分解为独立的子问题, ,似乎只有把各种可能情

57、况似乎只有把各种可能情况都考虑到都考虑到, ,并把全部解都列出来之后并把全部解都列出来之后, ,才能判定和得到最优解。才能判定和得到最优解。对于规模不大的问题，这些策略简单方便对于规模不大的问题，这些策略简单方便; ;而当问题的计算复而当问题的计算复杂度高且计算量很大时杂度高且计算量很大时, ,还是考虑采用还是考虑采用“动态规划法动态规划法”这个更这个更有效的算法策略有效的算法策略。 上节 下节 枚举法算法的实现枚举法算法的实现依赖于循环依赖于循环, ,通过循环嵌套枚举问题中通过循环嵌套枚举问题中各种可能的情况各种可能的情况, ,如八皇后问题能用八重循环嵌套枚举。而对如八皇后问题能用八重循环嵌

58、套枚举。而对于规模于规模不固定不固定的问题就无法用固定重数的循环嵌套来枚举了的问题就无法用固定重数的循环嵌套来枚举了, ,有的问题可能通过变换枚举对象也能用循环嵌套枚举实现有的问题可能通过变换枚举对象也能用循环嵌套枚举实现, ,但但更多的任意指定规模的问题是靠递归回朔法来更多的任意指定规模的问题是靠递归回朔法来“枚举枚举”或或“遍历遍历”各种可能的情况。比如各种可能的情况。比如n n皇后问题只能用皇后问题只能用“递归回朔递归回朔法法”通过递归实现（当然可以通过栈通过递归实现（当然可以通过栈, ,而不用递归）。而不用递归）。 上节上节 下节下节4 4算法策略的中心思想算法策略的中心思想 所有算法

59、策略的中心思想就是用算法的基本工具循环所有算法策略的中心思想就是用算法的基本工具循环机制和递归机制实现算法。递推法自然不用多说，贪婪算法机制和递归机制实现算法。递推法自然不用多说，贪婪算法就是逐步决策解决问题，动态规划也是。就是逐步决策解决问题，动态规划也是。 上节 下节 4.6.3 4.6.3 算法策略侧重的问题类型算法策略侧重的问题类型 一般我们在实际应用中遇到的问题主要分为四类一般我们在实际应用中遇到的问题主要分为四类: :判定性问题、判定性问题、计算问题、最优化问题和构造性问题。计算问题、最优化问题和构造性问题。 递推法递推法 、 递归法递归法 算法较适合解决判定性问题、计算问题。算法较适合解决判定性问题、计算问题。 “ “贪婪算法贪婪算法”、“分治法分治法” ” 、“动态规划法动态规划法” ” 与与“枚举法枚举法” ” 较适合较适合解最优化问题。解最优化问题。 构造性问题更多地依赖于人的经验和抽象能力，算法一般是构造性问题更多地依赖于人的经验和抽象能力，算法一般是人类智能充分对问题解决步骤细化后才能得到算法，少有通用的人类智能充分对问题解决步骤细化后才能得到算法，少有通用的算法策略。当然也有一些问题在构造过程中使用通用的算法策略。算法策略。当然也有一些问题在构造过程中使用通用的算法策略。 上节 下节下面就最优化问题讨论如下：下面就