難點:如何測試。我的解決方式是:a,三種解法,看結果是否一致。b,小數據(100個點),人工排查。第一種方法,暴力法適合小數據。第二種方法:我的改進型。第三種方法:經典方法(分治法)。實驗證明1000萬數據時,我的演算法有優勢。暴力演算法,O(n2)。我的改進型要點:先對所有數據按Y排序。只比較y距離小 ...
難點:如何測試。我的解決方式是:a,三種解法,看結果是否一致。b,小數據(100個點),人工排查。第一種方法,暴力法適合小數據。第二種方法:我的改進型。第三種方法:經典方法(分治法)。實驗證明1000萬數據時,我的演算法有優勢。
暴力演算法,O(n2)。我的改進型要點:先對所有數據按Y排序。只比較y距離小於等於已知最小距離的點對。經典方法:按Y排序,分成兩部分,遞歸調用。合併師只比較距離分界線不超過已知最小距離的點對。
實際證明500萬數據以下,我的改進演算法明顯優於經典演算法;1000萬數據時,略強於經典演算法。
核心代碼:
double Dis(const CPT& pt1,const CPT& pt2) { return sqrt((double) (pt1.x-pt2.x)*(pt1.x-pt2.x)+(pt1.y-pt2.y)*(pt1.y-pt2.y)+(pt1.z-pt2.z)*(pt1.z-pt2.z) ); } void InitData(CPT* pts,int iNum) { srand(time(NULL)); for( int i = 0 ; i < iNum ; i++) { pts[i].x = rand()%10000; pts[i].y = rand()%10000; pts[i].z = rand()%10000; } } double Fun1(CPT* pts,const int iNum) { double dMinDis = 10000*10000 ; for(int i = 0 ; i < iNum ; i++ ) for( int j = i+1 ; j < iNum ; j++ ) { const double d = Dis(pts[i] , pts[j]); if( d < dMinDis) { dMinDis = d ; } } return dMinDis; } class CCmpY { public: bool operator()(const CPT& pt1,const CPT& pt2) { return pt1.y < pt2.y ; } }; double Fun2(CPT* pts,const int iNum) { std::sort(pts,pts+iNum,CCmpY() ); double dMinDis = 10000*10000 ; for(int i = 0 ; i < iNum ; i++ ) for( int j = i+1 ; j < iNum ; j++ ) { const double d = Dis(pts[i] , pts[j]); if( d < dMinDis) { dMinDis = d ; } if( abs(pts[i].y - pts[j].y )> dMinDis ) { break; } } return dMinDis; } double Fun3(CPT* pts,const int iNum) { std::sort(pts,pts+iNum,CCmpY() ); if( iNum < 100 ) { return Fun1(pts,iNum); } const int iMid = iNum/2 ; const double dMin1 = Fun3(pts,iMid); const double dMin2 = Fun3(pts+iMid,iNum-iMid); double dMinDis = min(dMin1,dMin2) ; for(int i = iMid-1 ; i >= 0 ; i-- )//左集合 { if( abs(pts[i].y - pts[iMid].y ) > dMinDis ) { break; } for( int j = iMid ; j < iNum ; j++ )//右集合 { const double d = Dis(pts[i] , pts[j]); if( d < dMinDis) { dMinDis = d ; } if( abs(pts[i].y - pts[j].y )> dMinDis ) { break; } } } return dMinDis; }
可通過以下鏈接下載測試數據,exe,源碼(VS2005,VC8)
https://pan.baidu.com/s/1QyQgtUvqtuH3n7TCLHxKtA