考研复习资料大汇总(ppt 42页)

分治法大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:,X=Y=X=a2n/2+bY=c2n/2+dXY=ac2n+(ad+bc)2n/2+bd,a,b,c,d,复杂度分析T(n)=O(n2)没有改进,分治法大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:,XY=ac2n+(ad+bc)2n/2+bd为了降低时间复杂度，必须减少乘法的次数。XY=ac2n+(a-b)(d-c)+ac+bd)2n/2+bdXY=ac2n+(a+b)(d+c)-ac-bd)2n/2+bd,复杂度分析T(n)=O(nlog3)=O(n1.59)较大的改进,细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。,分治法循环赛日程表,设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。,按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,分治法线性时间选择,给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素,templateTypeRandomizedSelect(Typea,intp,intr,intk)if(p=r)returnap;inti=RandomizedPartition(a,p,r),j=i-p+1;if(k=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);,在最坏情况下，算法randomizedSelect需要O(n2)计算时间但可以证明，算法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。,TypeSelect(Typea,intp,intr,intk)if(r-p75)用某个简单排序算法对数组ap:r排序;returnap+k-1;for(inti=0;i=(r-p-4)/5;i+)将ap+5*i至ap+5*i+4的第3小元素与ap+i交换位置;/找中位数的中位数，r-p-4即上面所说的n-5Typex=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x),j=i-p+1;if(k=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);,复杂度分析T(n)=O(n),上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=n，01。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。,动态规划0-1背包问题,给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为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,物品重量(w1,w2,w3)=(2,3,4),物品价值(p1,p2,p3)=(1,2,5),背包容量C=6解：,m(1,6)=maxm(2,6),m(2,6-2)+1,m(2,6)=maxm(3,6),m(3,6-3)+2,m(2,4)=maxm(3,4),m(3,4-3)+2,m(3,6)=5m(3,3)=0,=5,=5,=6,解向量为(x1,x2,x3)=(1,0,1),m(3,4)=5m(3,1)=0,动态规划最长公共子序列,若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列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=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。,动态规划最长公共子序列的结构,设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，则(1)若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。(2)若xmyn且zkxm，则Z是Xm-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。,由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时cij=0。其它情况下，由最优子结构性质可建立递归关系如下：,计算最优值,由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,voidLCSLength(intm，intn，char*x，char*y，int*c，int*b)inti，j;for(i=1;i=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;,构造最长公共子序列voidLCS(inti，intj，char*x，int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1，j-1，x，b);coutxi;elseif(bij=2)LCS(i-1，j，x，b);elseLCS(i，j-1，x，b);,贪心法活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,贪心法活动安排问题,设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间si,fi)内占用资源。若区间si,fi)与区间sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。,在下面所给出的解活动安排问题的贪心算法:intgreedySelector(ints,intf,booleana)intn=s.length;a1=true;intj=1;intcount=1;for(inti=2;i=fj)ai=true;j=i;count+;elseai=false;returncount;,各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列,贪心法活动安排问题,由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,贪心法活动安排问题,例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：,贪心法活动安排问题,4.1活动安排问题,算法greedySelector的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。,贪心法多机调度问题,多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。设有n个独立的作业1,2,n，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。,约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。,贪心法多机调度问题,采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。按此策略，当时，只要将机器i的0,ti时间区间分配给作业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的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。1.算法描述,最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。,最优装载问题可形式化描述为：,xi=0表示不装入集装箱i，xi=1表示装入集装箱i。,贪心法最优装载,贪心法最优装载,floatloading(floatc,floatw,intx)intn=w.length;Elementd=newElementn;for(inti=0;in;i+)di=newElement(wi,i);MergeSort(d);/按重量从小到大排序floatopt=0;for(inti=0;in;i+)xi=0;for(inti=0;in,贪心法最优装载,2.贪心选择性质可以证明最优装载问题具有贪心选择性质。3.最优子结构性质最优装载问题具有最优子结构性质。,由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为O(nlogn)。,贪心法汽车加油问题,问题描述：一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。编程任务：对于给定的n和k个加油站位置，编程计算最少加油次数。,贪心法汽车加油问题,数据输入：输入2个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。输入k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。数据输出：将编程计算出的最少加油次数输出。如果无法到达目的地，则输出“NoSolution”。,贪心法汽车加油问题,最优子结构性质：设1i1i2ikm是所述问题的一个最优解。容易看出，i2i3ik是当出发地为i1时的一个最优解，否则将导致i1,i2,ik不是原问题的最优解。,贪心法汽车加油问题,贪心选择性质：采用每次加满油后使汽车行驶尽可能远的贪心选择策略。设1i1i2ikm是一个最优解，如果汽车在加油站i1不停靠加油站j1再加油，则我们在j1站停靠加油，其后再按最优解提供的停靠站加油，也能到达目的地，且停靠加油次数不会比最优次数更多。因此这是一个满足贪心选择性质的最优解。,回溯法n皇后问题,在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋