最近点对问题供参习.doc

最近对问题
算法分析与设计
最近对问题
问题描述:
在二维平面上的n个点中,如何快速的找出最近的一对点,就是最近点对问题。
程序设计思想:
:
基本思想:
分别计算每一对点之间的距离,然后找出距离最小的那一对,为了避免对同一对点计算两次距离,只考虑的那些点对。
复杂度分析:
对于此算法,主要就是算两个点的欧几里得距离。注意到在求欧几里得距离时,避免了求平方根操作,其原因是:如果被开方的数越小,则它的平方根也越小。所以复杂度就是求平方,求执行次数为:
;即时间复杂度为。
:
基本思想:
用分治法解决最近点对问题,就是将一个问题分解两个子问题,然后递归处理子问题,然后合并。可能两个点在每个子问题中,也可能两个点分别在两个子问题中,就这两种情况。则基本过程为:找一条中垂线(坐位集合坐标的中位数)把个元素分成左右两部分元素,然后分别求得两边的最短距离,,然后取两者中的最小者记为,在中线两边分别取的距离,记录该距离范围内点的个数,中线左边有个元素,右边有个元素,分别将两边的点按y坐标升序排列,在左边集合中每一个点,找右边集合的点,找到与之距离小于的点,更新最短距离,直到循环结束,即可求出最短距离。
复杂度分析:
应用分治法求解含有个点的最近对问题,其时间复杂性可由递推式表示:。
由以上分析:合并子问题的解的时间。进而可得分治法求最近对问题的时间复杂度为:。
程序代码:
#include <>
#include <>
#include <>
#define NUM 1000
typedef struct{
int x;
int y;
}N;
double distance(N n1,N n2);
double minDis(double d1,double d2);
double shortestDis(N *data,int length,N *n1 , N *n2);
double shortestDis(N *data,int length,N *n1 , N *n2){
int pre,last,middle,median;
int i,c1num = 0,c2num = 0,j;
N* dataP;
N* dataL;
N* CP;
N* CL;
N tn1,tn2;
double dis1 ,dis2;
// 当只有两个点时,返回最短距离,和点
if(length == 2 ){
double dis1 = distance(data[0],data[1]);
*n1 = data[0];
*n2 = data[1];
return dis1;
}else if(length == 3){
// 当只有三个点时,返回最短距离,和点
double dis1 = distance(data[0],data[1]);
double dis2 = distance(data[1],data[2]);
double dis3 = distance(data[0],data[2]);
double temp;
te