考研复习资料大总结.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分治法,大整数的乘法,请设计一个有效的算法，可以进行两个,n,位大整数的乘法运算,小学的方法：,O(n,2,),效率太低,分治法,:,X=,Y=,X=,a,2,n/2,+,b,Y=,c,2,n/2,+,d,XY=,ac,2,n,+(,ad,+,bc,)2,n/2,+,bd,a,b,c,d,复杂度分析,T(n)=O(n,2,),没有改进,分治法,大整数的乘法,请设计一个有效的算法，可以进行两个,n,位大整数的乘法运算,小学的方法：,O(n,2,),效率太低,分治法,:,XY=,ac,2,n,+(,ad,+,bc,)2,n/2,+,bd,为了降低时间复杂度，必须减少乘法的次数。,XY=,ac,2,n,+(,a,-,b,)(,d,-,c,)+,ac,+,bd,)2,n/2,+,bd,XY=,ac,2,n,+(,a,+,b,)(,d,+,c,)-,ac,-,bd,)2,n/2,+,bd,复杂度分析,T(n)=O(n,log3,)=O(n,1.59,),较大的改进,细节问题,：两个,XY,的复杂度都是,O(n,log3,),，,但考虑到,a+c,b+d,可能得到,m+1,位的结果，使问题的规模变大，故不选择第,2,种方案。,分治法,循环赛日程表,设计一个满足以下要求的比赛日程表：,(1),每个选手必须与其他,n-1,个选手各赛一次；,(2),每个选手一天只能赛一次；,(3),循环赛一共进行,n-1,天。,按分治策略，将所有的选手分为两半，,n,个选手的比赛日程表就可以通过为,n/2,个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下,2,个选手时，比赛日程表的制定就变得很简单。这时只要让这,2,个选手进行比赛就可以了。,1,2,3,4,5,6,7,8,2,1,4,3,6,5,8,7,3,4,1,2,7,8,5,6,4,3,2,1,8,7,6,5,5,6,7,8,1,2,3,4,6,5,8,7,2,1,4,3,7,8,5,6,3,4,1,2,8,7,6,5,4,3,2,1,分治法,线性时间选择,给定线性序集中,n,个元素和一个整数,k,，,1kn,，,要求找出这,n,个元素中第,k,小的元素,template,Type,RandomizedSelect,(Type,a,int,p,int,r,int,k),if(p=r)return ap;,int,i=,RandomizedPartition(a,p,r,),j=i-p+1;,if(k=j)return,RandomizedSelect(a,p,i,k,);,else return RandomizedSelect(a,i+1,r,k-j);,在最坏情况下，算法,randomizedSelect,需要,O(n,2,),计算时间,但可以证明，算法,randomizedSelect,可以在,O(n),平均时间内找出,n,个输入元素中的第,k,小元素。,分治法,线性时间选择,如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的,2,个子数组的长度都至少为原数组长度的,倍,(01,是某个正常数,),，那么就可以,在最坏情况下,用,O(n),时间完成选择任务。,例如，若,=9/10,，,算法递归调用所产生的子数组的长度至少缩短,1/10,。所以，在最坏情况下，算法所需的计算时间,T(n),满足递归式,T(n)T(9n/10)+O(n),。,由此可得,T(n)=O(n),。,将,n,个输入元素划分成,n/5,个组，每组,5,个元素，只可能有一个组不是,5,个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共,n/5,个。,递归调用,select,来找出这,n/5,个元素的中位数。如果,n/5,是偶数，就找它的,2,个中位数中较大的一个。以这个元素作为划分基准。,分治法,线性时间选择,设所有元素互不相同。在这种情况下，找出的基准,x,至少比,3(n-5)/10,个元素大，因为在每一组中有,2,个元素小于本组的中位数，而,n/5,个中位数中又有,(n-5)/10,个小于基准,x,。,同理，基准,x,也至少比,3(n-5)/10,个元素小。而当,n75,时，,3(n-5)/10n/4,所以按此基准划分所得的,2,个子数组的长度都至少缩短,1/4,。,Type,Select,(Type a,int,p,int,r,int,k),if(r-p75),用某个简单排序算法对数组,ap:r,排序,;,return ap+k-1;,;,for(,int,i=0;i=(r-p-4)/5;i+),将,ap+5*i,至,ap+5*i+4,的第,3,小元素,与,ap+i,交换位置,;,/,找中位数的中位数，,r-p-4,即上面所说的,n-5,Type x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);,int,i=Partition(a,p,r,x),j=i-p+1;,if(k=j)return Select(a,p,i,k);,else return Select(a,i+1,r,k-j);,复杂度分析,T(n)=,O(n),上述算法将每一组的大小定为,5,，并选取,75,作为是否作递归调用的分界点。这,2,点保证了,T(n),的递归式中,2,个自变量之和,n/5+3n/4=19n/20=,n,，,0,1,。,这是使,T(n)=O(n),的关键之处。当然，除了,5,和,75,之外，还有其他选择。,动态规划,0-1,背包问题,给定,n,种物品和一背包。物品,i,的重量是,w,i,，其价值为,v,i,，背包的容量为,C,。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大,?,0-1,背包问题是一个特殊的整数规划问题。,动态规划,0-1,背包问题,设所给,0-1,背包问题的,子问题,的最优值为,m(i,，,j),，即,m(i,，,j),是背包容量为,j,，可选择物品为,i,，,i+1,，,，,n,时,0-1,背包问题的最优值。由,0-1,背包问题的最优子结构性质，可以建立计算,m(i,，,j),的递归式如下。,考虑下列实例：,n=3,物品重量,(w,1,w,2,w,3,)=(2,3,4),物品价值,(p,1,p,2,p,3,)=(1,2,5),背包容量,C=6,解：,m(1,6)=max m(2,6),m(2,6-2)+1 ,m(2,6)=max m(3,6),m(3,6-3)+2 ,m(2,4)=max m(3,4),m(3,4-3)+2 ,m(3,6)=5,m(3,3)=0,=5,=5,=6,解向量为,(x,1,x,2,x,3,)=(1,0,1),m(3,4)=5,m(3,1)=0,动态规划,最长公共子序列,若给定序列,X=,x,1,x,2,x,m,，则另一序列,Z=,z,1,z,2,z,k,，是,X,的,子序列,是指存在一个,严格递增下标序列,i,1,i,2,i,k,使得对于,所有,j,=1,2,k,有：,z,j,=,x,i,j,。,例如，序列,Z=,B,C,D,B,是序列,X=,A,B,C,B,D,A,B,的子序列，相应的递增下标序列为,2,3,5,7,。,给定,2,个序列,X,和,Y,，当另一序列,Z,既是,X,的子序列又是,Y,的子序列时，称,Z,是序列,X,和,Y,的,公共子序列,。,给定,2,个序列,X=,x,1,x,2,x,m,和,Y=,y,1,y,2,y,n,，找出,X,和,Y,的最长公共子序列。,动态规划,最长公共子序列的结构,设序列,X=,x,1,x,2,x,m,和,Y=,y,1,y,2,y,n,的最长公共子序列为,Z=,z,1,z,2,z,k,，则,(1),若,x,m,=,y,n,，则,z,k,=,x,m,=,y,n,，且,Z,k-1,是,X,m-1,和,Y,n-1,的最长公共子序列。,(2),若,x,m,y,n,且,z,k,x,m,，则,Z,是,X,m-1,和,Y,的最长公共子序列。,(3),若,x,m,y,n,且,z,k,y,n,，则,Z,是,X,和,Y,n-1,的最长公共子序列。,由此可见，,2,个序列的最长公共子序列包含了这,2,个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有,最优子结构性质,。,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。,用,c,i,j,记录序列和的最长公共子序列的长度。其中，,X,i,=,x,1,x,2,x,i,；,Y,j,=,y,1,y,2,y,j,。当,i,=0,或,j,=0,时，空序列是,X,i,和,Y,j,的最长公共子序列。故此时,c,i,j,=0,。其它情况下，由最优子结构性质可建立递归关系如下：,计算最优值,由于在所考虑的子问题空间中，总共有,(,mn,),个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,void,LCSLength(int,m,，,int,n,，,char*x,，,char*y,，,int,*c,，,int,*b),int,i,，,j;,for(i=1;i=m;i+)ci0=0;,for(i=1;i=n;i+)c0i=0;,for(i=1;i=m;i+),for(j=1;j=cij-1),cij=ci-1j;bij=2,;,else,cij=cij-1;bij=3,;,构造最长公共子序列,void,LCS(int,i,，,int,j,，,char*x,，,int,*b),if(i=0|j=0)return;,if(bij=1),LCS(i-1,，,j-1,，,x,，,b);,cout,xi;,else if(bij=2)LCS(i-1,，,j,，,x,，,b);,else LCS(i,，,j-1,，,x,，,b);,贪心法,活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,贪心法,活动安排问题,设有,n,个活动的集合,E=,1,2,n,，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动,i,都有一个要求使用该资源的,起始时间,si,和一个,结束时间,fi,且,si,fi,。如果选择了活动,i,，则它在半开时间区间,si,fi,),内占用资源。,若区间,si,fi,),与区间,sj,fj,),不相交，则称,活动,i,与活动,j,是相容,的。也就是说，当,si,fj,或,sj,fi,时，活动,i,与活动,j,相容。,在下面所给出的解活动安排问题的贪心算法,:,int,greedySelector,(int,s,int,f,boolean,a),int,n=,s.length,;,a1=true;,int,j=1;,int,count=1;,for(,int,i=2;i=fj),ai=true;,j=i;,count+;,else ai=false;,return count;,各活动的起始时间和结束时间存储于数组,s,和,f,中且,按结束时间的非减序排列,贪心法,活动安排问题,由于输入的活动以其完成时间的,非减序,排列，所以算法,greedySelector,每次总是选择,具有最早完成时间,的相容活动加入集合,A,中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的,意义是,使剩余的可安排时间段极大化,，以便安排尽可能多的相容活动,。,算法,greedySelector,的效率极高。当输入的活动已按结束时间的非减序排列，算法只需,O,(,n,),的时间安排,n,个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用,O,(,nlog,n,),的时间重排。,贪心法,活动安排问题,例：,设待安排的,11,个活动的开始时间和结束时间,按结束时间的非减序排列,如下：,i,1,2,3,4,5,6,7,8,9,10,11,Si,1,3,0,5,3,5,6,8,8,2,12,fi,4,5,6,7,8,9,10,11,12,13,14,贪心法,活动安排问题,4.1,活动安排问题,算法,greedySelector,的计算过程,如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合,A,的活动，而空白长条表示的活动是当前正在检查相容性的活动。,i,1,2,3,4,5,6,7,8,9,10,11,Si,1,3,0,5,3,5,6,8,8,2,12,fi,4,5,6,7,8,9,10,11,12,13,14,贪心法,多机调度问题,多机调度问题,要求给出一种作业调度方案，使所给的,n,个作业在尽可能短的时间内由,m,台机器加工处理完成。,设有,n,个独立的作业,1,2,n,，,由,m,台相同的机器进行加工处理。作业,i,所需的处理时间为,t,i,。,这个问题是,NP,完全问题,，到目前为止还没有有效的解法。对于这一类问题,用,贪心选择策略,有时可以设计出较好的近似算法。,约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。,贪心法,多机调度问题,采用,最长处理时间作业优先,的贪心选择策略可以设计出解多机调度问题的较好的近似算法。,按此策略，当 时，只要将机器,i,的,0,t,i,时间区间分配给作业,i,即可。,当 时，首先将,n,个作业依其所需的处理时间,从大到小排序,。然后依此顺序将作业分配给空闲的处理机。,贪心法,多机调度问题,例如，,设,7,个独立作业,1,2,3,4,5,6,7,由,3,台机器,M1,，,M2,和,M3,加工处理。各作业所需的处理时间分别为,2,14,4,16,6,5,3,。按算法,Greedy,产生的作业调度如下图所示，所需的加工时间为,17,。,贪心法,最优装载,有一批集装箱要装上一艘载重量为,c,的轮船。其中集装箱,i,的重量为,W,i,。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。,1.,算法描述,最优装载问题可用贪心算法求解。,采用重量最轻者先装的贪心选择策略,，可产生最优装载问题的最优解。,最优装载问题可形式化描述为：,x,i,=,0,表示不装入集装箱,i,，,x,i,=,1,表示装入集装箱,i,。,贪心法,最优装载,贪心法,最优装载,float,loading,(float c,float w,int,x),int,n=w.length;,Element d=new Element n;,for(,int,i=0;i n;i+)di=new Element(wi,i);,MergeSort,(d);,/,按重量从小到大排序,float opt=0;,for(,int,i=0;i n;i+)xi=0;,for(,int,i=0;i n i+),xdi.i=1;,opt+=di.w;,c-=di.w;,return opt;,贪心法,最优装载,2.,贪心选择性质,可以证明最优装载问题具有贪心选择性质。,3.,最优子结构性质,最优装载问题具有最优子结构性质。,由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法,loading,的正确性。,算法,loading,的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为,O,(,nlog,n,),。,贪心法,汽车加油问题,问题描述,：,一辆汽车加满油后可行驶,n,公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。,编程任务：,对于给定的,n,和,k,个加油站位置，编程计算最少加油次数。,贪心法,汽车加油问题,数据输入：,输入,2,个正整数,n,和,k,，表示汽车加满油后可行驶,n,公里，且旅途中有,k,个加油站。输入,k+1,个整数，表示第,k,个加油站与第,k-1,个加油站之间的距离。第,0,个加油站表示出发地，汽车已加满油。第,k+1,个加油站表示目的地。,数据输出：,将编程计算出的最少加油次数输出。如果无法到达目的地，则输出“,No Solution,”,。,贪心法,汽车加油问题,最优子结构性质：,设,1i,1,i,2,i,k,m,是所述问题的一个最优解。容易看出，,i,2,i,3,i,k,是当出发地为,i,1,时的一个最优解，否则将导致,i,1,i,2,i,k,不是原问题的最优解。,贪心法,汽车加油问题,贪心选择性质,：,采用每次加满油后使汽车行驶尽可能远的贪心选择策略。设,1i,1,i,2,i,k,m,是一个最优解，如果汽车在加油站,i,1,不停靠加油站,j,1,再加油，则我们在,j,1,站停靠加油，其后再按最优解提供的停靠站加油，也能到达目的地，且停靠加油次数不会比最优次数更多。因此这是一个满足贪心选择性质的最优解。,回溯法,n,皇后问题,在,nn,格的棋盘上放置彼此不受攻击的,n,个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。,n,皇后问题等价于在,nn,格的棋盘上放置,n,个皇后，任何,2,个皇后不放在同一行或同一列或同一斜线上。,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,Q,Q,Q,Q,Q,Q,Q,Q,解向量：,(x,1,x,2,x,n,)，,x,i,表示皇后,i,放在棋盘的第,i,行第,x,i,列,显约束：,x,i,=,1,2,n,隐约束：,1),不同列：,x,i,x,j,2),不处于同一正、反对角线：,|,i-j|,|x,i,-x,j,|,回溯法,n,皇后问题,回溯法,n,皇后问题,boolean,place,(,int,k),for,(,int,j=1;jn)sum+;,else,for,(,int,i=1;in,时，表示算法已搜索到一个叶子结点，得到一个新的,n,皇后互不攻击放置方案，因此当前已找到的可行方案数,sum,增1。,当,in)sum+;,else,for(,int,i=1;i=m;i+),xt=i;,if(,ok(t,)backtrack(t+1);,boolean,ok(int,k),/,检查颜色可用性,for(,int,j=1;jn,时，表示算法已搜索到一个叶子结点，得到一个新的,m,着色方案方案，因此当前已找到的可,m,着色方案数,sum,增1。,当,i=n,时，当前扩展结点,Z,是解空间中的一个内部结点。该结点有,x,i,=,1,2,m,共,m,个儿子结点。对当前扩展结点,Z,的每一个儿子结点，由函数,ok,(),检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或减去不可行子树。,回溯法,图的,m,着色问题,回溯法,图的,m,着色问题,复杂度分析,图的,m,可着色问题的解空间树中内结点个数是,对于每一个内结点，在最坏情况下，用,ok,检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时,O(mn,),。因此，回溯法总的时间耗费是,