最近对蛮力分治实验报告.doc

《最近对蛮力分治实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《算法设计与分析》实验报告一学号：姓名：金玉琦日期：2011-10-13得分：一、实验内容：最近对问题，即找出一个点集合中距离最近的点对，分别运用蛮力法和分治法性能解决该问题，对两种算法进行性能比较。二、所用算法的基本思想及复杂度分析：1.分治法1）基本思想我们用分治法解决最近对问题，就是将集合S分成两个子集S1和S2，每个子集中有n/2个点。然后在每个子集中递归的求其最接近的点对，在求出每个子集的最接近点对后，关键问题是如何实现分治法中的合并步骤，如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是

2、，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需计算才能得到准确结果。2）复杂度分析应用分治法求解含有n个点得最近对问题，其时间复杂性可由下面的递推式表示：T（n）=2T（n/2）+f(n)合并子问题的解的时间f（n）=O（1），由通用分治递推式的主定理可得，T（n）=O（nlogn)2．蛮力法1）基本思想蛮力法求解最近对问题的过程是：分别计算每一对点之间的距离，然后找出距离最小的一对，为了避免对同一对点计算两次距离，只考虑i

3、杂度分析算法的基本操作是计算两个点的欧几里得距离。注意到在求欧几里得距离时，避免了球平方根操作，原因是：如果被开方的数越小，则它的平方根也越小。所以，算法的基本操作就是求平方，其执行次数为：T(n)==2=n（n-1）=O（n）三、源程序及注释：#defineLENGTH10000#definemin(X,Y)((X)<(Y)?(X):(Y))#include#include#include#include#include#incl

4、udeusingnamespacestd;structpoint{doublex;doubley;};pointpoints[LENGTH*2];//pointtempLeft[LENGTH];//pointtempRight[LENGTH];//排序intcmpp(pointa,pointb){if(a.x!=b.x)returna.x

5、eturn(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}//蛮力法函数doubleClosestPoints(intn,pointp[],int&index1,int&index2){doubleminDist=DBL_MAX;doubletemp;for(inti=0;i

6、nsqrt(minDist);}//分治法函数doubleDivPoints(pointp[],intbegin,intend){inti,j;intn=end-begin+1;intm=(begin+end)/2;if(n==2)returnDistence(p[begin],p[end]);//两个点返回距离if(n==3)//三个点直接求最近点并返回距离{doubled1=Distence(p[begin],p[begin+1]);doubled2=Distence(p[begin+1],p[end]);doubled

7、3=Distence(p[begin],p[end]);if(d1<=d2&&d1<=d3)returnd1;elseif(d2<=d3)returnd2;elsereturnd3;}doubleleft=DivPoints(p,begin,m);doubleright=DivPoints(p,m+1,end);doubled=min(left,right);intk,l,flag=0;//找到以m为中心的与m横坐标距离小于sqrt(d)的点for(i=begin;i<=end;i++){if(flag==0&&(p[m].

8、x-p[i].x)<=sqrt(d)){flag=1;k=i;}if((p[i].x-p[m].x)<=sqrt(d))l=i;}for(i=k;i<=m;i++){for(j=m+1;j<=l&&fabs((p[j].y-p[i].y))