难点:如何测试。我的解决方式是: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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605716.html