求最近點(diǎn)對(duì)算法

《算法設(shè)計(jì)與分析》上機(jī)報(bào)告姓名： 學(xué)號(hào)： 日期:上機(jī)題目： 求最近點(diǎn)對(duì)算法實(shí)驗(yàn)環(huán)境：CPU:2.10GHz;內(nèi)存:6G;操作系統(tǒng)：Win764位；軟件平臺(tái)：VisualStudio2008;一、算法設(shè)計(jì)與分析:題目：給定平面上n個(gè)點(diǎn)，找其中的一對(duì)點(diǎn)，使得在n個(gè)點(diǎn)的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)的距離最?。换靖拍睿篠中的點(diǎn)為平面上的點(diǎn)有2個(gè)坐標(biāo)值x和y。為了將平面上點(diǎn)集S線性分割為大小大致相等的2個(gè)子集S1和S2,我們選取一垂直線l:x=m來(lái)作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1={p￡S|pxWm}和S2={p￡S|px>m}。從而使S1和S2分別位于直線l的左側(cè)和右側(cè)，且S=S1US2。由于m是S中各點(diǎn)x坐標(biāo)值的中位數(shù)，因此S1和S2中的點(diǎn)數(shù)大致相等。遞歸地在S1和S2上解最接近點(diǎn)對(duì)問題，我們分別得到S1和S2中的最小距離61和62?，F(xiàn)設(shè)6=min(61,61)。若S的最接近點(diǎn)對(duì)(p,q)之間的距離d(p,q)<6則p和q必分屬于S1和S2。不妨設(shè)p￡S1,q￡S2。那么p和q距直線l的距離均小于6。因此，我們?nèi)粲肞1和P2分別表示直線l的左邊和右邊的寬為6的2個(gè)垂直長(zhǎng)條，則p￡P(guān)1,q￡P(guān)2。思路：對(duì)所有點(diǎn)先按x不減排序，二分x,得到點(diǎn)集S1,點(diǎn)集S2,通過(guò)遞歸求得S1,S2的最小點(diǎn)對(duì)距離d1,d2；D=min{d1,d2}；合并S1,S2：找到在S1,S2劃分線左右距離為D的所有點(diǎn)，按y不減(不增也可以)排序循環(huán)每個(gè)點(diǎn)找它后面7個(gè)點(diǎn)的最小距離；最后即求得最小點(diǎn)對(duì)距離。若要求得點(diǎn)對(duì)坐標(biāo)，在求值是保存點(diǎn)的坐標(biāo)即可。二、核心代碼：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卡回酒每/需大學(xué) 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

卡回縛每芯譚大學(xué)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)三、結(jié)果與分析:1、對(duì)closest（X,Y,0,n-1,a,b,d）;的時(shí)間復(fù)雜的的分析（假設(shè)時(shí)間復(fù)雜度為T（n））：2、將Y數(shù)組拷貝到SL,SR需要時(shí)間（n）（24-28行）3、遞歸調(diào)用closest時(shí)間復(fù)雜度為2T（n/2）（29行和30行）4、將中間區(qū)域存到數(shù)組Z中需要時(shí)間n（37-39行）5、將中間區(qū)域存放的數(shù)組的每一點(diǎn)與其后面7點(diǎn)的距離進(jìn)行比較，需要時(shí)間7n（40-45行）

卡回酒號(hào)/譚大學(xué)綜上：[ 1 n<=2T(n)=\ 由主方法可知其時(shí)間復(fù)雜度為0(nlogn)〔2T(n/2)+9n n>2對(duì)closest_pair的時(shí)間復(fù)雜的的分析：1、從X拷貝到Y(jié)需要時(shí)間0(n)(8-12行)2、在算法closest_pair中，對(duì)X,Y數(shù)組進(jìn)行排序都需要時(shí)間0(nlogn)(6、13行)3、closest(X,Y,0,n-1,a,b,d);的時(shí)間復(fù)雜度0(nlogn)綜上總的時(shí)間復(fù)雜度為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);#回酒沒/需大學(xué)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的點(diǎn)存在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