分而治之算法---距离最近的点对.doc

《分而治之算法---距离最近的点对.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、距离最近的点对给定n个点（xi，yi）（1≤i≤n），要求找出其中距离最近的两个点。例14-7假设在一片金属上钻n个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。通过检查所有的n(n-1)/2对点，并计算每一对点的距离，可以找出距离最近的一对点。这种方法所需要的时间为(n2)。我们称这种方法为直接方法。图14-13中给出了分而治之求解算法的伪代码。该算法对于小的问题采用直接方法求解，而对于大的问题则首先把它划分为两个较小的问题，其中一个问题（称为A）的大小为「n

2、/2ù，另一个问题（称为B）的大小为「n/2ù。初始时，最近的点对可能属于如下三种情形之一：1)两点都在A中（即最近的点对落在A中）；2)两点都在B中；3)一点在A，一点在B。假定根据这三种情况来确定最近点对，则最近点对是所有三种情况中距离最小的一对点。在第一种情况下可对A进行递归求解，而在第二种情况下可对B进行递归求解。if(n较小){用直接法寻找最近点对Return;}//n较大将点集分成大致相等的两个部分A和B确定A和B中的最近点对确定一点在A中、另一点在B中的最近点对从上面得到的三对点中，找出距离最小的一对点图14-13寻找最近的点对为了确定第

3、三种情况下的最近点对，需要采用一种不同的方法。这种方法取决于点集是如何被划分成A、B的。一个合理的划分方法是从xi（中间值）处划一条垂线，线左边的点属于A，线右边的点属于B。位于垂线上的点可在A和B之间分配，以便满足A、B的大小。例2-8考察图14-14a中从a到n的14个点。这些点标绘在图14-14b中。中点xi=1，垂线x=1如图14-14b中的虚线所示。虚线左边的点(如b,c,h,n,i)属于A，右边的点(如a,e,f,j,k,l)属于B。d,g,m落在垂线上，可将其中两个加入A,另一个加入B，以便A、B中包含相同的点数。假设d,m加入A，g加入

4、B。设是i的最近点对和B的最近点对中距离较小的一对点。若第三种情况下的最近点对比小。则每一个点距垂线的距离必小于，这样，就可以淘汰那些距垂线距离≥的点。图14-15中的虚线是分割线。阴影部分以分割线为中线，宽为2。边界线及其以外的点均被淘汰掉，只有阴影中的点被保留下来，以便确定是否存在第三类点对（对应于第三种情况）其距离小于。用RA、RB分别表示A和B中剩下的点。如果存在点对(p,q)，p?A,q?B且p,q的距离小于，则p?RA，q?RB。可以通过每次检查RA中一个点来寻找这样的点对。假设考察RA中的p点，p的y坐标为p.y，那么只需检查RB中满足p

5、.y-＜q.y＜p.y+的q点，看是否存在与p间距小于的点。在图14-16a中给出了包含这种q点的RB的范围。因此，只需将RB中位于×2阴影内的点逐个与p配对，以判断p是否是距离小于的第三类点。这个×2区域被称为是p的比较区（comparingregion）。例2-9考察例2-8中的14个点。A中的最近点对为(b,h)，其距离约为0.316。B中最近点对为(f,j)，其距离为0.3，因此=0.3。当考察是否存在第三类点时，除d,g,i,l,m以外的点均被淘汰，因为它们距分割线x=1的距离≥。RA={d,i,m}，RB={g,l}，由于d和m的比较区中没

6、有点，只需考察i即可。i的比较区中仅含点l。计算i和l的距离，发现它小于，因此(i,l)是最近的点对。为了确定一个距离更小的第三类点，RA中的每个点最多只需和RB中的6个点比较，如图14-16所示。1.选择数据结构为了实现图14-13的分而治之算法，需要确定什么是“小问题”以及如何表示点。由于集合中少于两点时不存在最近点对，因此必须保证分解过程不会产生少于两点的点集。如果将少于四点的点集做为“小问题”，就可以避免产生少于两点的点集。每个点可有三个参数：标号，x坐标，y坐标。假设标号为整数，每个点可用Pointl类（见程序14-8）来表示。为了便于按x坐

7、标对各个点排序，可重载操作符＜=。归并排序程序如14-3所示。程序14-8点类classPoint1{friendfloatdist(constPoint1&,constPoint1&);friendvoidclose(Point1*,Point2*,Point2*,int,int,Point1&,Point1&,float&);friendboolclosest(Point1*,int,Point1&,Point1&,float&);friendvoidmain();public:intoperator<=(Point1a)const{return(

8、x<=a.x);}private:intID;//点的编号floatx,y;//点坐标};cl