最近对蛮力分治实验报告

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

2、最多只有n/2个点与它构成最接近点对的候选者，仍需计算才能得到准确结果。 2）复杂度分析应用分治法求解含有n个点得最近对问题，其时间复杂性可由下面的递推式表示：T（n）=2T（n/2）+f(n)合并子问题的解的时间f（n）=O（1），由通用分治递推式的主定理可得，T（n）=O（nlogn) 2蛮力法1）基本思想蛮力法求解最近对问题的过程是：分别计算每一对点之间的距离，然后找出距离最小的一对，为了避免对同一对点计算两次距离，只考虑ij的那些点对（Pi，Pj）。2）复杂度分析算法的基本操作是计算两个点的欧几里得距离。注意到在求欧几里得距离时，避免了球平方根操作，原因是：如果被开方的数越小，则它的平

3、方根也越小。所以，算法的基本操作就是求平方，其执行次数为：T(n)= =2=n（n-1）=O（n）三、源程序及注释：#define LENGTH 10000#define min(X,Y) (X)(Y)?(X):(Y)#include #include #include #include #include #include using namespace std;struct pointdouble x;double y;point pointsLENGTH*2;/ point tempLeftLENGTH;/ point tempRightLENGTH;/排序int cmpp(point a

4、,point b)if(a.x!=b.x) return a.xb.x;return a.yb.y;/求距离的平方，在这不用求出距离，直接求出平方少计算一次，效果相同double Distence(point a,point b)return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);/蛮力法函数double ClosestPoints(int n,point p,int &index1,int &index2)double minDist=DBL_MAX;double temp;for (int i=0;in;i+)for (int j=i+1;j=n;

5、j+)temp=Distence(pi,pj);if(tempminDist)minDist=temp;index1=i;index2=j;return sqrt(minDist);/分治法函数double DivPoints(point p,int begin,int end)int i,j;int n=end-begin+1;int m=(begin+end)/2;if(n=2)return Distence(pbegin,pend);/两个点返回距离if(n=3)/三个点直接求最近点并返回距离double d1=Distence(pbegin,pbegin+1);double d2=Di

6、stence(pbegin+1,pend);double d3=Distence(pbegin,pend);if(d1=d2&d1=d3)return d1;else if(d2=d3)return d2;else return d3;double left=DivPoints(p,begin,m);double right=DivPoints(p,m+1,end);double d=min(left,right);int k,l,flag=0;/找到以m为中心的与m横坐标距离小于sqrt(d)的点for(i=begin;i=end;i+)if(flag=0&(pm.x-pi.x)=sqrt(

7、d)flag=1;k=i;if(pi.x-pm.x)=sqrt(d)l=i;for (i=k;i=m;i+)for (j=m+1;j=l&fabs(pj.y-pi.y)sqrt(d);j+)if(Distence(pi,pj)=d)d=Distence(pi,pj);/ for(i=begin;i=m;i+)/ if(pm.x-pi.x)=sqrt(d)/ tempLeftk+=pi;/将m左侧与m水平距离小于d的点放入tempLeft中/ for(i=m+1;i=end;i+)/ if(pi.x-pm.x)=sqrt(d)/ tempRightl+=pi;/将m右侧与m水平距离小于d的点放入

8、tempRight中/ /将tempLeft和tempRight按y升序排列/ sort(tempLeft,tempLeft+k,cmpy);/ sort(tempRight,tempRight+l,cmpy);/ double md=DBL_MAX;/ for(i=0;ik;i+)/ for(j=0;jl&fabs(tempLefti.y-tempRightj.y)=sqrt(d);j+)/ / if(Distence(tempLefti,tempRightj)=md)/ md=Distence(tempLefti,tempRightj);/ return d;/主函数void main()

9、LARGE_INTEGER begin,end,frequency;int n;int index1,index2;double forcedist,divdist;coutn;coutendl;/生成随机数srand(time(0);for (int i=0;in;i+)pointsi.x=rand();pointsi.y=rand();/蛮力法求最近对时间QueryPerformanceFrequency(&frequency);QueryPerformanceCounter(&begin);forcedist=ClosestPoints(n,points,index1,index2);Q

10、ueryPerformanceCounter(&end);cout最短距离是：forcedist两个点是：(pointsindex1.x,pointsindex1.y)和(pointsindex2.x,pointsindex2.y)endl;cout蛮力法求解时间(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPartsendl;/分治法求最近对时间QueryPerformanceCounter(&begin);sort(points,points+n,cmpp);/对点对排序divdist=sqrt(DivPoints(points,0,n-1);QueryPerformanceCounter(&end);cout最短距离是：divdistendl;cout分治法求解时间(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPartsendl;四、运行输出结果：五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：1在点的个数比较少的时候，蛮力法所用时间时间比