最近点对问题的.docVIP

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