求最近点对算法

《算法设计与分析》上机报告姓名：学号：日期：上机题目：求最近点对算法实验环境：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|px≤m}和S2={p∈S|pxm}。从而使S1和S2分别位于直线l的左侧和右侧，且S=S1∪S2。由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等。递归地在S1和S2上解最接近点对问题，我们分别得到S1和S2中的最小距离δ1和δ2。现设δ=min(δ1,δ1)。若S的最接近点对(p,q)之间的距离d(p,q)δ则p和q必分属于S1和S2。不妨设p∈S1，q∈S2。那么p和q距直线l的距离均小于δ。因此，我们若用P1和P2分别表示直线l的左边和右边的宽为δ的2个垂直长条，则p∈P1，q∈P2。思路：对所有点先按x不减排序，二分x，得到点集S1，点集S2，通过递归求得S1，S2的最小点对距离d1，d2；D=min{d1,d2}；合并S1，S2：找到在S1，S2划分线左右距离为D的所有点，按y不减(不增也可以)排序循环每个点找它后面7个点的最小距离；最后即求得最小点对距离。若要求得点对坐标，在求值是保存点的坐标即可。二、核心代码：1voidclosest_pair(POINTX[],intn,POINT&a,POINT&b,float&d)2{3if(n2)4d=0;5else{6merge_sort(X,n,true);//sortXaccordingtox-coordinate7A_POINT*Y=newA_POINT[n];8for(inti=0;in;i++){//copytheelementsofXintoY9Y[i].index=i;10Y[i].x=X[i].x;11Y[i].y=X[i].y;12}13merge_sort(Y,n,false);//sortYaccordingtoy-coordinate14closest(X,Y,0,n-1,a,b,d);//findtheclosest-pairamongX15d=sqrt(d);16deleteY;17}18}1voidclosest(POINTX[],A_POINTY[],intlow,inthigh,POINT&a,POINT&b,float&d)2{3inti,j,k,m;4POINTal,bl,ar,br;5floatdl,dr;6if((high-low)==1)//n=2,calculatedirectly7(a=X[low],b=X[high],d=dist(X[low],X[high]));8elseif((high-low)==2){//n=3,calculatedirectly9dl=dist(X[low],X[low+1]);10dr=dist(X[low],X[low+2]);11d=dist(X[low+1],X[low+2]);12if((dl=dr)&&(dl=d))13(a=X[low],b=X[low+1],d=dl);14elseif(dr=d)15(a=X[low],b=X[low+2],d=dr);16else17(a=X[low+1],b=X[low+2]);18}19else{//n3DivedeandConquer20A_POINT*SL=newA_POINT[(high-low)/2+1];21A_POINT*SR=newA_POINT[(high-low)/2];//divideXintotwosubarraybym22m=(high+low)/2;23j=k=0;24for(i=0;ihigh-low+1;i++)25if(Y[i].index=m)//collecttheelementsofauxiliaryarrayofleftsubarrayofX26SL[j++]=Y[i];27else//collecttheelementsofauxiliaryarrayofleftsubarrayofX28SR[k++]=Y[i];//calculatetheclosest-pairofleftsubarrayofX29closest(X,SL,low,m,al,bl,dl);//calculatetheclosest-pairofrightsubarrayofX30closest(X,SR,m+1,high,ar,br,dr);31if(dldr)//combination32(a=al,b=bl,d=dl);33else34(a=ar,b=br,d=dr);35POINT*Z=newPOINT[high-low+1];36k=0;//collectthepointswithinthetwostripsofwidthdofLfromY37for(i=0;ihigh-low+1;i++)38if((fabs(X[m].x-Y[i].x)d)39(Z[k].x=Y[i].x,Z[k++].y=Y[i].y);40for(i=0;ik;i++){41for(j=i+1;(jk)&&(Z[j].y-Z[i].yd);j++){42dl=dist(Z[i],Z[j]);43if(dld)44(a=Z[i],b=Z[j],d=dl);45}46}47}48deleteSL;deleteSR;deleteZ;49}三、结果与分析：1、对closest(X,Y,0,n-1,a,b,d);的时间复杂的的分析(假设时间复杂度为T(n))：2、将Y数组拷贝到SL，SR需要时间)(n(24-28行)3、递归调用closest时间复杂度为)2/(2nT(29行和30行)4、将中间区域存到数组Z中需要时间n(37-39行)5、将中间区域存放的数组的每一点与其后面7点的距离进行比较，需要时间7n(40-45行)综上：229)2/(21)(nnnnTnT由主方法可知其时间复杂度为)log(nn对closest_pair的时间复杂的的分析：1、从X拷贝到Y需要时间)(n(8-12行)2、在算法closest_pair中，对X,Y数组进行排序都需要时间)log(nn(6、13行)3、closest(X,Y,0,n-1,a,b,d);的时间复杂度)log(nn综上总的时间复杂度为)log(nn附录（源代码）算法源代码（C++描述）#includeiostream#includestring#includecmathusingnamespacestd;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)));}templateclassDataTypevoidInsertSort(DataTypea[],intn,boolbSortX)//bSortXsitruethensorta[].xelsesorta[].y{inti,j;DataTypetemp;if(bSortX){for(j=1;jn;j++){temp=a[j];i=j-1;while(temp.xa[i].x&&i=0){a[i+1]=a[i];i--;}a[i+1]=temp;}}else{for(j=1;jn;j++){temp=a[j];i=j-1;while(temp.ya[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;ihigh-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(dldr)(a=al,b=bl,d=dl);else(a=ar,b=br,d=dr);POINT*Z=newPOINT[high-low+1];k=0;for(i=0;ihigh-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;ik;i++){for(j=i+1;(jk)&&(Z[j].y-Z[i].yd);j++){dl=dist(Z[i],Z[j]);if(dld)(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(n2)d=0;else{InsertSort(X,n,true);A_POINT*Y=newA_POINT[n];for(inti=0;in;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;in;i++)for(intj=0;j!=i&&jn;j++){if(ddist(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}};POINTx2,y2;floatd2=0;cout输入点为：e