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

《中科大算法实验4,求平面最近点对算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档《算法设计与分析》上机报告姓名：张先荣学号：SA16225439日期：2016/11/22上机题目：4th：求最近点对算法实验环境：CPU;I3;内存:8G;操作系统Windows7;软件平台：Visualstudio2013;一、算法设计与分析：题目一:给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。我们考虑将所给的平面上n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，?然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和

2、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+δ]中最多

3、各有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、图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上。由于能

5、与p点一起构成最接近点对候选者的S2中点一定在矩形R中，并且要满足d(p,q)<δq∈P2,因此满足条件的点它们在直线l上的投影点距p在l上投影点的距离小于δ，由上面的分析可知，这种投影点不多于6个。因此，若将P1和P2中所有S的点按其y坐标排好序，则对P1中所有点p，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，对P1中每一点最多只要检查P2中排好序的相继6个点。至此，我们可以给出用分治法求二维最接近点对的算法CPAIR2如下:实用文档functionCPAIR2(S);beginif

6、S

7、=2thenδ:=S

8、中这2点的距离elseif

9、S

10、=0thenδ:=∞elsebegin1.m:=S中各点x坐标值的中位数;构造S1和S2，使S1={p∈S

11、px≤m}和S2={p∈S

12、px>m}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*中每个点检查P

13、2*中与其距离在δ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)时间。这不

14、符合我们的要求。因此，在这里我们要作一个技术上的处理。我们采用设计算法时常用的预排序技术，即在使用分治法之前，预先将S中n个点依其y坐标值排好序，设排好序的点列为P*。在执行分治法的第4步时，只要对P*作一次线性扫描，即可抽取出我们所需要的排好序的点列P1*和P2*。然后，在