算法分析与复杂性理论-实验报告-求最近点对的问题

1、深圳 大学实 验报告课程名称：算法分析与复杂性理论实验项目名称：实验二分治法求最近点对问题学院：计算机与软件学院专业：软件工程指导教师：杨烜报告人：文成学号:2150230509 班级：15级软工学术型实验时间：2015-10-22实验报告提交时间：2015-10-24教务部制实验目的与要求：实验目的：(1) 掌握分治法思想。(2) 学会最近点对问题求解方法。实验要求1. 在blackboard提交电子版实验报告，注意实验报告的书写，整体排版。2. 实验报告的实验步骤部分需详细给出算法思想与实现代码之间的关系解释，不可直接粘贴代码(直接粘贴代码者视为该部分内容缺失)。3. 实验报告样式可从表格

2、下载学生适用在校生管理-实践教学-实验：深圳大学学生实验报告)4. 源代码作为实验报告附件上传。5. 在实验课需要现场运行验证。实验内容:1. 对于平面上给定的 N个点，给出所有点对的最短距离，即，输入是平面上的N个点，输出是N点中具有最短距离的两点。2. 要求随机生成N个点的平面坐标，应用蛮力法编程计算出所有点对的最短距离。3. 要求随机生成N个点的平面坐标，应用分治法编程计算出所有点对的最短距离。4. 分别对N=100,1000,10000,100000，统计算法运行时间，比较理论效率与实测效率的差异，同时对蛮力法和分治法的算法效率进行分析和比较。5. 利用Unity3D输出分治算法中间每

3、个步骤的计算结果，并增设help按钮，详细解释算法思想。算法思想提示1. 预处理：根据输入点集S中的x轴和y轴坐标进行排序，得到X和Y,很显然此时X和Y中的点就是S中的点。2. 点数较少时的情形1 kd = g直接计Ji1V直揍计葺 »只有一个点* A只有两个点* A只有三个点3. 点数|S|>3时，将平面点集 S分割成为大小大致相等的两个子集Sl和Sr,选取一个垂直线L作为分割直线，考虑 Xl和Xr, Yl和Yr,这里还需要排序吗？实验过程及内容:（实验代码已作为附件提交，名为“算法实验二.cpp 了当点的数量小于3时，直接计算，当点的个数大于3时，采用分治法当N=1时只有一

4、个直” E:O +PROJECT、算法克验二'Debug' 算法实验二 exe"-请输入点的个数：1请输入各个点的坐标：1 1最近点对的距离为无穷大！ Press any key to continue捜狗拼音输入法全：当N=2时只有两个点，最近点对就是这两个点测试数据为（1,1）（ 2,2）预期结果为d=1.414与预期结果相同使用 蛮力法 求最近点对，核心代码如下"求距离平方的函数double Distinyui5h2(Node atNode b)return (a .x-b_x-b_x) + (a .y-b-if) *(a_yb .y);"蛮

5、力法求最近对void BruteForceCconst NLlst & L,CloseNode & cnode,int begin,int end) <For(int i=t)egin;i<=end;i*+) For(int j-i*1;j<-end;j*+)<double space = Distinyuish2(L，datai,L.dat日j)： iF<spdce<cnode«spaceb)<cnode .a-L.data1; cnode,b=L-dataj; cnode space=space;（计算两点之间的距离，分别

6、将每个点与其它点的距离求出来，找出最近点距离）当N>3时，使用分治法的情况核心代码如下:else/当23时进行分治<APOIHT *SL-nev fi_POINT(high-low)/2+1; 匸FDIHT *SR-neu nIPOINT(high-low)/2;"=(high-low)/2 ；哦组以码界划夯为厨半j=k=t);for(i=B;i<=high-lou;i*+)<if(Vi*indeK<=n)SLj + *-ViJ ；"收集左边子集中的最近点对else SRkt+=Yi ;"H煤右边子集中的最近点对> closes

7、tCX,SL,low,m,31,bl5dl);/if 算左边子集的最近点对closes t(X,Sfi,m+1,tiigh,ar.br,dr);/计算右集的巖疋点对 iF(dl<dr)i=al;b=bl;d=dl;else<a=ar;b=tjr ；d=dr;POIlfT *2=new POI NThigti-low+1 ;k=o；For(i=B;i<=t»igh-lcw;i*+)/收集距离中线?碍小于d的元素，保存SU数组科 <lf(Fabs(Xn.x-Vl.x)<d>Zk-X=V1.x;Zk-.y=Vi.j|；for(i-l;l<k;l+)

8、<far(j=i>1;(-y-Zij+)<n-mst(2i,zj)；if(dl<d>a = 2iJ；b 2jJ； ri = d) 当N=6时，给定一组测试数据测试数据与与预期结果相同。下面随机生成N个点的平面坐标，求解最近点对。并计算时间产生随机数代码：srand(unsignedNULL);i nt n;cout<Cl§输入点的个数； cin>>n；/cout«-Sf输入各个点的坐标：POINT *X=new P0iHTn;for(int i=0;i<n;i+)<Xi .x=rand()100;Xl.p>r

9、and()iioo；timet timel,time2; /计算时间代码tinel-time(NULL);"方法调用前设置一个tinel 得到的就毎抄 t2-GetTickcount()；"这样得到的就是臺秒time2=time(NULL);/方蛙调用前设置一个 tine2 /cout«,tine2:,«double(tine2)«endl; cout<<"耗时为"认doubl己l)"«endl;/统计时间为 tine2-tine1分治法例举:数据处理分析:扩大N的规模做测试n10100100

10、010000100000蛮力法1秒9秒57秒/分治法1秒9秒30秒/由以上数据可知，随着 N的增大，分治法效率比蛮力法效率越来越高。蛮力法求解最近对问题的过程是：分别计算每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑ivj的那些点对(Pi, Pj)。其实也就是组合的问题， 即从n个点中选取两个点的所有组合情况的问题，共有(n*(n-1)种情况。因此时间复杂度为：n 4 nn -1T(n)二 二 2=2 (n -i)= n(n -1)=0(n2)i =1 j=t+i#治法求解含有n个点的最近对问题，其时间复杂性可由下面的递推式表示：T(n) = 2T(n 2) f(n)合并子问题的解的时间 f(n) = 0(n)，根据通用分治递推式可得T(n)=0(nlog2 n)。实验结论与体会:分治法的思想就是将一个规模为 n的问题分解为k个规模较小的子问题， 这些子问 题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题解合并得到原问 题的解。通过本次试验我对分治法有了更深的了解。利用