算法分析与设计作业

最接近点对问题

问题

此问题分为一维，二维，三维的情况

1. 一维: 给定直线上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，这个问题比较简单，是引出二维解法的一个引子，因为一维的直线上的点，相邻点的距离肯定小于相隔的点的距离，只需要考虑相邻点即可。

2. 二维：给定平面上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，这是我们这一问题的重点

3. 三维：给定空间上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间

的距离最小，此问题是二维的解法的复杂化，具体可以在飞机航线等问题上运用，但在此不多做介绍。

基本思想

由于该问题的基本解法是去考察每个点和其他所有点的距离。因此它的时间复杂度是

O(n2),这样做的效率太低，我们就要去寻找一个更高效的办法：分治法。

1. 因二维的情况太过复杂，先考虑一维的情况中，可以用分治法对其进行分部计算： 把直线分成两部分, s1s2,分别求出其最接近点的距离d1 d2。但分割开的地方的两点距离可能小于这两个值，这三个值进行比较之后，得到最后结果。 2. 鉴于此，二维的也可以用此方法进行计算：

把待计算的点s分成两部分s1 s2，分别求出其最接近点的距离d1 d2。但d1d2最小的未必是s中的最小距离d，它有可能是s1中的一个点和s2中的一个点组成的最接近点对。所以还要考虑s1中的所有点到s2中的每一个点的距离，一一比较之后得出一个最小值，再和d1d2比较，这就得出了最后结果。 3. 接下来是具体算法实现的步骤：

1. 把待计算的点s分成两部分s1 s2:

重要的如何去划分，这里采用在二维平面上的中线（用横坐标的最小值加上最大值的平均数）来划分。

2. 分别求出其最接近点的距离d1 d2:

这可以用一个递归来完成。

3. 计算s1中的所有点到s2中的每一个点的距离：

这个问题是此问题的关键。

页 1

首先要考虑的是，s1中的点，是不是每一个都有可能和s2中的某个点组成最接近点呢。答案是未必。假设中线的横坐标是x.而d1 d2中较小的值为d。则s1中距离中线大于d的点，它和s2中任意点的距离必定大于d。所以，只用考虑符合（X-x1

然后要考虑的是，对于每个中距离中线小于d的点，是不是s2中的每个点都有可能和其组成最接近点呢？答案也是未必。假设一个s1中距离中线小于d的点为n1，它的纵坐标为y，那么s2中距离n1小于于d的点，它的纵坐标和y之差的绝对值必然小于d。即一定在下图阴影部分之中。

在下图中，我们观察到：将阴影部分分成6块，每块顶多有一个点。否则，任意一块中的两个点，他们的距离一定小于等于(d)?(d)，即小于d，这和d的定义矛盾。

至此，我们得到结论，不是每个s2中的点都需要计算的。我们只需要计算s1中距离中线x不超过d的点和与此点对应的符合阴影部分的s2中的点。

122232

4. 在第三步中的所有距离中得到一个最小距离d3，和d1 d2相比之后，得出最终

答案。

4. 现在要考虑的是这个算法和基本算法的O(n)的时间复杂度相比，它有优越性么?

假设问题的规模为n，在这个算法中，它的分割步骤和合并步骤总共耗时O(n)。因此，

2页 2

算法耗费的计算时间为T(n)满足递归方程T(n)??解此方程得T(n)=O(nlogn)。

O(1)n?4

?2T(n/2)?O(n)n?4?源代码

因课本上的关键代码是用C++编写的。本人不善于用C++，故进行修改并用C实现。

#include #include #define MAX 50

int point1,point2,x[MAX]; float point[MAX][2];

float distance(int a,int b) {//两点间距离 float dx,dy; dx=point[a][0]-point[b][0]; dy=point[a][1]-point[b][1]; return (sqrt(dx*dx+dy*dy)); }

void record(int a,int b)

{//用point1,point2来记录最接近点的编号。 if(point1==-1){point1=a;point2=b;} else if(distance(a,b)

float closest(int m,int n) {//分治法求最接近距离 float d,d1,d2,mid; int i,j,k; if((n-m)==1) { d=distance(x[m],x[n]); record(x[m],x[n]); return d; } if((n-m)==2) { d=distance(x[m],x[m+1]); d1=distance(x[m],x[n]); d2=distance(x[m+1],x[n]); if(d<=d1&&d<=d2) {record(x[m],x[m+1]); return d;} if(d1<=d&&d1<=d2) {record(x[m],x[n]); return d1;} if(d2<=d&&d2<=d1) {record(x[m+1],x[n]); return d2;} }

//多于点的情况用分治法 k=(m+n)/2; d1=closest(m,k); d2=closest(k+1,n); if(d1

页 3

if(point[x[i]][0]=k+1;j--) { if(point[x[j]][0]>mid+d)continue; //右边部分离中线距离大于d的被排除 if(abs(point[x[j]][1]-point[x[i]][1])>d)continue; //右边部分纵坐标离左边所选点纵坐标的距离大于d的被排除 d1=distance(x[i],x[j]); if(d1

void arrange(int n) { //对x[]进行赋值，赋值为以点的横坐标从小到大排列的点的序号 float x1[MAX],tem1; int tem; int i,j; for(i=0;ix1[j+1]) { tem1=x1[j];x1[j]=x1[j+1];x1[j+1]=tem1; tem=x[j];x[j]=x[j+1];x[j+1]=tem; } } } }

int main(void) { float x1[MAX],tem1; int i,j,n,tem; float a,b,d; point1=-1; //录入点的数据*****

printf(\请输入点的个数（为大于等于的自然数）：\); scanf(\,&n); for(i=0;i

//****************** arrange(n); d=closest(0,n-1); printf(\最接近点对为第%d个点和第%d个点\,point1+1,point2+1); printf(\其距离为%.5f\\n\,d); system(\); return 0; }

页 4

测试数据及运行结果

为验证程序的正确性，特寻找几组独特的数据进行检测

测试数据 N 1 2 5 4 1 ,1 1 ,1 1,1 0,0 2,2 1,2 0,8 1000,1000 4,4 1050,50 4,-4 50,1050 结果 无结果 1,2 1,2 1,4 1.41421 1.0000 5.65685 观察以上测试，基本符合题意要求。但此程序仅得到一个最接近点对，若出现相等的情况，

只给出其中一个。

调试心得和源程序

源程序在源代码部分已经给出。

在调试过程中，我发现对于数组地址的传递比较容易出错，鉴于时间问题，只好采取设置全局变量的办法解决了问题。

另：本程序几乎被我重新编写，和书中的代码有巨大的差异，但算法思想是一致的。

页 5

本文来源：https://www.bwwdw.com/article/rfe2.html