Divide-and-Conquer技术

,第三章,Divide-and-Conquer,技术,邹权（博士）,计算机科学系,3.1,Divide-and-Conquer,原理,3.2,整数乘法,3.3,矩阵乘法,3.4,Finding the closest pair of points,提要,3.1,Divide-and-Conquer,原理,Divide-and-Conquer,算法的设计,Divide-and-Conquer,算法的分析,设计过程分为三个阶段,Divide,：,整个问题划分为多个子问题,Conquer,：,求解各子问题(递归调用正设计的算法),Combine,：,合并子问题的解, 形成原始问题的解,Divide-and-Conquer,算法的设计,原始问题,求解子问题,子问题,子问题,子问题,求解子问题,求解子问题,子问题解,子问题解,子问题解,合并子解,问题分解,Divide,Conquer,Merge,原始问题的解,Homework,云计算、Map-Reduce、Hadoop、Mahout,分析过程,建立递归方程,求解,递归方程的建立方法,设输入大小为,n,T(n),为时间复杂性,当,nc,T(n)=,(1),Divide-and-Conquer,算法的分析,Divide,阶段的时间复杂性,划分问题为,a,个子问题。,每个子问题大小为,n/b,。,划分时间可直接得到=,D(n),Conquer,阶段的时间复杂性,递归调用,Conquer,时间,=,aT(n/b),Combine,阶段的时间复杂性,时间可以直接得到,=,C(n),总之,T(n)=,(1),if n1,使用,Master,定理,T(n)=,O,(,n,log3,)=O(,n,1.59,),算法的分析,3.,3,矩阵乘法,问题定义,输入,：,两个,n,n,矩阵,A,和,A,输出,：,X,和,Y,的积,通常，计算,XY,的时间复杂性位,O(n,3,),，,我们给出一个复杂性为,O(n,2.81,),的算法。,算法的数学基础,把,C=AB,中每个矩阵分成大小相同的,4,个子矩阵,每个子矩阵都是一个,n/2,n/2,矩阵,于是,=,展开并整理等式的右边，即得到计算的方法,M,1,= A,11,(B,12,- B,22,),M,2,= (A,11,+ A,12,) B,22,M,3,= (A,21,+ A,22,) B,11,M,4,= A,22,(B,21,- B,11,),M,5,= (A,11,+ A,22,) (B,11,+ B,22,),M,6,= (A,12,- A,22,) (B,21,+ B,22,),M,7,= (A,11,- A,12,) (B,11,+ B,12,),计算,n/2,n/2,矩阵的,10,个加减,和,7,个乘法,算法,C,11,= M,5,+ M,4,- M,2,+ M,6,C,12,= M,1,+ M,2,C,21,= M,3,+ M,4,C,22,= M,5,+ M,1, M,3, M,7,计算,n/2,n/2,矩阵的,8,个加减,18,个,n/2,n/2,矩阵加减法，每个需,O(n,2,),7,个,n/2,n/2,矩阵乘法,建立递归方程,T(n)=O(1) n=2,T(n)=7T(n/2) + O(n,2,) n2,使用,Master,定理求解,T(n),T(n) = O(n,log7,),O(n,2.81,),算法复杂性分析,3.,4 Finding the closest pair of points,问题定义,输入,：,Euclidean,空间上的,n,个点的集合,Q,输出,：,P,1, P,2,Q,Dis(,P,1, P,2,)=MinDis(,X, Y,) |,X, Y,Q,Dis(,X, Y,),是,Euclidean,距离,:,如果,X=(,x,1, x,2,), Y=(,y,1, y,2,),，则,一维,空间算法,利用排序的算法,算法,把,Q,中的点排序,通过排序集合的线性扫描找出最近点对,时间复杂性,T(,n,)=O(,n,log,n,),一维空间算法,(,续,),Divide-and-conquer,算法,Preprocessing:,如果,Q,中仅包含,2,个点，则返回这个点对,；,求,Q,中点的中位数,m,。,Divide:,1.,用,Q,中点坐标中位数,m,把,Q,划分为两个,大小相等的子集合,Q,1,= ,x,Q,|,x,m,Q,2,= ,x,Q,|,x,m,Q,1,Q,2,p,1,p,2,p,3,q,3,q,2,q,1,m,Conquer:,1.,递归地在,Q,1,和,Q,2,中找出最接近点对,(,p,1, p,2,),和,(,q,1, q,2,),Q,1,Q,2,p,1,p,2,p,3,q,3,q,2,q,1,m,2.,在,(,p,1, p,2,),、,(,q,1, q,2,),和某个,(,p,3, q,3,),之间选择最,接近点对,(,x, y,),其中,p,3,是,Q,1,中最大点,q,3,是,Q,2,中最小点，,(,x, y,),是,Q,中最接近点。,Merge:,时间复杂性,Divide,阶段需要,O(n),时间,Conquer,阶段需要,2T(n/2),时间,Merge,阶段,需要,O(n),时间,递归方程,T(n)= O(1) n,=,2,T(n) = 2T(n/2) + O(n) n,3,用,Master,定理求解,T(n),T(n) = O(n,log,n),二维空间算法,Divide-and-conquer,算法,Divide:,计算,Q,中各点,x-,坐标,的中位数,m,；,用垂线,L:x=m,把,Q,划分成两个大小相等的子集,合,Q,L,和,Q,R,，,Q,L,中点在,L,左边,Q,R,中点在,L,右边,.,Preprocessing:,如果,Q,中仅包含一个点，则算法结束,；,把,Q,中点分别按,x,-,坐标,值,和,y,-,坐标,值,排序,.,Divide:,递归地在,S,L,、,S,R,中找出最接近点对,:,(,p,1, p,2,),S,L,(,q,1, q,2,),S,R,2. d=min,Dis,(,p,1, p,2,),Dis,(,q,1,q,2,);,p,1,p,2,q,1,q,2,L: x=m,Q,L,Q,R,m-d,m+d,临界区,Merge:,1.,在临界区查找距离小于,d,的点对,(,p,l, q,r,),p,l,Q,L,q,r,Q,R,;,2.,如果找到，则,(,p,l,q,r,),是,Q,中最接近点对，否则,(,p,1, p,2,),和,(,q,1, q,2,),中距离最小者为,Q,中最接近,点对,.,关键是,(,p,l,q,r,),的搜索方法及其搜索时间,(,p,l, q,r,),的搜索方法,：,如果,(,p, q,),是最接近点对而且,p,Q,L,q,Q,R,则,dis,(,p, q,),d,，,(,p, q,),只能在下图的区域,D,.,若,p,在分割线,L,上，包含,(,p, q,),的区域,D,最大，嵌于,d,2d,的矩形,(,p,-,右邻域,),中，如下图所示,.,L,p,d,d,d,D,L,p,d,d,d,2d,D,p,-,右邻域,只包含,6,个点,对于任意,p,我们只需在,p-,右邻域中,点,q,最多,6,个,.,算法,1.,把临界区中所有点集合投影到分割线,L,上,;,2.,对于左临界区的每个点,p,考察,p-,右临界区的每个点,(,这样的点共有,6,个,),q,，如果,Dis(p, q)d,则令,d=Dis(p, q);,3.,如果,d,发生过变化,与最后的,d,对应的点对即为,(,p,l, q,r,),否则不存在,(,p,l, q,r,).,时间复杂性,Divide,阶段需要,O(n),时间,Conquer,阶段需要,2T(n/2),时间,Merge,阶段,需要,O(n),时间,递归方程,T(n)= O(1) n,=,2,T(n) = 2T(n/2) + O(n) n,3,用,Master,定理求解,T(n),T(n) = O(n,log,n),正确性分析,定理,1.,对于左临界区中的每个点,p,p,-,右邻域中仅,包含,6,个点。,证明,：,把,p,-,右邻域,划分为,6,个,(d/2),(2d/3),的矩形。,若,p,-,右邻域,中点数大于,6,由鸽巢原理，至少,有一个矩形中有两个点，设为,u,、,v.,(,x,u,-x,v,),2,+ (,y,u,-y,v,),2, (,d/2,),2,+(,2d/3,),2,=,25d,2,/36,即,Dis(u, v),5d/6,d,与,d,的定义矛盾。,2d/3,2d/3,2d/3,d/2,d/2,u,v,