最接近点对问题实验报告

最接近点对问题

一．实验目的：

1.理解算法设计的基本步骤及各步的主要内容、基本要求；

2.加深对分治设计方法基本思想的理解，并利用其解决现实生活中的问题； 3.通过本次实验初步掌握将算法转化为计算机上机程序的方法。

二．实验内容：

1.编写实现算法：给定n对点，在这n对点中找到距离最短的点对。

2.将输出数据存放到另一个文本文件中，包括结果和具体的运行时间。 3.对实验结果进行分析。 三．实验操作：

1.最接近点对查找的思想：

首先，将所有的点对按照x坐标排序，找到x坐标的中位数，将所有的点对分成

三部分，横坐标小于x（S1）、等于x（S2）和大于x（S3）的点对，在求取每部分中的最短距离，利用分治法，一步步地分解为子问题，找到最短距离d。由于距离最近的两个点可能在不同的区域中，需要进一步判断。

选择S1中的一个点，由于与它相比较的点的距离不可能超过d，故其配对范围

为d*2d的矩形，将这个矩形划分为6份2/d*3/d的小矩形，其对角线的长度为5/6d，小于d,故S1中的任意一个点只需和S2中的6个点比较即可，最终确定最短的距离。 2.取中位数：

为了减少算法的时间开销，需要将所有的点对进行分组，以中位数为基准，考虑到快速排序的不稳定性，本次排序使用了合并排序。 代码实现：

template

void Merge(Type c[],Type d[],int l,int m,int r){

int i = l,j = m + 1,k = l; while((i<=m)&&(j<=r)){

if(c[i]<=c[j]) d[k++] = c[i++]; else d[k++] = c[j++]; }

if(i>m) {

for(int q=j; q<=r; q++) d[k++] = c[q]; } else{

for(int q=i; q<=m; q++) d[k++] = c[q]; }

}

template

void MergeSort(Type a[],Type b[],int left,int right){

if(left

int i = (left + right)/2; MergeSort(a,b,left,i);

1 / 4

MergeSort(a,b,i+1,right);

Merge(a,b,left,i,right);//合并到数组a Copy(a,b,left,right);//复制回数组a }

}

3.数据存入文件:

本次对文件的输入没有存入文本文件中，只将输出数据输入到指定的文件夹中，用

到了输出流文件。 代码实现：

ofstream outFile;

outFile.open(\程序设计/practice 1/算法设计与分析/文本文件夹/最接近点对问题结果.txt\

int length;

cout<<\请输入点对数：\ cin>>length; xPosition X[M];

cout<<\随机生成的二维点对为：\ outFile<<\随机生成的二维点对为：\\n\ for(int i=0;i

cout<<\ outFile<<\ }

xPosition a; xPosition b; float d; start=clock();

Cpair2(X,length,a,b,d); finish=clock(); cout<

cout<<\最邻近点对为：(\和

(\

outFile<<\最邻近点对为：(\和

(\

cout<<\最邻近距离为： \ outFile<<\最邻近距离为： \

cout<<\程序运行时间：\ outFile<<\程序运行时间：\ outFile.close(); 4.求解最短距离：

将总的点对分为三部分，对每一部分求解最短的距离，对只有两对、三对的情况直

接进行距离求解。当对每一部分求解最短距离时，采用分治法分解为一个个小的子问题，

2 / 4

对点在两个区域的情况，依照思想，进行排序比较，和已有的最短距离比较，最终确定最短距离的点对。 代码实现：

void closest(xPosition X[],yPosition Y[],yPosition Z[],int left,int right,xPosition& a,xPosition& b,float& d){

if(right-left==1) //两点的情形 {

a=X[left]; b=X[right];

d=dis(X[left],X[right]); return; }

if(right-left==2) //3点的情形 {

float d1=dis(X[left],X[left+1]); float d2=dis(X[left+1],X[right]); float d3=dis(X[left],X[right]); if(d1<=d2 && d1<=d3){ a=X[left]; b=X[left+1]; d=d1; return; }

if(d2<=d3){ a=X[left+1]; b=X[right]; d=d2; } else{

a=X[left]; b=X[right]; d=d3; }

return; }

//多于3点的情形，用分治法 int m=(left+right)/2; int f=left,g=m+1;

for(int i=left;i<=right;i++){ if(Y[i].p>m) Z[g++]=Y[i]; else Z[f++]=Y[i]; }

closest(X,Z,Y,left,m,a,b,d); float dr;

3 / 4

xPosition ar,br;

closest(X,Z,Y,m+1,right,ar,br,dr); {

a=ar; b=br; d=dr; }

Merge(Z,Y,left,m,right);//重构数组Y int k=left;

for(int i=left;i<=right;i++){ if(fabs(X[m].x-Y[i].x)

//搜索Z[l:k-1]

for(int i=left;i

for(int j=i+1;j

a=X[Z[i].p]; b=X[Z[j].p]; } } }

}

四．实验数据分析：

本实验对不同规模的数据进行测试，实验数据如下。

运行时间/ms最短距离求解时间图表86420050, 0150, 1300, 24006008001000700, 4900, 6200测试数目/对1 五．实验感受：

在实验中，随机生成一定数量的点对，对这些点对进行最短距离求解，由于设置

的范围过小，在进行时间测量时，得到的数据都为零，故在进行实际分析时，需要使用大规模的数据。

4 / 4