求最近点对算法

《算法设计与分析》上机报告姓名： 学号： 日期:上机题目： 求最近点对算法实验环境：CPU:2.10GHz;内存:6G;操作系统：Win764位；软件平台：VisualStudio2008;一、算法设计与分析:题目：给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小；基本概念：S中的点为平面上的点有2个坐标值x和y。为了将平面上点集S线性分割为大小大致相等的2个子集S1和S2,我们选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1={p£S|pxWm}和S2={p£S|px>m}。从而使S1和S2分别位于直线l的左侧和右侧，且S=S1US2。由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等。递归地在S1和S2上解最接近点对问题，我们分别得到S1和S2中的最小距离61和62。现设6=min(61,61)。若S的最接近点对(p,q)之间的距离d(p,q)<6则p和q必分属于S1和S2。不妨设p£S1,q£S2。那么p和q距直线l的距离均小于6。因此，我们若用P1和P2分别表示直线l的左边和右边的宽为6的2个垂直长条，则p£P1,q£P2。思路：对所有点先按x不减排序，二分x,得到点集S1,点集S2,通过递归求得S1,S2的最小点对距离d1,d2；D=min{d1,d2}；合并S1,S2：找到在S1,S2划分线左右距离为D的所有点，按y不减(不增也可以)排序循环每个点找它后面7个点的最小距离；最后即求得最小点对距离。若要求得点对坐标，在求值是保存点的坐标即可。二、核心代码：voidclosest_pair(POINTX[],intn,POINT&a,POINT&b,float&d)(if(n<2)d=0;else{merge_sort(X,n,true);//sortXaccordingtox-coordinateA_POINT*Y=newA_POINT[n];for(inti=0;i<n;i++){//copytheelementsofXintoYY[i].index=i;Y[i].x=X[i].x;

111213141516171812345678910111213141516171819202122232425262728卡回酒每/需大学 Y[i].y=X[i].y;)merge_sort(Y,n,false);//sortYaccordingtoy-coordinateclosest(X,Y,0,n-1,a,b,d);//findtheclosest-pairamongXd=sqrt(d);deleteY;))voidclosest(POINTX[],A_POINTY[],intlow,inthigh,POINT&a,POINT&b,float&d)(inti,j,k,m;POINTal,bl,ar,br;floatdl,dr;if((high-low)==1) //n=2,calculatedirectly(a=X[low],b=X[high],d=dist(X[low],X[high]));elseif((high-low)==2){ //n=3,calculatedirectlydl=dist(X[low],X[low+1]);dr=dist(X[low],X[low+2]);d=dist(X[low+1],X[low+2]);if((dl<=dr)&&(dl<=d))(a=X[low],b=X[low+1],d=dl);elseif(dr<=d)(a=X[low],b=X[low+2],d=dr);else(a=X[low+1],b=X[low+2]);)else{ //n>3DivedeandConquerA_POINT*SL=newA_POINT[(high-low)/2+1];A_POINT*SR=newA_POINT[(high-low)/2];//divideXintotwosubarraybymm=(high+low)/2;j=k=0;for(i=0;i<high-low+1;i++)if(Y[i].index<=m)//collecttheelementsofauxiliaryarrayofleftsubarrayofXSL[j++]=Y[i];else//collecttheelementsofauxiliaryarrayofleftsubarrayofXSR[k++]=Y[i];//calculatetheclosest-pairofleftsubarrayofX

卡回缚每芯谭大学29 closest(X,SL,low,m,al,bl,dl);//calculatetheclosest-pairofrightsubarrayofX30 closest(X,SR,m+1,high,ar,br,dr);31 if(dl<dr)//combination32 (a=al,b=bl,d=dl);33 else34 (a=ar,b=br,d=dr);35 POINT*Z=newPOINT[high-low+1];36 k=0;//collectthepointswithinthetwostripsofwidthdofLfromY37 for(i=0;i<high-low+1;i++)38 if((fabs(X[m].x-Y[i].x)<d)39 (Z[k].x=Y[i].x, Z[k++].y=Y[i].y);40 for(i=0;i<k;i++){41424142434445464748if(dl<d)(a=Z[i],b=Z[j],d=dl);)))deleteSL;deleteSR;deleteZ;49)三、结果与分析:1、对closest（X,Y,0,n-1,a,b,d）;的时间复杂的的分析（假设时间复杂度为T（n））：2、将Y数组拷贝到SL,SR需要时间（n）（24-28行）3、递归调用closest时间复杂度为2T（n/2）（29行和30行）4、将中间区域存到数组Z中需要时间n（37-39行）5、将中间区域存放的数组的每一点与其后面7点的距离进行比较，需要时间7n（40-45行）

卡回酒号/谭大学综上：[ 1 n<=2T(n)=\ 由主方法可知其时间复杂度为0(nlogn)〔2T(n/2)+9n n>2对closest_pair的时间复杂的的分析：1、从X拷贝到Y需要时间0(n)(8-12行)2、在算法closest_pair中，对X,Y数组进行排序都需要时间0(nlogn)(6、13行)3、closest(X,Y,0,n-1,a,b,d);的时间复杂度0(nlogn)综上总的时间复杂度为0(nlogn)附录(源代码)算法源代码(C++描述)#include<iostream>#include<string>#include<cmath>usingnamespacestd;typedefstruct(floatx;floaty;}POINT;typedefstruct(floatx;floaty;intindex;}A_POINT;floatdist(POINTA,POINTB)(return(sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)));}template<classDataType>voidInsertSort(DataTypea[],intn,boolbSortX)//bSortXsitruethensorta[].xelsesorta[].y(inti,j;DataTypetemp;if(bSortX)for(j=1;j<n;j++)(temp=a[j];i=j-1;while(temp.x<a[i].x&&i>=0)(a[i+1]=a[i];i--;)a[i+1]=temp;)}else(for(j=1;j<n;j++)(temp=a[j];i=j-1;while(temp.y<a[i].y&&i>=0)(a[i+1]=a[i];i--;)a[i+1]=temp;))voidclosest(POINTX[],A_POINT*constY,intlow,inthigh,POINT&a,POINT&b,float&d)(inti,j,k,m;POINTal,bl,ar,br;floatdl=0,dr=0;if((high-low)==1)(a=X[low],b=X[high],d=dist(X[low],X[high]));elseif((high-low)==2)(dl=dist(X[low],X[low+1]);dr=dist(X[low],X[low+2]);d=dist(X[low+1],X[low+2]);if((dl<=dr)&&(dl<=d))(a=X[low],b=X[low+1],d=dl);elseif(dr<=d)(a=X[low],b=X[low+2],d=dr);#回酒没/需大学else(a=X[low+1],b=X[low+2]);)else(A_POINT*constSL=newA_POINT[(high-low)/2+1];A_POINT*constSR=newA_POINT[(high-low)/2];m=(high+low)/2;j=k=0;for(i=0;i<high-low+1;i++)if(Y[i].index<=m)SL[j++]=Y[i];elseSR[k++]=Y[i];closest(X,SL,low,m,al,bl,dl);closest(X,SR,m+1,high,ar,br,dr);if(dl<dr)(a=al,b=bl,d=dl);else(a=ar,b=br,d=dr);POINT*Z=newPOINT[high-low+1];k=0;for(i=0;i<high-low+1;i++) 〃将x=m两边距离x=m小于d的点存在Z口中if(fabs(X[m].x-Y[i].x)<d)(Z[k].x=Y[i].x,Z[k++].y=Y[i].y);for(i=0;i<k;i++){for(j=i+1;(j<k)&&(Z[j].y-Z[i].y<d);j++){dl=dist(Z[i],Z[j]);if(dl<d)(a=Z[i],b=Z[j],d=dl);))delete[]SL;delete[]SR;delete[]Z;))voidclosest_pair(POINTX[],intn,POINT&a,POINT&b,float&d){if(n<2)d=0;else{

InsertSort(X,n,true);A_POINT*Y=newA_POINT[n];for(inti=0;i<n;i++)(Y[i].index=i;Y[i].x=X[i].x;Y[i].y=X[i].y;)InsertSort(Y,n,false);closest(X,Y,0,n-1,a,b,d);//d=sqrt(d);deleteY;))voidclosest_test(POINTX[],intn,POINT&a,POINT&b,float&d)(d=dist(X[0],X[1]);for(inti=0;i<n;i++)for(intj=0;j!=i&&j<n;j++)(if(d>dist(X[i],X[j]))(a=X[i];b=X[j];d=dist(X[i],X[j]);)))intmain()(POINTpt[10]={{10,2},{1,3},{2,8},{9,0},{4,5},{3,2},{5,7},{7,1},{6,6},{8,4}};POINTx,y;floatd=0;POINTpt2[10]={{10,2},{1,3},{2,8},{9,0},{4,5},{3,2},{5,7},{7,1},{6,6},{8,4}};POIN