第四章5贪心动态

第四章5贪心动态第1页，共75页。在动态规划算法策略中，表达在它的决策不是线性的而是全在动态规划算法策略中，表达在它的决策不是线性的而是全面考虑不同的情况分别进展决策面考虑不同的情况分别进展决策,并通过多阶段决策来最终解决并通过多阶段决策来最终解决问题。在各个阶段采取决策后问题。在各个阶段采取决策后,会不断决策出新的数据会不断决策出新的数据,直到找到直到找到最优解最优解.每次决策依赖于当前状态每次决策依赖于当前状态,又随即引起状态的转移。一个又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，故有决策序列就是在变化的状态中产生出来的，故有“动态的含义。动态的含义。所以，这种多阶段决策最优化的解决问题的过程称为动态规划。所以，这种多阶段决策最优化的解决问题的过程称为动态规划。上节上节 下节下节4.5 4.5 动态规划动态规划第2页，共75页。我们通过一个简单的例子来说明动态规划的多阶段决策与贪婪算法有什么区别。【例【例1】数塔问题数塔问题 上节 下节4.5.1 认识动态规划第3页，共75页。【例【例1 1】数塔问题数塔问题 有形如图4-11所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。问题分析算法设计算法小结第4页，共75页。问题分析这个问题用贪婪算法有可能会找不到真正的最大和。以图4-11为例就是如此。用贪婪的策略，那么路径和分别为：9+15+8+9+10=51自上而下，19+2+10+12+9=52自下而上。都得不到最优解，真正的最大和是：9+12+10+18+10=59。在知道数塔的全貌的前提下，可以用枚举法或下一章将学习的搜索算法来完成。上节下节第5页，共75页。算法设计算法设计 动态规划设计过程如下：动态规划设计过程如下：1.1.阶段划分：阶段划分：第一步对于第五层的数据，我们做如下五次决策：第一步对于第五层的数据，我们做如下五次决策：对经过第四层对经过第四层2 2的路径选择第五层的的路径选择第五层的1919，对经过第四层对经过第四层1818的路径选择第五层的的路径选择第五层的1010，对经过第四层对经过第四层9 9的路径也选择第五层的的路径也选择第五层的1010，对经过第四层对经过第四层5 5的路径选择第五层的的路径选择第五层的1616。上节上节 下节下节第6页，共75页。以上的决策结果将五阶数塔问题变为以上的决策结果将五阶数塔问题变为4 4阶子问题，递推阶子问题，递推出第四层与第五层的和为出第四层与第五层的和为: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阶数塔问题，就是整个问题的最优解。阶数塔问题，就是整个问题的最优解。上节上节 下节下节第7页，共75页。2 2存储、求解：存储、求解：1)1)原始信息存储原始信息存储 原始信息有层数和数塔中的数据，层数用一个整型原始信息有层数和数塔中的数据，层数用一个整型 变量变量n n存储，数塔中的数据用二维数组存储，数塔中的数据用二维数组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 上节上节 下节下节第8页，共75页。2)2)动态规划过程存储动态规划过程存储 必需用二维数组必需用二维数组a a存储各阶段的决策结果。二维数组存储各阶段的决策结果。二维数组a a的存的存储内容如下：储内容如下：dnj=datanj j=1,2,ndnj=datanj j=1,2,n；i=n-1,n-2,1 i=n-1,n-2,1，j=1,2,ij=1,2,i；时；时 dij=max(di+1j dij=max(di+1j，di+1j+1)+dataijdi+1j+1)+dataij 最后最后a11a11存储的就是问题的结果。存储的就是问题的结果。上节上节 下节下节第9页，共75页。3)3)最优解路径求解及存储最优解路径求解及存储 仅有数组仅有数组datadata和数组和数组a a可以找到最优解的路径，可以找到最优解的路径，但需要自顶向下比较但需要自顶向下比较数组数组datadata和数组和数组a a是可以找到。如图是可以找到。如图4.5.24.5.2求解和输出过程如下：求解和输出过程如下：上节上节 下节下节第10页，共75页。输出输出a119a119 b=d11-data11=59-9=50 b b=d11-data11=59-9=50 b与与d21,d22 d21,d22 比较比较 b b与与d21d21相等输出相等输出data2112data2112 b=d21-data21=50-12=38 b b=d21-data21=50-12=38 b与与d31,d32 d31,d32 比较比较 b b与与d31d31相等输出相等输出data3110data3110 b=a31-data31=38-10=28 b b=a31-data31=38-10=28 b与与d41,d42 d41,d42 比较比较 b b与与d42d42相等输出相等输出data4218data4218 b=d42-data42=28-18=10 b b=d42-data42=28-18=10 b与与d52,d53 d52,d53 比较比较 b b与与d53d53相等输出相等输出data5310“data5310“上节上节 下节下节第11页，共75页。数组数组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 4 16 图图4-12 4-12 数塔及动态规划过程数据数塔及动态规划过程数据 上节上节 下节下节第12页，共75页。为了设计简洁的算法，我们最后用三维数组为了设计简洁的算法，我们最后用三维数组a50503a50503存储以上存储以上确定的三个数组的信息。确定的三个数组的信息。a50501 a50501代替数组代替数组datadata，a50502 a50502代替数组代替数组d,d,a50503 a50503记录解路径。记录解路径。上节上节 下节下节第13页，共75页。数塔问题的算法数塔问题的算法main()main()int a50503,i,j,n;int a50503,i,j,n;print(please 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;else else aij2=aij2+ai+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);上节上节 下节下节第15页，共75页。从例子中可以看到：从例子中可以看到：动态规划动态规划=贪婪策略贪婪策略+递推递推(降阶降阶)+)+存储递推结果存储递推结果 贪贪婪婪策策略略、递递推推算算法法都都是是在在“线线性性地地解解决决问问题题，而而动动态态规规划划那那么么是是全全面面分分阶阶段段地地解解决决问问题题。可可以以通通俗俗地地说说动动态态规规划划是是“带带决策的多阶段、多方位的递推算法。决策的多阶段、多方位的递推算法。上节上节 下节下节第16页，共75页。动态规划算法的问题及决策应该具有三个性质：最优化原理、无后向性、子问题重叠性质。1)最优化原理(或称为最正确原那么、最优子构造)。2)无后向性(无后效性)。3)有重叠子问题。上节下节 算法框架第17页，共75页。2.动态规划的根本思想 动态规划方法的根本思想是，把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。最后一个子问题就是初始问题的解。由于动态规划的问题有重叠子问题的特点，为了减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。上节 下节第18页，共75页。3.设计动态规划算法的根本步骤 设计一个标准的动态规划算法的步骤：1)划分阶段 2)选择状态 3)确定决策并写出状态转移方程 但是,实际应用当中的简化步骤：1)分析最优解的性质，并刻划其构造特征。2)递推地定义最优值。3)以自底向上的方式或自顶向下的记忆化方法(备忘录 法)计算出最优值.4)根据计算最优值时得到的信息，构造问题的最优解。上节 下节第19页，共75页。4.标准动态规划的根本框架for(j=1;j=1;i=i-1)/其它n-1个阶段 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;上节 下节第20页，共75页。【例【例2 2】资源分配问题。【例【例3 3】n个矩阵连乘的问题。上节 下节4.5.3 突出阶段性的动态规划应用第21页，共75页。【例【例2 2】资源分配问题。】资源分配问题。设设有有资资源源a,a,分分配配给给n n个个工工程程,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,x1+xx2+x3+xn=a,xi0,i=1xi0,i=1，2,3,n2,3,n函数函数gi(x)gi(x)以数据表的形式给出以数据表的形式给出.例例如如：现现有有7 7万万元元投投资资到到A A，B B，C C 三三个个工工程程，利利润见表润见表,求问题总利润最大的资源分配方案。求问题总利润最大的资源分配方案。上节上节 下节下节第22页，共75页。算法设计算法设计1阶段划分及决策阶段划分及决策比较直观的阶段划分就是逐步考虑每一个工程在不比较直观的阶段划分就是逐步考虑每一个工程在不同投资额下的利润情况。同投资额下的利润情况。3.数据构造设计：数据构造设计：1)开辟一维数组开辟一维数组q来存储原始数据。来存储原始数据。2)另开辟一维数组另开辟一维数组f存储当前最大收益情况。存储当前最大收益情况。3)开辟记录中间结果的一维数组数组开辟记录中间结果的一维数组数组temp，记录正在计，记录正在计算的最大收益。算的最大收益。4)开辟二维数组开辟二维数组a。5)数组数组gain存储第存储第i个工程投资数的最后结果。个工程投资数的最后结果。上节上节下节下节第23页，共75页。对于一般问题设计对于一般问题设计算法算法如下如下：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?print(“How mang item?);input(m););input(m);print(“How mang money?print(“How mang money?);input(n););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=j;上节上节 下节下节第24页，共75页。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-)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);第25页，共75页。【例3】n个矩阵连乘的问题。问题分析 算法设计 算法1(递归算法)算法1说明 算法2(递归算法)算法3(非递归算法)输出算法 上节 下节第26页，共75页。问题分析问题分析多个矩阵连乘运算是满足结合律的。多个矩阵连乘运算是满足结合律的。例例:M15*20*M220*50*M350*1*M41*100分别按分别按(M1*M2)*M3)*M4，M1*(M2*(M3*M4)，(M1*(M2*M3)*M4的次序相乘的次序相乘,各需进展各需进展5750,115000,1600次乘法。次乘法。这个问题要用这个问题要用“动态规划算法来完成动态规划算法来完成:首先首先,从两个矩阵相乘的情况开场；从两个矩阵相乘的情况开场；然后然后,尝试三个矩阵相乘的情况；尝试三个矩阵相乘的情况；最后最后,等到等到n个矩阵相乘所用的最少的乘法次数及结合方式。个矩阵相乘所用的最少的乘法次数及结合方式。上节上节下节下节第27页，共75页。算法设计算法设计1.阶段划分阶段划分1初始状态为一个矩阵相乘的计算量为初始状态为一个矩阵相乘的计算量为0;2第二阶段第二阶段,计算两个相邻矩阵相乘的计算量计算两个相邻矩阵相乘的计算量,共共n-1组组3第三阶段第三阶段,计算两个相邻矩阵相乘的计算量计算两个相邻矩阵相乘的计算量,共共n-2组组4最后一个阶段最后一个阶段,是是n个相邻矩阵相乘的计算量个相邻矩阵相乘的计算量,共共1组组,是问题解。是问题解。上节上节下节下节第28页，共75页。2.2.阶段决策阶段决策 一般地，计算一般地，计算M1*M2*M3*Mn M1*M2*M3*Mn 其中其中M1M1，M2M2，,Mi,Mi分别是分别是 r1*r2 r1*r2，r2*r3r2*r3，,ri*ri+1,ri*ri+1阶矩阵，阶矩阵，i=1,2,3,ni=1,2,3,n。设设mi,jmi,j是计算是计算Mi*Mi+1*MjMi*Mi+1*Mj的最少乘法次数的最少乘法次数(1ijn),(1ijn),对对 mi,j mi,j有公式：有公式：0 0 当当i=ji=j时时 ri-1*ri*ri+1 ri-1*ri*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的。的。用二维矩阵用二维矩阵comij(n*n)comij(n*n)来存储使来存储使mijmij为最小值时的为最小值时的 k k 值。值。上节上节 下节下节第29页，共75页。算法算法1 1(递归算法递归算法)intr100,com100100;mainintn,i;print(“Howmangmatrixes?);input(n);peint(“Howsizeeverymatrixe?);for(i=1;i=n+1;i+)input(ri);print(“Theleastcalculatequantity：,course(1,n);for(i=1;i=n;i+)print(“换行符);for(j=1;j=n;j+)print(comij);上节下节第30页，共75页。intcourse(inti,intj)intu,t;if(i=j)return0;if(i=j-1)comii+1=i;returnri*ri+1*rr+2;u=course(i,i)+course(i+1,j)+ri*ri+1*rj+1;comij=i;for(intk=i+1;kj;k+)t=course(i,k)+course(k+1,j)+ri*rk+1*rj+1;if(tu)u=t;comij=k;returnu;上节下节第31页，共75页。算法1说明以上的递归算法虽然解决了问题，但效率很低，有子问题重叠，n=4时的递归过程如以下图：上节下节第32页，共75页。算法2(改进后递归算法)intm100100,com100100,r100;matrix2intn,;print(“Howmangmatrixes?);input(n);print(“Howsizeeverymatrixe?);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(“Theleastcalculatequantity：m1n);for(i=1;i=n;i+)print(“换行符换行符);for(j=1;j0returnmij;if(i=j)return0;if(i=j-1)comii+1=i;mij=ri*ri+1*ri+2;returnmij;intu=course(i,i)+course(i+1,j)+ri*ri+1*rj+1;comij=i;for(intk=i+1;kj;k+)intt=course(i,k)+course(k+1,j)+ri*rk+1*rj+1;if(tu)u=t;comij=k;mij=u;returnu;上节上节下节下节第34页，共75页。算法算法3 3(非递归算法非递归算法)mainintn,r100,m100100,com100100;peint(“Howmangmatrixes?);input(n);peint(“Howsizeeverymatrixe?);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=0mii+1=ri*ri+1*ri+2;s=1comii+1=i+1;上节下节第35页，共75页。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(tmij)mij=t;comij=k;print(“Theleastcalculatequantity：m1n);for(i=1;i=n;i+)print(“换行符换行符);for(j=1;j=n;j+)print(comij);上节上节下节下节第36页，共75页。输出局部的算法设计以上算法中关于矩阵相乘的结合方式，只是简单的输出了数组com的内容，不容易直观地被利用，还需要继续进展必要的人工处理，才能真正找到矩阵相乘的结合方式。怎么样更直观、合理地输出结合过程？即算法的输出能使用户直接了解计算矩阵的过程。首先看一下com数组存储的信息意义，它是一个二维数组，元素comij存储的是MiMj相乘的组合点k1，也就是说：Mi*Mi+1*Mj是由 Mi*Mi+1*Mk和Mk+1*Mj同样，在数组com中我们也能找到MiMk相乘的组合点k2，Mk+1Mj相乘的组合点k3，。从数组信息中找到了大规模问题与小规模问题的递归关系：第37页，共75页。输出算法记k1=com1n，那么最后一次运算的结合过程是M1*Mk1和Mk1+1*Mn记k2=com1k1，M1*Mk1的结合过程是M1*Mk2和Mk2+1*Mk1combine(inti,intj)if(i=j)return;combine(i,comij);combine(comij+1,j);printM,i,“*M，comij;printandM,comij+1,“*M，j;上节下节第38页，共75页。这这一一节节问问题题的的设设计计角角度度是是从从递递推推思思想想进进展展的的,设设计计中中只只要要找找出出大大规规模模问问题题与与小小规规模模问问题题(子子问问题题)之之间间的的递递推推关关系系,最最后后一一个个子子问问题题所所得得最最优优解解就是原问题的最优解。就是原问题的最优解。【例【例4 4】求两个字符序列的最长公共字符子序列。】求两个字符序列的最长公共字符子序列。【例【例5 5】最长不降子序列。】最长不降子序列。上节上节 下节下节4.5.4 4.5.4 突出递推的动态规划应用突出递推的动态规划应用第39页，共75页。【例【例4】求两个字符序列的最长公共字符子序 列。问题分析 算法设计 算法(递归形式)算法(非递归)上节 下节第40页，共75页。问题分析问题分析假设假设A的长度为的长度为n，假设，假设B的长度为的长度为m，那么，那么A的子序列共有：的子序列共有：Cn1+Cn2+Cn3+Cnn=2n-1B的子序列共有：的子序列共有：Cm1+Cm2+Cm3+Cmm=2m-1如采用枚举策略，当如采用枚举策略，当m=n时，共进展串比较：时，共进展串比较：Cn1*Cm1+Cn2*Cm2+Cn3*Cm3+Cnn*Cnn0,i,j0,且且ai-1=bj-1ai-1=bj-1；3 3cij=max(cij-1,ci-1j)cij=max(cij-1,ci-1j)如果如果i,j0,i,j0,且且ai-1bj-1ai-1bj-1。上节上节 下节下节第43页，共75页。算法算法(递归形式递归形式)intNum=100charaNum,bNum,strNum;main()intm,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);上节上节下节下节第44页，共75页。lcs_len(inti，j)/计算最优值计算最优值if(i=0orj=0)cij=0;elseif(ai-1=bj-1)cij=lcs_len(i-1，j-1)+1;elsecij=maxlcs_len(i，j-1)，lcs_len(i-1，j);buile_lcs(k,i,j);/构造最长公共子序列构造最长公共子序列ifi=0orj=0return;ifcij=ci-1jbuile_lcs(k,i-1,j);elseifcij=cij-1buile_lcs(k,i,j-1);elsestrk=ai-1;buile_lcs(k-1,i-1,j-1);上节上节下节下节第45页，共75页。算法算法(非递归非递归)n=100charan,bn,strn;lcs_len(chara,charb,intcn)/计算最优值计算最优值intm,n,i,j;print(“Entertwostring);input(a,b);m=strlen(a);n=strlen(b);for(i=0;i=m;i+)ci0=0;for(i=0;i=n;i+)c0i=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;elsecij=cij-1;第46页，共75页。buile_lcs()/构造最构造最长长公共子序列公共子序列intk,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;elsek=k-1;strk=ai-1;j=j-1;上节上节 下节下节第47页，共75页。【例【例5】最长不降子序列】最长不降子序列 设有由设有由n个不一样的整数组成的数列，记为个不一样的整数组成的数列，记为:a(1)、a(2)、a(n)且且a(i)a(j)(ij)假假设设存存在在i1i2i3 ik 且且有有a(i1)a(i2)a(ik)，那那么么称称为为长长度度为为k的的不不下下降降序序列列。请请求求出出一一个数列的最长不下降序列。个数列的最长不下降序列。算法设计算法设计 算法算法(逆推法逆推法)上节上节 下节下节第48页，共75页。算法设计算法设计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)大的且最大的且最长的不下降序列，作为它的后继。长的不下降序列，作为它的后继。上节上节下节下节第49页，共75页。算法算法(逆推法逆推法)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=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;imax)max:=bi;p:=i;print(maxlong=,max);print(resultis:);while(p0)print(ap);p:=cp;上节 下节第51页，共75页。算法策略和算法是有区别的算法策略和算法是有区别的,它们是算法设计中的两个方面，它们是算法设计中的两个方面，算法策略是面向问题的算法策略是面向问题的,算法是面向实现的；但二者又是不可分算法是面向实现的；但二者又是不可分的的,首先是通过算法策略才找出解决问题的算法，其次对于用不首先是通过算法策略才找出解决问题的算法，其次对于用不同算法求解的问题算法策略是自然不同的。同算法求解的问题算法策略是自然不同的。本章共介绍了五种算法策略本章共介绍了五种算法策略,它们互相有着一定的差异，适应的问题它们互相有着一定的差异，适应的问题也有所差异。也有所差异。上节上节下节下节4.6 4.6 算法策略间的比较算法策略间的比较第52页，共75页。“贪婪算法贪婪算法“递推法递推法“递归法递归法“枚举法枚举法“递归回朔法递归回朔法“分治法分治法“动态规划法动态规划法上节上节下节下节4.6.1 4.6.1 不同算法策略特点小结不同算法策略特点小结第53页，共75页。“贪婪算法贪婪算法这些策略求解的是最简单的一类问题，或者说是对问题要求这些策略求解的是最简单的一类问题，或者说是对问题要求最严格的算法策略。最严格的算法策略。“贪婪算法解决这类问题是按一定顺序贪婪算法解决这类问题是按一定顺序从前向后或从后向前等一定的策略，只需考虑当前局部信从前向后或从后向前等一定的策略，只需考虑当前局部信息就能做出决策，即所谓局部最优就是全局最优。息就能做出决策，即所谓局部最优就是全局最优。上节上节下节下节第54页，共75页。“递推法递推法“递推法和贪婪算法一样也是由当前问题的逐步解决从而得递推法和贪婪算法一样也是由当前问题的逐步解决从而得到整个问题的解，只是依赖的是信息间本身的递推关系，每一步到整个问题的解，只是依赖的是信息间本身的递推关系，每一步不需要策略参与到算法中，它们更多地用于计算。不需要策略参与到算法中，它们更多地用于计算。上节上节下节下节第55页，共75页。“递归法递归法和递推法类似，递归法是利用大问题与其子问题间的递归关和递推法类似，递归法是利用大问题与其子问题间的递归关系来解决问题的。能采用递归描述的算法通常有这样的特征：系来解决问题的。能采用递归描述的算法通常有这样的特征：为求解规模为为求解规模为N的问题，设法将它分解成规模较小的问题，然的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模别地，当规模N=1时，能直接得解。时，能直接得解。上节上节下节下节第56页，共75页。“枚举法枚举法枚举法既是一个策略，也是一个算法，也是一个分析问题的手段。枚举法既是一个策略，也是一个算法，也是一个分析问题的手段。枚举法的求解思路很简单枚举法的求解思路很简单,就是对所有可能的解逐一尝试，从而找出就是对所有可能的解逐一尝试，从而找出问题的真正解。当然这就要求所解的问题可能的解是有限的、固定问题的真正解。当然这就要求所解的问题可能的解是有限的、固定的，不会产生组合爆炸、容易枚举的。多用于决策类问题。这类问的，不会产生组合爆炸、容易枚举的。多用于决策类问题。这类问题都不易进展问题的分解，只能整体来求解。题都不易进展问题的分解，只能整体来求解。上节上节下节下节第57页，共75页。“递归回朔法递归回朔法类似于枚举法的思想类似于枚举法的思想,递归回朔法通过递归尝试遍问题各个可能解递归回朔法通过递归尝试遍问题各个可能解的通路，发现此路不通时回朔到上一步继续尝试别的通路。在下一的通路，发现此路不通时回朔到上一步继续尝试别的通路。在下一章中对其应用做详细介绍。章中对其应用做详细介绍。上节上节下节下节第58页，共75页。“分治法分治法求解的那么是较复杂的问题，这类问题是可以被分解成独立求解的那么是较复杂的问题，这类问题是可以被分解成独立的子问题来解决的，将两个或两个以上的独立子问题的解的子问题来解决的，将两个或两个以上的独立子问题的解“合合成，就得到较大的子问题的解，最后合成为总问题的解。成，就得到较大的子问题的解，最后合成为总问题的解。上节上节下节下节第59页，共75页。“动态规划法动态规划法动态规划法与贪心法类似，是通过多阶段决策过程来解决问题的。但动态规划法与贪心法类似，是通过多阶段决策过程来解决问题的。但每个阶段决策的结果是一个决策结果序列，这个结果序列中最后采用哪每个阶段决策的结果是一个决策结果序列，这个结果序列中最后采用哪一个结果取决于以后每个阶段决策，因此称为一个结果取决于以后每个阶段决策，因此称为“动态规划法。当然每动态规划法。当然每一次的决策结果序列都必须进展存储。因此，可以说一次的决策结果序列都必须进展存储。因此，可以说“动态规划是高效动态规划是高效率、高消费的算法。率、高消费的算法。另一方面，动态规划法与分治法类似，当问题不能分解为独立另一方面，动态规划法与分治法类似，当问题不能分解为独立的子问题的子问题,但又符合最优化原理但又符合最优化原理(最优子构造性质最优子构造性质)时时,用动态规划，用动态规划，通过多阶段决策过程从逐步找出子问题的最优解，从而决策出问通过多阶段决策过程从逐步找出子问题的最优解，从而决策出问题的结果。题的结果。上节上节下节下节第60页，共75页。1.对问题进展分解的算法策略对问题进展分解的算法策略-分治法分治法与与动态规划法动态规划法2.多阶段过程多阶段过程贪婪算法贪婪算法、递推法递推法、递归法递归法和和动态规划法动态规划法3.全面逐一尝试、比较全面逐一尝试、比较蛮力法蛮力法、枚举法枚举法、递归回溯法递归回溯法4算法策略的中心思想算法策略的中心思想上节上节下节下节4.6.2 4.6.2 算法策略间的关联算法策略间的关联第61页，共75页。-“分治法与“动态规划法 “分治法与“动态规划法都是递归思想的应用之一，是找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。区别在于：上节 下节第62页，共75页。分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：1)该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；2)该问题可以分解为假设干个规模较小的一样问题，即该问该问题可以分解为假设干个规模较小的一样问题，即该问题具有。题具有。3)利用该问题分解出的子问题的解可以合并为该问题的解利用该问题分解出的子问题的解可以合并为该问题的解;4)该问题所分解出的各个子问题是相互独立的，即子问题该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。之间不包含公共的子问题。上节上节下节下节第63页，共75页。第一条特征是绝大多数问题都可以满足的第一条特征是绝大多数问题都可以满足的;第二条特征是应用分治法的前提第二条特征是应用分治法的前提,它也是大多数问题可以满足的它也是大多数问题可以满足的;第三条特征是关键。第三条特征是关键。第四条特征涉及到分治法的效率。第四条特征涉及到分治法的效率。动态规划的动态规划的实质实质是分治思想和解决冗余。是分治思想和解决冗余。上节上节 下节下节第64页，共75页。2 2多阶段过程多阶段过程“贪婪算法、贪婪算法、“递推法、递推法、“递归法和递归法和“动态规划法动态规划法 多阶段过程就是按一定顺序多阶段过程就是按一定顺序(从前向后或从从前向后或从后向前等后向前等)一定的策略一定的策略,逐步解决问题的方法。逐步解决问题的方法。“贪婪算法每一步根据策略得到一个结果贪婪算法每一步根据策略得到一个结果传递到下一步，自顶向下，一步一步地作出贪心传递到下一步，自顶向下，一步一步地作出贪心选择。选择。上节上节 下节下节第65页，共75页。“动态规划法那么根据一定的决策动态规划法那么根据一定的决策,每一步决策出的不是一个结每一步决策出的不是一个结果，而只是使问题的规模不断的缩小，如果断策比较简单果，而只是使问题的规模不断的缩小，如果断策比较简单,是一般的算是一般的算法运算法运算,那么可找到不同规模问题间的关系，使算法演变成那么可找到不同规模问题间的关系，使算法演变成“递推法、递推法、“递归法算法递归法算法,所以说动态规划更侧重算法设计策略，而不是算法。所以说动态规划更侧重算法设计策略，而不是算法。“递推法、递推法、“递归法更注重每一步之间的关系递归法更注重每一步之间的关系,决策的因素较少。决策的因素较少。“递推法根据关系从前向后推递推法根据关系从前向后推,由小规模的结论由小规模的结论,推解出问题的解。推解出问题的解。“递归递归法根据关系先从后向前使大问题，转化为小问题，最后同样由小规模法根据关系先从后向前使大问题，转化为小问题，最后同样由小规模结论，推解出问题的解。结论，推解出问题的解。上节上节下节下节第66页，共75页。3 3全面逐一尝试、比较全面逐一尝试、比较“蛮力法、蛮力法、“枚举法、枚举法、“递归回溯法递归回溯法 考虑到有这样一类问题，问题中不易考虑到有这样一类问题，问题中不易找到信息间的相互关系，也不能分解为独立的找到信息间的相互关系，也不能分解为独立的子问题子问题,似乎只有把各种可能情况都考虑到似乎只有把各种可能情况都考虑到,并并把全部解都列出来之后把全部解都列出来之后,才能判定和得到最优才能判定和得到最优解。对于规模不大的问题，这些策略简单方便解。对于规模不大的问题，这些策略简单方便;而当问题的计算复杂度高且计算量很大时而当问题的计算复杂度高且计算量很大时,还还是考虑采用是考虑采用“动态规划法这个更有效的算法动态规划法这个更有效的算法策略。策略。上节上节 下节下节第67页，共75页。枚举法算法的实现依赖于循环枚举法算法的实现依赖于循环,通过循环嵌套枚举问题中各种通过循环嵌套枚举问题中各种可能的情况可能的情况,如八皇后问题能用八重循环嵌套枚举。而对于规模不固如八皇后问题能用八重循环嵌套枚举。而对于规模不固定的问题就无法用固定重数的循环嵌套来枚举了定的问题就无法用固定重数的循环嵌套来枚举了,有的问题可能通过有的问题可能通过变换枚举对象也能用循环嵌套枚举实现变换枚举对象也能用循环嵌套枚举实现,但更多的任意指定规模的问但更多的任意指定规模的问题是靠递归回朔法来题是靠递归回朔法来“枚举或枚举或“遍历各种可能的情况。比方遍历各种可能的情况。比方n皇皇后问题只能用后问题只能用“递归回朔法通过递归实现当然可以通过栈递归回朔法通过递归实现当然可以通过栈,而不而不用递归。用递归。上节上节下节下节第68页，共75页。4 4算法策略的中心思想算法策略的中心思想 所所有有算算法法策策略略的的中中心心思思想想就就是是用用算算法法的的根根本本工工具具循循环环机机制制和和递递归归机机制制实实现现算算法法。递递推推法法自自然然不不用用多多说说，贪贪婪婪算算法法就就是是逐逐步步决决策策解解决决问问题题，动态规划也是。动态规划也是。上节上节 下节下节第69页，共75页。4.6.3算法策略侧重的问题类型一般我们在实际应用中遇到的问题主要分为四类:判定性问题、计算问题、最优化问题和构造性问题。递推法、递归法算法较适合解决判定性问题、计算问题。“贪婪算法、“分治法、“动态规划法与“枚举法较适合解最优化问题。构造性问题更多地依赖于人的经历和抽象能力，算法一般是人类智能充分对问题解决步骤细化后才能得到算法，少有通用的算法策略。当然也有一些问题在构造过程中使用通用的算法策略。上节下节第70页，共75页。下面就最优化问题讨论如下：下面就最优化问题讨论如下：在现实生活中，有这样的问题：他有在现实生活中，有这样的问题：他有n n个输入个输入,而而他的解就由他的解就由n n个输入的某个子集组成，只是这个子集必个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。把那些必须满足的条件称须满足某些事先给定的条件。把那些必须满足的条件称为约束条件为约束条件;而把满足约定条件的子集称为该问题的可而把满足约定条件的子集称为该问题的可行解。显然行解。显然,满足约束条件的子集可能不止一个满足约束条件的子集可能不止一个,因此，因此，可行解一般来说是不唯一的。为了衡量可行解的优劣，可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也给出了一定的标准事先也给出了一定的标准,这些标准一般以函数形式给这些标准一般以函数形式给出出,这些函数称为目标函数。这些函数称为目标函数。那些使目标函数取极值那些使目标函数取极值的可行解，的可行解，称为最优解称为最优解,这一类需求取最优解的问题这一类需求取最优解的问题,又可根据描述约束条件和目标函数的又可根据描述约束条件和目标函数的 数学模型的特性数学模型的特性或求借问题方法的不同或求借问题方法的不同进展而细分为进展而细分为 线形规那么、整数规那么、非线形规线形规那么、整数规那么、非线形规那么、动态规划等那么、动态规划等问题。问题。上节上节 下节下节第71页，共75页。尽管各类规划问题都有一些相应的求解方法，但其中的某些问题，还尽管各类规划问题都有一些相应的求解方法，但其中的某些问题，还可用一种更直接的方法来求解，这种方法就叫贪心方法。可用一种更直接的方法来求解，这种方法就叫贪心方法。动态规划法是将问题实例归纳为更小的、动态规划法是将问题实例归纳为更小的、相似的子问题相似的子问题,并通过求解并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择出的所有选择,但不依赖于有待于做出的选择和子问题。但不依赖于有待于做出的选择和子问题。而分治法中的而分治法中的各个子问题是独立的各个子问题是独立的(即不包含公共的子子问题即不包含公共的子子问题),因此一旦递归地求出各因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但缺乏子问题的解后，便可自下而上地将子问题的解合并成问题的解。但缺乏的是的是,如果当前选择可能要依赖子问题的解时如果当前选择可能要依赖子问题的解时,那么难以通过局部的贪心那么难以通过局部的贪心策略到达全局最优解策略到达全局最优解;如果各子问题是不独立的如果各子问题是不独立的,那么分治法要做许多不那么分治法要做许多不必要的工作必要的工作,重复地解公共的子问题。重复地解公共的子问题。上节上节下节下节第72页，共75页。动态规划在解决不独立子问题时，是分为假设干个阶段进展的动态规划在解决不独立子问题时，是分为假设干个阶段进展的,而且在任一阶段后的行为都仅依赖而且在任一阶段后的行为都仅依赖i阶段的过程状态阶段的过程状态,而与而与i阶段之前的阶段之前的过程如何到达这种状态的方法无关过程如何到达这种状态的方法无关,这样的过程就构成一个多阶段决策这样的过程就构成一个多阶段决策过程。过程。动态规划不仅求出了当前状态到目标状态的最优值动态规划不仅求出了当前状态到目标状态的最优值,而且同时而且同时求出了到中间状态的最优值。求出了到中间状态的最优值。显然显然,用枚举的方法从所有可能的决策序列中选取最优决策序列是一用枚举的方法从所有可能的决策序列中选取最优决策序列是一种最笨的方法。种最笨的方法。上节上节下节下节第73页，共75页。最优性原理指出,过程的最优序列有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。如果求解问题的最优性原理成立,那么说明用动态规划方法有可能解决该问题。而解决问题的关键在于获得各阶段间的递推关系式。因此,从某种意义上说动态规划是一种找出子问题间递推或递归关系的方法。动态规划相比一般穷举也存在一定缺点:空间占据过多,但对于空间需求量不大的题目来说,动态规划无疑是最正确方法！上节下节第74页，共75页。人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。第75页，共75页。