最短点对
2019-01-01 23:16:00来源:博客园 阅读 ()
难点:如何测试。我的解决方式是: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
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 如何0基础学习C/C++? 2020-06-06
- Emergency Evacuation(最短下车时间)———(思维) 2020-04-11
- 标准输入重定向到文件后,如何连续读入,如何判断标准输入流 2020-03-20
- 手把手教你如何玩转CLion 2020-02-06
- c++-引用 2019-12-20
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash