第5章递归与分治策略冯2010.ppt

第5章递归与分治策略法DivideandConquerMethod,算法设计与分析本科生课程DesignandAnalysisofAlgorithm,冯思玲海南大学信息科学技术学院CollegeofInformationScienceandTechnology,HainanUniversitylily85161,2020/4/28,DivideandConquerMethod,2,第1章算法引论（6学时）第2章常用数学工具（3学时）第3章NP完全性理论（4.5学时）第4章蛮力法（3学时）第5章递归与分治策略（3学时）第6章减冶法（3学时）第7章动态规划（3学时）第8章贪心算法（4.5学时）第9章回溯法（4.5学时）第10章分支限界法（4.5学时）第11章概率算法（4.5学时）第12章近似算法（3学时）总复习（3学时）,课程目录,2020/4/28,DivideandConquerMethod,3,本章要点,5.1概述,5.2递归,5.3排序问题中的分治法,5.4组合问题中的分治法,5.5几何问题中的分治法,5.6实验项目最近对问题,2020/4/28,DivideandConquerMethod,4,5.1.1分治法的设计思想,5.1.2分治法的求解过程,概述,2020/4/28,DivideandConquerMethod,5,将一个难以直接解决的大问题，划分成一些规模较小的子问题，以各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。,分治法的设计思想：,概述-分治法思想,2020/4/28,DivideandConquerMethod,6,2.独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。,1.平衡子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k2、4,），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。,启发式规则：,概述-分治法思想,2020/4/28,DivideandConquerMethod,7,分治法的典型情况,概述-分治法思想,2020/4/28,DivideandConquerMethod,8,5.1.1分治法的设计思想,5.1.2分治法的求解过程,概述,2020/4/28,DivideandConquerMethod,9,一般来说，分治法的求解过程由以下三个阶段组成：（1）划分：既然是分治，当然要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。,概述-分治法的求解过程,2020/4/28,DivideandConquerMethod,10,概述-分治法的求解过程,2020/4/28,DivideandConquerMethod,11,例：计算an，应用分治技术得到如下计算方法,分析时间性能,2020/4/28,DivideandConquerMethod,12,讨论an的蛮力法计算复杂度为O(n)，因为：a=1;For(i=1;i1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1的划分组成。,(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。,前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,递归的概念,2020/4/28,DivideandConquerMethod,23,例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,正整数n的划分数p(n)=q(n,n)。,递归的概念,2020/4/28,DivideandConquerMethod,24,递归算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具。但是，因为递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。,递归小结,2020/4/28,DivideandConquerMethod,25,递归小结,优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,2020/4/28,DivideandConquerMethod,26,递归小结-分治法适用条件,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,2020/4/28,DivideandConquerMethod,27,递归小结-分治法基本步骤,divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题dividePintosmallersubinstancesP1,P2,.,Pk；/分解问题for(i=1,irj?r1rj,j，否则交换（3）ris1)s1=lefts;s2=0;rights=0;/再求解s2for(j=center+1;js2)s2=rights;sum=s1+s2;/计算情况的最大子段和if(sum=tr+s,棋盘覆盖问题,2020/4/28,DivideandConquerMethod,62,/覆盖右下角子棋盘if(dr=tr+s,棋盘覆盖问题,2020/4/28,DivideandConquerMethod,63,设T(k)是覆盖一个2k2k棋盘所需时间，从算法的划分策略可知，T(k)满足如下递推式：,解此递推式可得T(k)=O(4k)。由于覆盖一个2k2k棋盘所需的骨牌个数为(4k-1)/3，所以，算法5.8是一个在渐进意义下的最优算法。,棋盘覆盖问题,2020/4/28,DivideandConquerMethod,64,组合问题中的分治法,5.4.1最大子段和问题,5.4.2棋盘覆盖问题,5.4.3循环赛日程安排问题,2020/4/28,DivideandConquerMethod,65,本章要点,5.1概述,5.2递归,5.3排序问题中的分治法,5.4组合问题中的分治法,5.5几何问题中的分治法,5.6实验项目最近对问题,2020/4/28,DivideandConquerMethod,66,5.5几何问题中的分治法,5.5.1最近对问题,5.5.2凸包问题,2020/4/28,DivideandConquerMethod,67,最近对问题,设p1=(x1,y1),p2=(x2,y2),pn=(xn,yn)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。严格地讲，最接近点对可能多于一对，简单起见，只找出其中的一对作为问题的解。,2020/4/28,DivideandConquerMethod,68,用分治法解决最近对问题，很自然的想法就是将集合S分成两个子集S1和S2，每个子集中有n/2个点。然后在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，如果集合S中最接近的两个点都在子集S1或S2中，则问题很容易解决，如果这两个点分别在S1和S2中，问题就比较复杂了。,最近对问题,2020/4/28,DivideandConquerMethod,69,为了使问题易于理解，先考虑一维的情形。此时，S中的点退化为x轴上的n个点x1,x2,xn。用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S2含有点的个数相同。递归地在S1和S2上求出最接近点对(p1,p2)和(q1,q2)，如果集合S中的最接近点对都在子集S1或S2中，则d=min(p1,p2),(q1,q2)即为所求，如果集合S中的最接近点对分别在S1和S2中，则一定是(p3,q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。,最近对问题,2020/4/28,DivideandConquerMethod,70,按这种分治策略求解最近对问题的算法效率取决于划分点m的选取，一个基本的要求是要遵循平衡子问题的原则。如果选取m=(maxS+minS)/2，则有可能因集合S中点分布的不均匀而造成子集S1和S2的不平衡，如果用S中各点坐标的中位数（即S的中值）作为分割点，则会得到一个平衡的分割点m，使得子集S1和S2中有个数大致相同的点。,最近对问题,2020/4/28,DivideandConquerMethod,71,下面考虑二维的情形，此时S中的点为平面上的点。为了将平面上的点集S分割为点的个数大致相同的两个子集S1和S2，选取垂直线x=m来作为分割线，其中，m为S中各点x坐标的中位数。由此将S分割为S1=pS|xpm和S2=qS|xqm。递归地在S1和S2上求解最近对问题，分别得到S1中的最近距离d1和S2中的最近距离d2，令d=min(d1,d2)，若S的最近对(p,q)之间的距离小于d，则p和q必分属于S1和S2，不妨设pS1，qS2，则p和q距直线x=m的距离均小于d，所以，可以将求解限制在以x=m为中心、宽度为2d的垂直带P1和P2中，垂直带之外的任何点对之间的距离都一定大于d。,最近对问题,2020/4/28,DivideandConquerMethod,72,S1=pS|xpm,S2=qS|xqm,最近对问题,2020/4/28,DivideandConquerMethod,73,对于点pP1，需要考察P2中的各个点和点p之间的距离是否小于d，显然，P2中这样点的y轴坐标一定位于区间y-d,y+d之间，而且，这样的点不会超过6个。,2020/4/28,DivideandConquerMethod,74,应用分治法求解含有n个点的最近对问题，其时间复杂性可由下面的递推式表示：合并子问题的解的时间f(n)O(1)，根据1.2.4节的主定理，可得T(n)=O(nlog2n)。,最近对问题,2020/4/28,DivideandConquerMethod,75,4.5几何问题中的分治法,5.5.1最近对问题,5.5.2凸包问题,2020/4/28,DivideandConquerMethod,76,凸包问题,设p1=(x1,y1),p2=(x2,y2),pn=(xn,yn)是平面上n个点构成的集合S，并且这些点按照x轴坐标升序排列。几何学中有这样一个明显的事实：最左边的点p1和最右边的点pn一定是该集合的凸包顶点（即极点）。设p1pn是从p1到pn的直线，这条直线把集合S分成两个子集：S1是位于直线左侧和直线上的点构成的集合，S2是位于直线右侧和直线上的点构成的集合。S1的凸包由下列线段构成：以p1和pn为端点的线段构成的下边界，以及由多条线段构成的上边界，这条上边界称为上包。类似地，S2中的多条线段构成的下边界称为下包。整个集合S的凸包是由上包和下包构成的。,2020/4/28,DivideandConquerMethod,77,凸包问题,pmax,2020/4/28,DivideandConquerMethod,78,快包的思想是：首先找到S1中的顶点pmax，它是距离直线p1pn最远的顶点，则三角形pmaxp1pn的面积最大。S1中所有在直线p1pmax左侧的点构成集合S1,1，S1中所有在直线pnpmax右侧的点构成集合S1,2，包含在三角形pmaxp1pn之中的点可以不考虑了。递归地继续构造集合S1,1的上包和集合S1,2的上包，然后将求解过程中得到的所有最远距离的点连接起来，就可以得到集合S1的上包。,凸包问题,S1,1,S1,2,2020/4/28,DivideandConquerMethod,79,接下来的问题是如何判断一个点是否在给定直线的左侧（或右侧）？几何学中有这样一个定理：如果p1=(x1,y1),p2=(x2,y2),p3=(x3,y3)是平面上的任意三个点，则三角形p1p2p3的面积等于下面这个行列式的绝对值的一半：,当且仅当点p3=(x3,y3)位于直线p1p2的左侧时，该式的符号为正。可以在一个常数时间内检查一个点是否位于两个点确定的直线的左侧，并且可以求得这个点到该直线的距离。,凸包问题,2020/4/28,DivideandConquerMethod,80,复杂度的讨论平均情况：O(nlog2n)最坏情况：O（n2）蛮力法：O（n3）,凸包问题,2020/4/28,DivideandConquerMethod,81,本章要点,5.1概述,5.2递归,5.3排序问题中的分治法,5.4组合问题中的分治法,5.5几何问题中的分治法,5.6实验项目最近对问题,2020/4/28,DivideandConquerMethod,82,5.6实验项目最近对问题,1.实验题目设p1=(x1,y1),p2=(x2,y2),pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。,2.实验目的（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。,3.实验要求（1）分别用蛮力法和分治法求解最近对问题；（2）分析算法的时间性能，设计实验程序验证分析结论。,2020/4/28,DivideandConquerMethod,83,5.6实验项目最近对问题,2020/4/28,DivideandConquerMethod,84,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:,a,b,c,d,复杂度分析T(n)=O(n2)没有改进,X=Y=X=a2n/2+bY=c2n/2+dXY=ac2n+(ad+bc)2n/2+bd,2020/4/28,DivideandConquerMethod,85,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:,XY=ac2n+(ad+bc)2n/2+bd为了降低时间复杂度，必须减少乘法的次数。XY=ac2n+(a-c)(b-d)+ac+bd)2n/2+bdXY=ac2n+(a+c)(b+d)-ac-bd)2n/2+bd,复杂度分析T(n)=O(nlog3)=O(n1.59)较大的改进,细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。,2020/4/28,DivideandConquerMethod,86,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:O(n1.59)较大的改进更快的方法?,如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换(FastFourierTransform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。是否能找到线性时间的算法？目前为止还没有结果。,2020/4/28,DivideandConquerMethod,87,Strassen矩阵乘法,A和B的乘积矩阵C中的元素Ci,j定义为:,若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。因此，算出矩阵C的个元素所需的计算时间为O(n3),传统方法：O(n3),2020/4/28,DivideandConquerMethod,88,Strassen矩阵乘法,使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：,传统方法：O(n3)分治法:,由此可得：,2020/4/28,DivideandConquerMethod,89,复杂度分析T(n)=O(n3)没有改进,2020/4/28,DivideandConquerMethod,90,Strassen矩阵乘法,传统方法：O(n3)分治法:,为了降低时间复杂度，必须减少乘法的次数。,2020/4/28,DivideandConquerMethod,91,复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进,2020/4/28,DivideandConquerMethod,92,Strassen矩阵乘法,传统方法：O(n3)分治法:O(n2.81)更快的方法?,Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.376)是否能找到O(n2)的算法？目前为止还没有结果。,2020/4/28,DivideandConquerMethod,93,线性时间选择,给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素,privatestaticComparablerandomizedSelect(intp,intr,intk)if(p=r)returnap;inti=randomizedpartition(p,r),j=i-p+1;if(k=j)returnrandomizedSelect(p,i,k);elsereturnrandomizedSelect(i+1,r,k-j);,在最坏情况下，算法randomizedSelect需要O(n2)计算时间但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。,2020/4/28,DivideandConquerMethod,94,线性时间选择,如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。,例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n)。由此可得T(n)=O(n)。,2020/4/28,DivideandConquerMethod,95,将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5