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

《数据结构与算法课程设计报告--最近点对问题的解决算法.docx》由会员分享，可在线阅读，更多相关《数据结构与算法课程设计报告--最近点对问题的解决算法.docx（9页珍藏版）》请在第一文库网上搜索。

1、课程设计报告课程名称：数据结构与算法项目名称：正文部分D简介题目原文：最近点对问题在一片金属板上钻多个大小一样的洞，如果洞太近（洞中心距离Dcm）,金属可能会断。现假设在金属板上，钻了n个洞，请编程判断该金属板是否会断。该问题的抽象模型:在一个二维平面中有有限的点，求其中距离最近的两点的距离。2）实现（算法，流程，数据结构，复杂度分析等的描述）算法：采用分治法。首先划分集合S为S1和SR,使得S1中的每一个点位于SR中每一个点的左边，并且S1和SR中点数相同。分别在S1和SR中解决最近点对问题，得到D1和DR,分别表示S1和SR中的最近点对的距离。令d=min（D1zDR）o如果S中的最近点对

2、（P1P2）。P1P2两点一个在S1和一个在SR中，那么P1和P2一定在以1为中心的间隙内，以1-d和1+d为界，如下图所示：I11I1Sr如果在S1中的点P和在SR中的点Q成为最近点对，那么P和Q的距离必定小于do因此对间隙中的每一个点，在合并步骤中，只需要检验yp+d和yp-d内的点即可。流程：步骤1：根据点的y值和X值对S中的点排序。步骤2:找出中线1将S划分为S1和SR步骤3:将步骤2递归的应用解决S1和SR的最近点对问题，并令d=min(d1zdR)o步骤4:将1-d1+d内的点以y值排序，对于每一个点(X1y1)找出y值在y1-dy1+d内的所有点,计算距离为d,o如果Cr小于d,

3、令d=d,最后的d值就是答案。数据结构：顺序存储。算法复杂度分析：ST1:sort使用了时间复杂度为O(n1gn)的排序算法，对于一个数据规模为n的最近点对问题，定义它的复杂度为T(n)o算法的第一步将问题分解成两个子问题，分解这部分的复杂读是2T(n)o第2步线性扫描，上界为O(n)o第3步对于P中的每一个点，其比较的时间复杂度是常数。由于需要扫描所有P点，上界为O(n)o原问题时间复杂度T(n)=2T(n)+O(n)使用算法导论的主定理可以得出总的上界为O(n1gn)易知空间复杂度为0(n)3）结果展示（效果，功能，以及其他相关图片，数据等）可自行设置安全距离，设置打孔数量请输入打孔数量?

4、O至少需要两个点.1至少需要两个点.2实际运行效果，附穷举法验证:请设定安全距离.4.567请输入打孔数量？1017.3555.08安全0.3312.98615.03317.000.80：5安全.55安全.7.98.8安全.77危险，最近两点的距离为2.01246,少于4.567使用有举法验证最小距离为2.012464）问题分析（碰到什么问题，如何解决）在类中定义的比较方法需要定义为静态，所以将数据存储容器作为全局变量定义。5）程序代码清单（代码应含有恰当的注释语句）/*源代码*/inc1ude#inc1ude#inc1udeinc1udeusingnamespacestd;c1assPoin

5、tdoub1ex,y;点对象的结构pub1ic:Point(doub1ex,doub1ey)(this-x=x;this-y=y;)doub1edist_to(Pointp)(returnsqrt(x-p.x)*(x-p.x)+(y-p.y)*(y-p.y);)friendc1assP1ane;)；vectorcontainer;点集的容器，使用ST1VeCtor存储c1assP1ane(pub1ic:平面类的声明voidadd(Pointp)(container.push_back(p);)staticboo1cmpXY(constPoint&a,constPoint&b)(if(a.x!=

6、b.x)returna.xb.x;returna.yb.y;/若横坐标不同则比较横坐标，否则比较纵坐标staticboo1cmpY(inta,intb)以纵坐标为主的比较函数(returncontainera.ycontainerb.y;)doub1edist(inti,intj)/求第i与第j个点的距离(已排序)returncontaineri.distjo(containerj);doub1emin(doub1ex,doub1ey)取最小值方法(returnxy?x:y;)voidSOrt()/使用ST1a1gorithm提供的sort方法对所有点进行XY排序(std:sort(conta

7、iner.begin(),container.end(),cmpXY);)doub1egetC1osest(intIeftJntright)/主要方法，递归调用(int*tmp=newint10000;/用以存放与左右两边边界距离为d的所有点doub1ed=9999999;if(eft=right)returnd;if(1eft+1=right)returndist(1eft,right);intmid=(1eft+right)2;doub1ed1eft=getC1osest(1eft,mid);/取左区域最小距离doub1edright=getC1osest(mid+1,right);取右区

8、域最小总巨离d=min(d1eft,dright);从两者中取最小值intk=0;for(inti=1eft;i=right;i+)(if(fabs(containermid.x-containeri.x)=d)tmpk+=i;/取边界两侧距边界小于d的点std:sort(tmp,tmp+k,cmpY);for(inti=0;ik;i+)(for(intj=i+1;jk&containertmpj.y-containertmpi.yt)d=t;在边界点中按y轴方向的距离比较；)de1etetmp;returnd;)doub1ebrute_getC1osest()穷举法，用以验证结果的准确性in

9、t1en=container.size();doub1ed=99999;for(inti=0;iIen;i+)for(intj=i+1;jIen;j+)(if(dist(i5j)d)d=dist(i,j);)returnd;)-P1ane()(container.car();)；intmain()(doub1esafe_dist;coutP1easeinputthesafedistancebetweeneachtwopoints.n;cinsafe_dist;intn;coutn;whi1e(n=1)(coutn;)P1anepn;for(intixy;Pointp(x,y);pn.add(p

10、);pn.sort();doub1edist=pn.getC1osSt(0,i);if(dist=1)(coutWarning,theminimumdistanceofpointsisdist,1essthansafe_distend1;Cout,Verifyingwithbrutea1gorithm,pn.brute-getC1osest（）end1;break;）e1secoutThenewho1eissafe.n;）*代码结束*/6）心得与体会体会：第一点：通过这个作业，我们充分认识和了解了用分治法解决实际问题的优点：分-将问题分解为规模更小的子问题；治-将这些规模更小的子问题逐个击破；

11、合-将已解决的子问题合并，最终得出母问题的解；第二点：两个人分工合作也体现了程序设计中的面向对象，模块化设计的思想。7）任务分工及所完成的状况分工：李逸飞负责：步骤1（根据点的y值和X值对S中的点排序。）步骤2（找出中线1将S划分为S1和SR）步骤3（将步骤2递归的应用解决S1和SR的最近点对问题，并令d=min（d1,dR）（共同完成）梁志煌负责：步骤3（将步骤2递归的应用解决S1和SR的最近点对问题，并令d=min（d1,dR）（共同完成）步骤4（将1-d1+d内的点以y值排序，对于每一个点（X1y1）找出y值在y1-d-y1+d内的所有点，计算距离为d,o如果Cr小于d,令d=d,最后的d值就是答案。）8）参考文献1“最近点对问题“，NoA1Go,http:/noa1go.info/793.htm19）诚信承诺（注此项不可分开为两页！）个人得分权重分配表排序姓名学号项目个人权重150%250%我组成员总共2名，权重总和为：100%本组成员郑重承诺在课程设计完成过程中不发生任何不诚信现象，一切不诚信所导致的后果均由本组成员承担。同时我组成员同意此课程设计的个人得分权重分配表。签名（手签全部成员）：