分治与递归策略课件bjvp.pptx

《分治与递归策略课件bjvp.pptx》由会员分享，可在线阅读，更多相关《分治与递归策略课件bjvp.pptx（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法分析与设计1第2讲分治与递归策略v2.1 分治算法的基本思想v2.2 递归概念 v2.3 典型分治算法举例算法分析与设计2算法总体思想 将一个难以直接解决的规模较大的问题分解为若干个规模较小的子问题，并各个击破，分而治之。n/16 n n/4 n/4 n/4 n/4n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16算法分析与设计3 将求出的较小规模的问题解合并成一个较大规模的问题解，并自底向上地求出原问题的解。最顶层问题a 为分解的子问题数量；n/b 为每个子问题的数据规模；f(n)为合并子问

2、题解所消耗的时间。算法分析与设计42.1 分治算法的基本思想 分治算法的基本思想是将一个规模为n的问题分解为a个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。算法分析与设计5分治算法所能解决问题一般具有以下几个特征：缩小问题规模可以降低解决问题的难度；可以将子问题的解合并为原问题解；问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。算法分析与设计6分治算法的算法框架divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决规模小的问题/将问题P 分解为子问题P1,P2,.,Pa；fo

3、r(i=1,i=a,i+)yi=divide-and-conquer(Pi);/递归的求解各子问题 return merge(y1,.,ya);/合并为原问题的解算法分析与设计7 一个分治算法将规模为n的问题分成a个规模为nb的子问题。设分解阈值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为a个子问题以及用merge将a个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治算法解规模为|P|=n的问题所需的计算时间，则有下列递归方程：通过求解递归方程得到递归算法的时间复杂性。分治算法的复杂性分析算法分析与设计8v替换方法v递归树方法v公式法求解递归

4、方程的三种方法：算法分析与设计9替换方法v替换方法的主要思想是首先推测出递归方程的解，然后代入递归方程，查看是否满足条件。v适用比较容易猜出递归解的情形。猜测出递归解的形式 用数学归纳法找出使解真正有效的常数v 替换方法解递归方程的基本步骤：算法分析与设计10例：T(n)=2T(n/2)+n（2路归并)假设解对n/2成立，即T(n/2)c(n/2)lg(n/2)将其对递归方程进行替换，得：T(n)=2T(n/2)+n 2(c(n/2)lg(n/2)+n cnlg(n/2)+n cnlgn-cnlg2+n=cnlgn-cn+n 当c1时，显然cnlgn-cn+n cnlgn 根据O符号定义，证明

5、猜测正确。数学归纳法：v 猜测出解为T(n)=O(nlgn)v 证明存在某个常数c，使得T(n)cnlgn算法分析与设计11递归树方法v 构造递归树的方法就是展开递归方程，然后将树中每层的时间求和，最终获得算法的时间复杂性。v用递归树方法求解递归方程的基本步骤:v递归树可以方便地推测递归方程的解，是描述分治算法的运行时间复杂性的有效手段。利用递归树推测出一个解 利用替换方法进行证明算法分析与设计12例：T(n)=3T(n/4)+cn2 T(n)算法分析与设计13log4n+1nlog4 3O(nlog4 3)算法分析与设计v 现在，我们来计算一下，有多少个叶节点。第1层有3个节点，第2层有32

6、个节点，依次类推，第k层有3k个节点，当k=log4n，即为叶节点，因此，叶节点的个数为，而每个叶节点需要的时间为T(1),因此，整个叶节点的时间为。14l 递归树总共有多少层？当递归树展开一层，其规模为n/4，当递归树展开到第2层时，其规模为n/16=n/42，依次类推，当展开到第k层时，其规模为n/4k=1时，不再展开，由此可以求得递归树的层数为k=log4n。算法分析与设计15将递归树每一层的时间累加，可得：i=0 所以，由递归树猜测T(n)=O(n2)随后，再利用数学归纳法证明。算法分析与设计16 其中，a1，b1是常数，f(n)是一个渐进函 数，描述划分问题与合并解的时间复杂性。n/

7、b可以是，也可以是 公式法上述方程描述了如下算法的运行时间：将一个规模为n的问题划分为a个规模为n/b的子问题，其中a和b为正常数。分别递归地解决a个子问题，解每个子问题所需时间为T(n/b)。划分原问题和合并子问题的解所需要的时间由f(n)决定算法分析与设计17定理：上述递归方程含有三种情形的渐进界：（1）对于某个常数 如果 则（2）如果 则（3）对某个常数 如果 且对某个常数 c 1 以及任意足够大的n,有af(n/b)cf(n),则 算法分析与设计18定理含义将f(n)与 进行比较，当 较大时，相等时 当 较小时，结论：可以通过尽量减少子问题的个数或者减少f(n)的数量级来增强分治算法的

8、有效性。从定理中可以看出，公式法只要记住三种情形，就可以很容易地确定许多递归方程的解。算法分析与设计19例1：T(n)=9T(n/3)+n由上式可知，a=9，b=3，f(n)=n,且又因为对于 有满足定理（1），因此，算法分析与设计20例2：T(n)=T(2n/3)+1由上式可知a=1,b=3/2,f(n)=1，且又因为满足定理（2），因此算法分析与设计212.2 递归概念 分治算法 递归技术直接或间接地调用自身的算法称为递归算法。在定义函数时调用到函数自身称为递归函数。分治算法递归技术 分治与递归像一对孪生兄弟分治算法的特征：将较大规模的问题分解为若干个较小规模的子问题，每个子问题的求解过程

9、与原问题一样，并利用自底向上的求解策略得到最终的解。算法分析与设计22递归应用举例1:Fibonacci数列边界条件递归方程边界条件与递归方程是递归函数的二要素。无穷2阶数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。递归定义为：算法分析与设计23 A(1,0)=2 A(0,m)=1 m0 A(n,0)=n+2 n2 A(n,m)=A(A(n-1,m),m-1)n,m1递归应用举例2:Ackerman函数算法分析与设计24m=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，A(1,2)=A(A(0,2),1)=A(1,1)=2 可以得出A(

10、n,2)=2n。m=3时，类似的可以推出A(1,0)=2A(0,m)=1 m0A(n,0)=n+2 n2A(n,m)=A(A(n-1,m),m-1)n,m1Ackerman函数的特征：A(n，m)的自变量m的每一个值都定义了一个单变量函数。m=0时，A(n,0)=n+2m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，A(1,1)=2 可以得出A(n,1)=2*n算法分析与设计25递归应用举例3:排列问题求解n个元素r1,r2,rn的全排列。n个元素的全排列有n!种可能。解题基本方法：（1）固定位置放元素（2）固定元素找位置算法分析与设计26假设R=r1,r2,rn是待

11、排列的n个元素，Ri=R-ri。假设集合Ri中元素的全排列记为perm(Ri)。(ri)perm(Ri)表示在全排列perm(Ri)的每一个排列的第一个位置加前缀ri得到的排列。当n=1时，perm(R)=(r)其中r是集合R中唯一的元素；当n1时，perm(R)的全排列为：(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)方法1：固定位置找元素算法分析与设计27递归公式算法分析与设计28算法分析与设计29将每个元素交换到固定位置上，并求解其余位置元素的全排列。举例，03共4个数值的全排列思路？算法分析与设计30假设:要求Pm、Pm+1、Pn的全排列:5.值得注意的是

12、，将Pm和某个Pk交换，求出剩余元素的所有排列后，为 了避免重复，发生混乱，必须将Pm 和Pk交换回去，然后才能继续Pm 和PK+1的交换。4.当问题规模降为求一个元素Pm的全排列时，问题就极为简单，可作为 递归出口。3.然后依次考虑Pm+3，,Pn。2.然后考虑Pm+1，通过交换Pm和Pm+1，这样我们仍然只要考虑求剩 余元素Pm+1、Pm+2,Pn的所有排列即可。1.需要先考虑Pm，如果能够求出剩余元Pm+1、Pm+2、，Pn 的所有排列，我们只需将Pm放到每个排列的开头。算法分析与设计31算法分析与设计32void perm(int r,int i,int n)/r存放R集合元素，r0r

13、n/i,n 表示目前求解的全排列起始与终止位置 if（只有一个元素）/递归边界条件 显示当前排列；else 依次将i n 之间的每个元素交换/递归到第i 个位置，并用同样的方法（递归）求解i+1n 之间的全排列 算法分析与设计33void perm(int r,int i,int n)if(i=n)/只有一个数值 for(int j=0;j=n;j+)/输出结果 coutrj;coutendl;else for(int j=i;j=n;j+)swap(r,i,j);/交换ri与rj perm(r,i+1,n);/计算i+1 n 全排列 swap(r,i,j);/交换ri与rj 算法分析与设计3

14、4 将n放在p3位置上，并用p1.2和p4.n产生n-1个元素的全排列；方法2：固定元素找位置 元素放置位置：p1pn 直到将n放在pn位置上，并用p1.n-1产生n-1个 元素的全排列。.将n放在p1位置上，并用p2.n产生n-1个元素的全排列；基本过程：在n-1 个元素的全排列基础上，将某个元素插入到每个位置上，进而得出n 个元素的全排列。将n放在p2位置上，并用p1和p3.n产生n-1个元素的全排列；算法分析与设计35321,312,231,132,213,123算法分析与设计36void perm2(int p,int n)/n=NUM-1/p1pn放置元素，初始为0，/n为当前参与排

15、列的元素数量,1,2,3,n if(参与排列的数据数量为0)输出结果 else 依次将n放在每个位置，并采用同样的方法求解另外n-1元素的全排列；算法分析与设计37void perm2(int p,int n)if(n=0)/元素集合为空 for(int i=1;i=NUM;i+)/输出结果 coutpi;coutendl;else for(int i=1;i=NUM;i+)if(pi=0)pi=n;perm2(p,n-1);pi=0;初始：p1.n=0;perm(p,n);NUM为n+1例如：n=3，NUM=4算法分析与设计38实现过程v注意：在n放定一个位置pK，找到剩下n-1个元素的所有

16、 排列后，在找n的下一个可放置位置时，即把n放到位置 Pk+1前，原来放n的位置pK一定要置0。否则，将有某 些元素找不到位置。v 依次递归下去，直到数组没有为0 的元素为止。v我们初始化数组p1.n的值为0，对于元素n，可以依次把它 放到数组的p1,p2,.,pn位置，在n放定一个位置后pK 后，剩下的n-1个元素可以放在那些值为0的数组元素p1.k-1 和pk+1.n上。算法分析与设计39递归小结递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。优点：缺点：算

17、法分析与设计40给定已按升序排列的n个元素a0:n-1，现要在这n个元素中找出一个特定元素x。分析：v 搜索范围越小，越容易确定解；v 该问题可以分解为若干个规模较小的相同问题;v 分解出的子问题的解就是原问题的解；v 分解出的各个子问题是相互独立的。2.3节 分治算法举例1：二分搜索技术分析：此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治算法的基本条件。算法分析与设计41templat int binarySearch(T a,int x,int n)int left=0;int right=n-1;while(left amiddle)left=mid

18、dle+1;else right=middle-1;return-1;/未找到x算法复杂性分析：每执行一次while循环，搜索范围缩小一半。因此，在最坏情况下，while循环被执行了O(lgn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(lgn)算法分析与设计两个n位二进制大整数乘法运算的基本方法:(1)小学的方法：时间复杂性 效率太低42分治算法举例2：大整数的乘法算法分析与设计43X=A 2n/2+BY=C 2n/2+D A B C DX=Y=(2)分治算法:注意：乘以2n表示向左位移n位，这个运算耗时复杂性分析XY=(A 2n/2+B)(C 2n/2+

19、D)=AC 2n+(AD+BC)2n/2+BD乘法4次，加法3次，位移2次算法分析与设计44将公式：XY=AC 2n+(AD+BC)2n/2+BD变换为：XY=AC 2n+(A-B)(D-C)+AC+BD)2n/2+BD乘法：3次；加减法：6次；位移：2次算法分析与设计45for(int i=0;i n;i+)for(int j=0;j n;j+)Cij=0;for(int k=0;k n;k+)Cij+=Aik*Bkj;分治算法举例3：Strassen矩阵乘法两个nn的方矩Ann,Bnn相乘的传统方法：时间复杂性：O(n3)算法分析与设计46 分治算法：分别将矩阵A，B和C分解为4个大小相等

20、的子矩阵,假设n=2r。C=AB可以写为：可以得出：算法分析与设计47降低时间复杂性的思路：减少乘法的次数。算法分析与设计48Strassen矩阵乘法算法实现void strassen(int aN,int bN,int cN,int topX,int topY,int n)if(n=2)直接相乘结果存放在c 中；返回；分块（a11,a12,a21,a22,b11,b12,b21,b22）计算m1,m2,m3,m4,m5,m6,m7；计算c11,c12,c21,c22；将结果拷贝到c中。结论：较少乘法次数是优化算法的重要途径。算法分析与设计49分治算法举例4：棋盘覆盖 在一个2k2k 个方格组

21、成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。算法分析与设计50残缺棋盘算法分析与设计51算法分析与设计52u放置一个三格板后，棋盘中间区域已经放置好。如果把这个三格板看成三个残缺格，原来的残缺棋盘就可以分成4个残缺棋盘。虽然这个三个棋盘与原来棋盘不相似，但是通过放置一个三格板，可以将原来不相似的三个棋盘构造成残缺棋盘，这样这三个棋盘的放置方法可以采用类似原来残缺棋盘的放置方法。v 当残缺棋盘的规模降为2*2时，这时棋盘不再分解

22、，递归终 止，因为这时残缺棋盘只要放置一个三格板就可以铺满。算法分析与设计53当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘,即k=0,11。算法分析与设计54棋盘覆盖分治算法伪语言if(size=0)return;/覆盖左上角子棋盘if(特殊方块在左上角)覆盖左上角;else 在右下角放一小方块;覆盖左上角;/覆盖右上

23、角子棋盘if(特殊方块在右上角)覆盖右上角;else 在左下角放一小方块;覆盖右上角;/覆盖左下角子棋盘if(特殊方块在左下角)覆盖左下角;else 在右上角放一小方块;覆盖左下角;/覆盖右下角子棋盘if(特殊方块在右下角)覆盖右下角;else 在左上角放一小方块;覆盖右下角;void chessBoard(int tr,int tc,int dr,int dc,int size)算法分析与设计55void chessBoard(int tr,int tc,int dr,int dc,int size)if(size=1)return;int t=tile+,/L型骨牌号s=size/2;/分

24、割棋盘/覆盖左上角子棋盘if(dr tr+s&dc tc+s)/特殊方格在此棋盘中chessBoard(tr,tc,dr,dc,s);else/此棋盘中无特殊方格/用t 号L型骨牌覆盖右下角boardtr+s-1tc+s-1=t;/覆盖其余方格chessBoard(tr,tc,tr+s-1,tc+s-1,s);/覆盖右上角子棋盘if(dr=tc+s)/特殊方格在此棋盘中chessBoard(tr,tc+s,dr,dc,s);else/此棋盘中无特殊方格/用t 号L型骨牌覆盖左下角boardtr+s-1tc+s=t;/覆盖其余方格chessBoard(tr,tc+s,tr+s-1,tc+s,s)

25、;/覆盖左下角子棋盘if(dr=tr+s&dc=tr+s&dc=tc+s)/特殊方格在此棋盘中chessBoard(tr+s,tc+s,dr,dc,s);else/用t 号L型骨牌覆盖左上角boardtr+stc+s=t;/覆盖其余方格chessBoard(tr+s,tc+s,tr+s,tc+s,s);算法分析与设计56算法分析与设计57void chessBoard(int boardNN,int tr,int tc,int dr,int dc,int size,int&tile)if(size=1)return;int s=size/2;int t=tile+;/左上角if(dr tr+s

26、&dc tc+s)chessBoard(board,tr,tc,dr,dc,s,tile);else boardtr+s-1tc+s-1=t;chessBoard(board,tr,tc,tr+s-1,tc+s-1,s,tile);/右上角if(dr=tc+s)chessBoard(board,tr,tc+s,dr,dc,s,tile);else boardtr+s-1tc+s=t;chessBoard(board,tr,tc+s,tr+s-1,tc+s,s,tile);/左下角if(dr=tr+s&dc=tr+s&dc=tc+s)chessBoard(board,tr+s,tc+s,dr,d

27、c,s,tile);else boardtr+stc+s=t;chessBoard(board,tr+s,tc+s,tr+s,tc+s,s,tile);算法分析与设计58算法分析与设计59分治算法举例5：归并排序void mergeSort(T a,int left,int right)if(含有2个以上元素)计算中点位置；归并排序前半部分；/分解归并排序后半部分；/分解将两个有序段合并到b；/合并结果将b中的结果复制回a；基本思想:将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，然后将两个排好序的子集合 归并成一个有序的集合。算法分析与设计60template void

28、mergeSort(T a,int left,int right)if(left right)mid=(left+right)/2;/计算中点mergeSort(a,left,mid);/归并排序前后两部分mergeSort(a,mid+1,right);merge(a,b,left,mid,right);/将两个有序段合并到bcopy(a,b,left,right);/将结果复制到数组a算法分析与设计61算法分析与设计62算法分析与设计63（2）成对处理输入值，用其中较小者与当前最小值比较，用较大值与当前最大值比较，每对数据比较3次，共比较 次。分治算法举例6：线性时间选择在有n个元素的集合

29、中找最小值或最大值需比较n-1次。如果利用锦标赛树，其他元素需要比较 次。（1）分别找出最大值和最小值，比较次数为2（n-1）同时找到最大值和最小值方法：算法分析与设计64T randomizedSelect(T a,int p,int r,int k)如果只有一个元素，将其返回；int i=随机将线性序列分解为两部分(前小后大）；j=计算前段元素个数;if(第k个小的元素位于前段)采用同样的方法在前段找第k 个小元素；else采用同样的方法在后段找k-j 个小元素;p irja问题：给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素。算法分析与设计65Templat

30、e T randomizedSelect(T 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);p irja算法分析与设计66 一种选择支点元素的方法是使用“中间的中间（median-of-median）”首先将数组a中的n 个元素分成n/r 组，r 为某一整常数，除了最后一组外，每组都有r个元素。然后通过在每组中对r 个元素进

31、行排序来寻找每组中位于中间位置的元素。最后对所得到的n/r 个中间元素，递归使用选择算法，求得”中间之中间”作为支点元素。规则：算法分析与设计67如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至多为原数组长度的倍(01是某个正常数)，就可以在最坏情况下用O(n)时间完成选择任务。在最坏情况下，算法randomizedSelect需要O(n2)计算时间。可以证明，算法randomizedSelect可以在O(n)时间内找出n个输入元素中的第k小元素。例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)

32、满足递归式T(n)T(9n/10)+O(n)。由此可得T(n)=O(n)。算法分析与设计68v P=8,17,4,11,3,13,6,19,16,5,7,23,22v Q=25v R=31,60,33,51,57,49,35,43,37,52,32,54,41,46,29按递增顺序，找出下面29个元素的第18个元素：8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,16,5,41,7,23,22,46,29.举例(1)把前面25个元素分为5(=floor(29/5)组：(8,31,60,33,17),(4,51,57,49,3

33、5),(11,43,37,3,13),(52,6,19,25,32),(54,16,5,41,7).(2)提取每一组的中值元素，构成集合31,49,13,25,16；(3)递归地使用算法求取该集合的中值，得到m=25；(4)根据m=25,把29个元素划分为3个子数组：算法分析与设计69(7)求取这3组元素的中值元素分别为：51,43,41，这个集合的中值元素是43;例子（续）(5)由于|P|=13,|Q|=1,k=18，所以放弃P,Q，使 k=18-13-1=4，对R递归地执行本算法；(6)将R划分成3(floor(15/5)组：31,60,33,51,57,49,35,43,37,52,32

34、,54,41,46,29(8)根据43将R划分成3组：31,33,35,37,32,41,29,43,60,51,57,49,52,54,46算法分析与设计70(12)因为k=4,而第一、第二个子数组的元素个数为3，所以33即为所求取的第18个小元素。例子（续）(9)因为k=4，第一个子数组的元素个数大于k，所以放弃后面两个子数组，以k=4对第一个子数组递归调用本算法；(10)将这个子数组分成5个元素的一组：31,33,35,37,32，取其中值元素为33；(11)根据33，把第一个子数组划分成31,32,29,33,35,37,41;算法分析与设计71 找出这 个元素的中位数。如果 是偶数，

35、就找它的2个中 位数中较大的一个。以这个元素作为划分基准。将n个输入元素划分成 个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共 个。设所有元素不相同。在这种情况下，基准x至少比3 个元素大，因为在每一组中有2个元素小于本组的中位数，而 个中位数中又有 个小于基准x。同理，基准x也至少比3 个元素小。当n75时，3(n-5)/10n/4。所以按此基准划分所得的2个子数组的长度都至少缩短1/4。算法分析与设计72T select(T a,int p,int r,int k)if(少于或等于5个数值)直接排序;return ap+k-

36、1;分组排序，并将中位数交换到前面;int x=确定中位数的中位数;int i=partition(p,r,x),j=计算前半区个数;if(k=j)return select(a,p,i,k);else return select(a,i+1,r,k-j);if(r-p5)bubbleSort(p,r);return ap+k-1;for(int i=0;i(r-p+1)/5;i+)int s=p+5*i,int t=s+4;bubbleSort(s,t);swap(a,p+i,s+2);int x=select(a,p,p+(r-p+1)/5-1,(r-p)/10);int i=partit

37、ion(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);算法分析与设计73T(n/5)：在n/5个组中找中位数的中位数。T(3n/4)：划分的子序列最多为3n/4。结论：在这里，将75作为递归界限条件，5作为分组大小，可以保证：n/5+3n/4=19n/20=n，01,这是关键。算法分析与设计74 给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。解决方法：将每个点与其余n-1个点的距离计算出来，最小距离者即为最接近点对。时间复杂性O(n2)。(1

38、)一维情形:S中的n个点退化为x轴上的n个实数x1,x2,xn。最接近点对为其中相差最小的2个实数。分治算法举例7：最接近点对问题算法分析与设计75优化最接近点对问题算法问题：无法应用于二维点对。解决方法：对所有点进行排序，需要O(n n)。再扫描一遍即可以得出最接近点对。证明得知，该问题的时间下界为(n n)算法分析与设计76优化最接近点对问题算法v假设用x轴上某个点m将S划分为2个子集S1和S2，基于平 衡子问题的思想，用S中各点坐标的中位数来作分割点。v递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并 设d=min|p1-p2|,|q1-q2|，S中的最接近点对或者是 p1

39、,p2，或是q1,q2，或是某个p3,q3，其中p3S1且 q3S2。v思考：能否在线性时间内找到p3,q3？算法分析与设计77v如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者 与m的距离不超过d，即p3(m-d,m，q3(m,m+d。v由于在S1中，每个长度为d的半闭区间至多包含一个点（否则 必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m中至多包含S中的一个点。由图可以看出，如果(m-d,m中 有S中的点，则此点就是S1中最大点。v因此，用线性时间就能找到区间(m-d,m和(m,m+d中所有点，即p3和q3。从而用线性时间就可以将S1的解和S2的解合

40、并成 为S的解。算法分析与设计78一维点集S的最接近点对的算法double cpair1(S)/排序,(n n)n=|S|;if(n2)return;m=S中各点坐标的中位数；/线性时间构造S1和S2;/线性时间d1=cpair1(S1);/计算左侧的最接近距离d2=cpair1(S2);/计算右侧的最接近距离p=max(S1);/左侧最大值,线性时间q=min(S2);/右侧最小值,线性时间d=min(d1,d2,q-p);/最接近距离,常量时间return d;算法分析与设计79(2)二维情形v选取一垂直线l，x=m来作为分割 直线。其中m为S中各点x坐标的中 位数。由此将S分割为S1和S

41、2。v递归地在S1和S2上找出其最小距 离d1和d2，并设d=mind1,d2，S 中的最接近点对或者是d，或者是 某个p,q，其中pP1且qP2。v能否在线性时间内找到p,q？算法分析与设计80考虑P1中任意一点p，若与P2中的点q构成最接近点对的候选者，必有distance(p，q)d。满足这个条件的P2中的点一定落在一个d2d的矩形R中，由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点，因此在分治算法的合并步骤中最多只需要检查6n/2=3n个候选者。证明:将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)(2d/3

42、)的矩形。若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个(d/2)(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则distance(u,v)d。这与d的意义矛盾。算法分析与设计81为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多

43、只要检查P2中排好序的相继6个点算法分析与设计82double cpair2(S)n=|S|;if(n 2)return;1.m=S中各点x间坐标的中位数;/构造S1和S2；S1=pS|x(p)m2.d1=cpair2(S1);d2=cpair2(S2);3.dm=min(d1,d2);4.设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；P2是S2中距分割线l的距离在dm之内所有点组成的集合；将P1和P2中点依其y坐标值排序；并设X和Y是相应的已排好序的点列；5.通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；设dl是按这种扫描方式找到的点对间的最小距离；6.d=min(dm,dl);算法分析与设计83练习一：邮局选址问题 问题描述：在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。要求：为建邮 局选址，使得n个居民点到邮局之距离的总和最小 提示：带权中位数（分治算法）