最近点对问题

1、最近点对问题I.一维问题:一、问题描述和分析最近点对问题的提法是：给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。严格的讲，最接近点对可能多于1对，为简单起见，只找其中的1对作为问题的解。简单的说，只要将每一点与其它n-1个点的距离算出，找出达到最小距离的2点即可。但这样效率太低，故想到分治法来解决这个问题。也就是说，将所给的平面上n个点的集合S分成2个子集S1和S2,每个子集中约有n/2个点。然后在每个子集中递归的求其最接近的点对。这里，关键问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对。如果组成S的最接近点对

2、的2个点都在S1中或都在S2中，则问题很容易解决，但如果这2个点分别在S1和S2中，问题就不那么简单了。下面的基本算法中，将对其作具体分析。、基本算法假设用x轴上某个点m将S划分为2个集合S1和S2,使得S1=esn;while(sn!=-1)n+;cinsn;returnn;floatmax(floats,intb,inte)返回sb到se中的最大值floatm1=sb;for(inti=b+1;i=e;i+)if(m1si)m1=si;returnm1;floatmin(floats,intb,inte)返回sb到se中的最小值floatm1=sb;for(inti=b+1;isi)m1=

3、si;returnm1;返回s中的具有最近距离的点对及其距离cpaircpair1(floats,intn)cpairtemp=1000,0,0;/当点集中元素的个数不足2时,返回具有无穷大的dist值(此处设为1000)的tempif(n2)returntemp;floatm1=max(s,0,n-1),m2=min(s,0,n-1);floatm=(ml+m2)/2;找出点集中的中位数intj=0,k=0;将点集中的各元素按与m的大小关系分组floatslM,s2M;for(inti=0;in;i+)if(si=m)slj=si;j+;elses2k=si;k+;cpaird1=cpair

4、1(s1,j),d2=cpair1(s2,k);递归floatp=max(sl,0,j-l),q=max(s2,0,k-l);返回s中的具有最近距离的点对及其距离if(d1.distd2.dist)if(q-p)d1.dist)temp.dist=(q-p);temp.d1=q;temp.d2=p;returntemp;elsereturnd1;elseif(q-p)d2.dist)temp.dist=(q-p);temp.d1=q;temp.d2=p;returntemp;elsereturnd2;voidmain()intn,m;floatsM;cpairdist;m=input(s,n)

5、;dist=cpair1(s,m);coutn该一维点集中最近点对为(dist.d1,dist.d2),其距离为dist.distendl;II.二维问题一、问题描述与分析问题描述与分析见上。下面仅对最接近点对中的2个点分别在S1和S2中的情形作具体分析。二、基本算法S中的点为平面上的点，它们都有两个坐标值x和y。为了将平面上点集S线形分割为大小大致相等的两个子集S1和S2,选取一垂直线1：x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1=e()和S2=e()。从而使S1和S2分别位于直线1的左侧和右侧，且S=SUS2。由于m是S中各点x坐标值的中位数，因此S1和S2中

6、的点数大致相等。递归的在S1和S2上届最接近点对问题，分别得到S1和S2中的最小距离di和d2。现设d=mindl,d2。若S的最接近点对(p,q)之间的距离小于d，则p和q必分属于S1和S2。不妨设pe,e。和距离直线的距离均小于。因此，若用和分别表示直线的左边和右边的宽为的两个垂直长条。则peie2如下图所示。SlddS2SlddS2图2距直线1的距离小于d的所有点在二维条件下，P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。由d的意义可知，P2中任何两个S中的点的距离都不小于d。由此可推出矩阵R中最多只有6个S中的点。由此稀疏性质，对于P1中任一点p，P2中最多只有6个点与它

7、构成最接近点对的候选者。因此，在分治法的合并步骤中，最多只需要检查6*n/2=3*n个候选者。但并不确切知道要检查哪6个点。为解决这问题，可以将p和P2中所有S2的点投影到垂直线1上。由于能与p点一起构成最接近点对候选者的S2中的点一定在d*2d的矩形中，所以它们在直线1上的投影点距p在1上投影点的距离小于d。由上述分析可知，这种投影点最多有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，贝I对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。具体算法见程序。三、实现环境本程序在VC+环境下实现。四、测试情况本

8、程序可按屏幕提示进行输入操作，即相应输出如下：请输入点集中元素的个数:1该n值不存在最近点对,请重新输入!请输入点集中元素的个数:4请依次输入二维点集中的各点:第1个点:25第2个点:14第3个点:33第4个点:58该点集中的最近点对为(1,4)和(2,5),它们的距离为1.41421五、源代码#includeiostream.h#includestdio.h#includemath.h#defineM20structpointfloatx,y;点的x,y坐标intid;/点在数组中的标号;structpairpointa,b;floatdist;/a,b两点间的距离;若xx为真时，对poin

9、t型数组xn按元素的x坐标排序；否则按其y坐标排序voidsort(pointx,intn,boolxx)for(inti=0;in;i+)for(intj=i+1;jxj.x)xi、xj互换pointt=xj;xj=xi;xi=t;修改xi、xj的id值xi.id=i;xj.id=j;else/按元素的y坐标排序if(xi.yxj.y)xi、xj互换pointt=xj;xj=xi;xi=t;修改xi、xj的id值xi.id=i;xj.id=j;输入二维点集中的各点，记录于数组x中voidinput(pointx,intn)coutvv请依次输入二维点集中的各点:n;for(inti=0;ix

10、i.xxi.y;xi.id=i;floatdis(pointa,pointb)returnsqrt(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);pairclosestpair(pointx,pointy,pointz,intl,intr)pairt;if(r=l)/1点的情形t.dist=1000;returnt;if(r-l=1)/2点的情形t.a=xl;t.b=xr;t.dist=dis(xl,xr);returnt;if(r-l=2)/3点的情形floatd1=dis(xl,xl+1),d2=dis(xl+1,xr),d3=dis(xl,xr);if(d

11、1=d2&d1=d3)t.a=xl;t.b=xl+1;t.dist=d1;returnt;if(d2=d3)t.a=xl+1;t.b=xr;t.dist=d2;returnt;elset.a=xl;t.b=xr;t.dist=d3;returnt;/多于3点的情形，用分治法intm=(l+r)/2;intf=l,g=m+1;for(inti=l;im)zg+=yi;elsezf+=yi;/递归求解pairbest=closestpair(x,z,y,l,m);pairright=closestpair(x,z,y,m+1,r);if(right.distbest.dist)best=right;将距中位线l=m的距离小于dist且宽度为2*dist的点置于z中intk=l;for(i=l;i=r;i+)if(abs(xm.x-yi.x)best.dist)zk+=yi;/搜索zl:k-1for(i=l;ik;i+)for(intj=i+1;jk&zj.y-zi.ybest.dist;j+)floatdp=dis(zi,zj);if(dpbest.dist)t.a=zi;t.b=zj;t.dist=dp;return