数据结构与算法课程设计报告--最近点对问题的解决算法.docx

课程设计报告课程名称：数据结构与算法项目名称：最近点对问题的解决算法正文部分1）简介题目原文：最近点对问题在一片金属板上钻多个大小一样的洞，如果洞太近（洞中心距离Dcm）,金属可能会断。现假设在金属板上，钻了n个洞，请编程判断该金属板是否会断。该问题的抽象模型:在一个二维平面中有有限的点，求其中距离最近的两点的距离。2）实现（算法，流程，数据结构，复杂度分析等的描述）算法：采用分治法。首先划分集合S为SL和SR,使得SL中的每一个点位于SR中每一个点的左边，并且SL和SR中点数相同。分别在SL和SR中解决最近点对问题，得到DL和DR,分别表示SL和SR中的最近点对的距离。令d=min（DL,DR）o如果S中的最近点对（PLP2）。PLP2两点一个在SL和一个在SR中，那么Pl和P2一定在以L为中心的间隙内，以L-d和L+d为界，如下图所示：LSl SR 如果在SL中的点P和在SR中的点Q成为最近点对，那么P和Q的距离必定小于do因此对间隙中的每一个点，在合并步骤中,只需要检验yp÷d和yp-d内的点即可。流程：步骤1：根据点的y值和X值对S中的点排序。步骤2:找出中线L将S划分为SL和SR步骤3:将步骤2递归的应用解决SL和SR的最近点对问题，并令d=min(dL,dR)o步骤4:将L-d-L+d内的点以y值排序,对于每一个点(XLyI)找出y值在yl-d-yl÷d内的所有点，计算距离为d'o如果Cr小于d,令d=d,最后的d值就是答案。数据结构：顺序存储。算法复杂度分析：STLisort使用了时间复杂度为O(Mgn)的排序算法,对于一个数据规模为n的最近点对问题，定义它的复杂度为T(n)o算法的第一步将问题分解成两个子问题，分解这部分的复杂读是2T(n)第2步线性扫描,上界为0(n)。第3步对于P中的每一个点，其比较的时间复杂度是常数。由于需要扫描所有P点，上界为0(n)。原问题时间复杂度T(n)=2T(n)+0(n)使用算法导论的主定理可以得出总的上界为O(nlgn)易知空间复杂度为0(n)3）结果展示（效果，功能，以及其他相关图片，数据等）可自行设置安全距离，设置打孔数量请输入打孔数量?至少需要两个点.至少需要两个点.实际运行效果，附穷举法验证:请设定安全距离.4.567请输入打孔数量？1017.3555.08安全.0.3312.98615.03317.000.80：5安全.55安全.7.98.8安全.77危险，最近两点的距离为2.01246,少于4.567使用穷举法验证最小距离为2.012464）问题分析（碰到什么问题，如何解决）在类中定义的比较方法需要定义为静态，所以将数据存储容器作为全局变量定义。5）程序代码清单（代码应含有恰当的注释语句）/*源代码*/#include<iostream>#include<math.h>#include<vector>#include<algorithm>usingnamespacestd;classPointdoublex,y;点对象的结构public:Point(doublex,doubley)(this->x=x;this->y=y;)doubledistjo(Pointp)returnsqrt(×-p.x)*(x-p.x)+(y-p.y)*(y-p.y);)friendclassPlane:；vector<Point>container:点集的容器，使用STLVeCtor存储classPlanePub附平面类的声明voidadd(Pointp)(container.psh-back(p);)staticboolcmpXY(constPoint&a,constPointsb)(if(a.xI=b.x)returna.×<b.x;returna.y<b.y;若横坐标不同则比较横坐标，否则比较纵坐标staticboolcmpY(inta,intb)以纵坐标为主的比较函数returncontainera.y<ntainerb.y;)doubledist(inti,intj)Zi与第j个点的距离(已排序)returncontaineri.distJo(containerO);doublemin(doublex,doubley)取最小值方法returnx<y?x:y;)voidsort()使用STLalgorithm提供的sort方法对所有点进行XY排序std:sort(container.begin(),container.end(),cmpXY);)doublegetClosest(intleft,intright)主要方法，递归调用int*tmp=newint10000;用以存放与左右两边边界距离为d的所有点doubled=9999999;if(left=right)returnd;if(left+1=right)returndist(left,right);intmid=(left+right)2;doubledleft=getClosest(left,mid);取左区域最小距离doubledright=getClosest(mid+i,right);取右区域最小距离d=min(dleft,dright);从两者中取最小值intk=0;for(inti=left;i<=right;i+)if(fabs(containermid.x-container(i.x)<=d)tmpk+=i;取边界两侧距边界小于d的点std:sort(tmp,tmp+k,cmpY);for(inti=0;i<k;i+)for(intj=i+1;j<k&&containertmpj.y-containertmpi.y<d;j+)doublet=dist(tmpi,tmpj);if(d>t)d=t;W在边界点中按y轴方向的距离比较；)deletetmp;returnd;)doublebrute_getClosest()穷举法，用以验证结果的准确性intlen=container.size();doubled=99999;for(inti=0;i<Ien;i+)for(intj=i+1;j<Ien;j+)if(dist(i,j)<d)d=dist(i,j);)returnd;)-Plane()(container.clear();)；intmain()(doublesafe_dist:cout<<',Pleaseinputthesafedistancebetweeneachtwopoints.n"cin»safe_dist;intn;cout<<',Howmanyholedoyouwanttodrillontheplate?n"cin>>n;while(n<=1)cout<<',Thereshouldbeatleast2points.n"cin>>n;)Planepn:for(inti=0;i<n;i+)doublex,y;cin>>x>>y;Pointp(x,y);pn.add(p);pnsort();doubledist=p.getClosest(0,i);if(dist<safe_dist&&i>=1)cout<<"Warning,theminimumdistanceofpointsis',<<dist<<",lessthan"«safe_dist«endl;Cout<<,Verifyingwithbrutealgorithm,<<pn.brute-getClosest（）<<endl;break;）elsecout<<,Thenewholeissafe.n"）*代码结束*/6）心得与体会体会：第一点：通过这个作业，我们充分认识和了解了用分治法解决实际问题的优点：分一将问题分解为规模更小的子问题；治一将这些规模更小的子问题逐个击破；合一将已解决的子问题合并,最终得出"母问题的解；第二点：两个人分工合作也体现了程序设计中的面向对象，模块化设计的思想。7）任务分工及所完成的状况分工：李逸飞负责：步骤1（根据点的y值和X值对S中的点排序。）步骤2（找出中线L将S划分为SL和SR）步骤3（将步骤2递归的应用解决SL和SR的最近点对问题，并令d=min（dLzdR）供同完成）梁志煌负责：步骤3（将步骤2递归的应用解决SL和SR的最近点对问题，并令d=min（dLzdR）（共同完成）步骤4（将L-d-L+d内的点以y值排序,对于每一个点（XLyI）找出y值在yl-d-yl÷d内的所有点，计算距离为d'o如果Cr小于d,令d=d',最后的d值就是答案。）8）参考文献1”最近点对问题"，NoAlGo,http:/noalgo.info/793.html9）诚信承诺（注此项不可分开为两页！）个人得分权重分配表排序姓名学号项目个人权重150%250%我组成员总共2名，权重总和为：100%本组成员郑重承诺在课程设计完成过程中不发生任何不诚信现象，一切不诚信所导致的后果均由本组成员承担。同时我组成员同意此课程设计的个人得分权重分配表。签名（手签全部成员）：