最近点对问题.doc
- 文档编号:1311105
- 上传时间:2023-04-30
- 格式:DOC
- 页数:8
- 大小:84KB
最近点对问题.doc
《最近点对问题.doc》由会员分享,可在线阅读,更多相关《最近点对问题.doc(8页珍藏版)》请在冰点文库上搜索。
最近对问题
算法分析与设计
最近对问题
问题描述:
在二维平面上的n个点中,如何快速的找出最近的一对点,就是最近点对问题。
程序设计思想:
1.蛮力法求最近对问题:
基本思想:
分别计算每一对点之间的距离,然后找出距离最小的那一对,为了避免对同一对点计算两次距离,只考虑的那些点对。
复杂度分析:
对于此算法,主要就是算两个点的欧几里得距离。
注意到在求欧几里得距离时,避免了求平方根操作,其原因是:
如果被开方的数越小,则它的平方根也越小。
所以复杂度就是求平方,求执行次数为:
;即时间复杂度为。
2.分治法求最近对问题:
基本思想:
用分治法解决最近点对问题,就是将一个问题分解两个子问题,然后递归处理子问题,然后合并。
可能两个点在每个子问题中,也可能两个点分别在两个子问题中,就这两种情况。
则基本过程为:
找一条中垂线(坐位集合坐标的中位数)把个元素分成左右两部分元素,然后分别求得两边的最短距离,,然后取两者中的最小者记为,在中线两边分别取的距离,记录该距离范围内点的个数,中线左边有个元素,右边有个元素,分别将两边的点按y坐标升序排列,在左边集合中每一个点,找右边集合的点,找到与之距离小于的点,更新最短距离,直到循环结束,即可求出最短距离。
复杂度分析:
应用分治法求解含有个点的最近对问题,其时间复杂性可由递推式表示:
。
由以上分析:
合并子问题的解的时间。
进而可得分治法求最近对问题的时间复杂度为:
。
程序代码:
#include
#include
#include
#defineNUM1000
typedefstruct{
intx;
inty;
}N;
doubledistance(Nn1,Nn2);
doubleminDis(doubled1,doubled2);
doubleshortestDis(N*data,intlength,N*n1,N*n2);
doubleshortestDis(N*data,intlength,N*n1,N*n2){
intpre,last,middle,median;
inti,c1num=0,c2num=0,j;
N*dataP;
N*dataL;
N*CP;
N*CL;
Ntn1,tn2;
doubledis1,dis2;
//当只有两个点时,返回最短距离,和点
if(length==2){
doubledis1=distance(data[0],data[1]);
*n1=data[0];
*n2=data[1];
returndis1;
}elseif(length==3){
//当只有三个点时,返回最短距离,和点
doubledis1=distance(data[0],data[1]);
doubledis2=distance(data[1],data[2]);
doubledis3=distance(data[0],data[2]);
doubletemp;
temp=dis1 dis1: dis2; temp=temp temp: dis3; if(temp==dis1){ *n1=data[0];*n2=data[1]; }elseif(temp==dis2){ *n1=data[1];*n2=data[2]; }else{ *n1=data[0];*n2=data[2]; } returntemp; } 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 dataP[i]=data[i]; for(i=0;i dataL[i]=data[i+pre]; dis1=shortestDis(dataP,pre,n1,n2); dis2=shortestDis(dataL,last,&tn1,&tn2); if(dis1>dis2){ *n1=tn1; *n2=tn2; } dis1=minDis(dis1,dis2); for(i=0;i if(dataP[i].x-median CP[c1num++]=dataP[i]; }//将在中位数之前的区域中与中位数距离小于最短距离的点放到CP中 for(i=0;i if(median-dataL[i].x CL[c2num++]=dataL[i]; }//将在中位数之后的区域中与中位数距离小于最短距离的点放到CL中 for(i=0;i for(j=0;j doubletemp=distance(CP[i],CL[j]); if(temp dis1=temp; *n1=CP[i]; *n2=CL[j]; } } }//依次计算中位数两旁的区域中,每一个点与另外一个区域中的距离,并且记录最短距离 returndis1; } doubledistance(Nn1,Nn2){ returnsqrt((n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y)); } doubleminDis(doubled1,doubled2){ doubled=d1 d1: d2; returnd; } //分治法排序 voidMergeSort(Nq[],intnum,intmode){ inti,nump,numl; N*qPre; N*qLast; if(num==1) return; if(num%2&&num! =2){ numl=num/2; nump=num/2; nump++; }else{ numl=num/2; nump=num/2; } qPre=(N*)malloc(sizeof(N)*nump); qLast=(N*)malloc(sizeof(N)*numl); for(i=0;i qPre[i]=q[i]; for(i=0;i qLast[i]=q[nump+i]; MergeSort(qPre,nump,mode); MergeSort(qLast,numl,mode); Merge(qPre,qLast,q,nump,numl,mode); } voidMerge(N*pre,N*last,N*total,intnump,intnuml,intmode){ inti=0,j=0,k=0; while(i if(mode==0){ if(pre[i].x>last[j].x){ total[k++]=pre[i++]; }else{ total[k++]=last[j++]; } }else{ if(pre[i].y>last[j].y){ total[k++]=pre[i++]; }else{ total[k++]=last[j++]; } } } if(i==nump){ for(i=j;i total[k++]=last[i]; }else{ for(j=i;j total[k++]=pre[j]; } } voidcomputeShortestDistance(N*data,intnum,intresult[4]){ FILE*fo; inti,j,l=0; int*datax,*datay; doubledis=666666,temp; datax=(int*)malloc(sizeof(int)*1000); datay=(int*)malloc(sizeof(int)*1000); for(i=0;i datax[i]=data[i].x; datay[i]=data[i].y; } for(i=0;i for(j=i+1;j if((temp=(datax[i]-datax[j])*(datax[i]-datax[j])+(datay[i]-datay[j])*(datay[i]-datay[j])) dis=temp; result[0]=datax[i]; result[1]=datay[i]; result[2]=datax[j]; result[3]=datay[j]; } } printf("\n蛮力法: \n"); printf("shortestdis: %f",sqrt(dis)); } voidgenerateDots(intnumber){ FILE*fo; inti,n1,n2; if(! (fo=fopen("data.txt","w"))){ printf("openfilefail"); exit (1); } for(i=0;i srand((i*i)); n1=rand()%8000; srand(time(NULL)*i*i); n2=rand()%6000; if(i%2) fprintf(fo,"%d%d\n",n1,n2); else fprintf(fo,"%d%d\n",n2,n1); } fclose(fo); } intmain() {FILE*fo; N*data; inti; Nn1,n2; doubledis; intre[4]; //生成数据 generateDots(NUM); data=(N*)malloc(sizeof(N)*1000); if(! (fo=fopen("data.txt","r"))){ printf("openfilefail"); exit (1); } for(i=0;i fscanf(fo,"%d%d",&data[i].x,&data[i].y); } fclose(fo); //合并排序,排好序的数据放置到data中。 MergeSort(data,NUM,0); //分治法 dis=shortestDis(data,NUM,&n1,&n2); printf("分治法: \n"); printf("%f\nX: %d\tY: %d\nX: %d\tY: %d\t",dis,n1.x,n1.y,n2.x,n2.y); //蛮力法 computeShortestDistance(data,NUM,re); printf("\nx: %d\ty: %d\nx: %d\ty: %d",re[0],re[1],re[2],re[3]); } 实验环境: Codeblocks 编译器: MinGW(MinimalistGNUforWindows) 实验结果: 心得体会: 1.在课堂上听了老师讲解算法之后,自己在亲自动手实现算法之后,对算法有了更深的理解。 2.在算法的实现过程中遇到了一些小问题,但是都通过自己google解决了。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最近 问题