中科大算法实验4,求平面最近点对算法.docVIP

《算法设计与分析》上机报告 姓名： 张先荣 学号： S日期： 2016/11/22 上机题目： 4th：求最近点对算法 CPU; I3 ; 内存: 8G ;操作系统 Windows7 ;软件平台： Visual studio 2013 ; 一、算法设计与分析： 题目一: 给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。 我们考虑将所给的平面上n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，?然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足:　T(n)=2T(n/2)+O(n2) 在一维的情形，距分割点距离为δ的2个区间(m-δ,m](m,m+δ]中最多各有S中一个点。因而这2点成为唯一的末检查过的最接近点对候选者。二维的情形则要复杂些，此时，P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。在最坏情况下有n2/4对这样的候选者。但是P1和P2中的点具有以下的稀疏性质，它使我们不必检查所有这n2/4对候选者。考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者，则必有d(p,q)δ。满足这个条件的P2中的点有多少个呢？容易看出这样的点一定落在一个δ×2δ的矩形R中. 因此d(u,v)≤5δ/6δ 。这与δ的意义相矛盾。也就是说矩形R中最多只有6个S中的点。图4(b)是矩形R中含有S中的6个点的极端情形。由于这种稀疏性质，对于P1中任一点p，P2中最多只有6个点与它构成最接近点对的候选者。因此，在分治法的合并步骤中，我们最多只需要检查6×n/2=3n对候选者，而不是n2/4对候选者。这是否就意味着我们可以在O(n)时间内完成分治法的合并步骤呢？现在还不能作出这个结论，因为我们只知道对于P1中每个S1中的点p最多只需要检查P2中的6个点(确切的说，是矩形R中的6个S中的点)，但是我们并不确切地知道要如何检查。为了解决这个问题，我们可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，并且要满足d(p,q)δ q∈P2,因此满足条件的点它们在直线l上的投影点距p在l上投影点的距离小于δ，由上面的分析可知，这种投影点不多于6个。因此，若将P1和P2中所有S的点按其y坐标排好序，则对P1中所有点p，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，对P1中每一点最多只要检查P2中排好序的相继6个点。 至此，我们可以给出用分治法求二维最接近点对的算法CPAIR2如下: function CPAIR2(S); begin if |S|=2 then δ:=S中这2点的距离 else if |S|=0 then δ:=∞ else begin 1. m:=S中各点x坐标值的中位数; 构造S1和S2，使S1={p∈S|px≤m}和S2={p∈S|pxm} 2. δ1:=CPAIR2(S1);δ2:=CPAIR2(S2); 3. δm:=min(δ1,δ2); 4. 设P1是S1中距垂直分割线l的距离在δm之内的所有点组成的集合， P2是S2中距分割线l的距离在δm之内所有点组成的集合。将P1和P2中的点依其y坐标值从小到大排序，并设P1*和P2*是相应的已排好序的点列; 5. 通过扫描P1*以及对于P1*中每个点检查P2*中与其距离在δm之内的所有点(最多6个)可以完成合并。当P1*中的扫描指针逐次向上移动 时，P2*中的扫描指针可在宽为2δm的一个区间内移动。设δl是按 这种扫描方式找到的点对间的最小距离; 6. δ=min(δm,δl); end; return(δ); end; 下面我们来分析一下算法CPAIR2的计算复杂性。设对于n个点的平面点集S，算法耗时T(n)。算法的第1步和第5步用了O(n)时间，第3步和第6步用了常数时间，第2步用了2T(n/2)时间。若在每次执行第4步时进行排序，则在最坏情况下第4步要用O(nlogn)时间。这不符合我们的要求。因此，在这里我们要作一个技术上的处理。我们采用设计算法时常用的预排序技术，即在使用分治法之前，预先将S中n个点依其y坐标值排好序，设排好序的点