最近对蛮力分治实验报告

1《算法设计与分析》实验报告一学号：1004091130姓名：金玉琦日期：2011-10-13得分：一、实验内容：最近对问题，即找出一个点集合中距离最近的点对，分别运用蛮力法和分治法性能解决该问题，对两种算法进行性能比较。二、所用算法的基本思想及复杂度分析：1.分治法1）基本思想我们用分治法解决最近对问题，就是将集合S分成两个子集S1和S2，每个子集中有n/2个点。然后在每个子集中递归的求其最接近的点对，在求出每个子集的最接近点对后，关键问题是如何实现分治法中的合并步骤，如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需计算才能得到准确结果。2）复杂度分析应用分治法求解含有n个点得最近对问题，其时间复杂性可由下面的递推式表示：T（n）=2T（n/2）+f(n)合并子问题的解的时间f（n）=O（1），由通用分治递推式的主定理可得，T（n）=O（nlog2n)2．蛮力法1）基本思想蛮力法求解最近对问题的过程是：分别计算每一对点之间的距离，然后找出距离最小的一对，为了避免对同一对点计算两次距离，只考虑ij的那些点对（Pi，Pj）。2）复杂度分析算法的基本操作是计算两个点的欧几里得距离。注意到在求欧几里得距离时，避免了球平方根操作，原因是：如果被开方的数越小，则它的平方根也越小。所以，算法的基本操作就是求平方，其执行次数为：T(n)=11ninij12=211)(niin=n（n-1）=O（n2）三、源程序及注释：#defineLENGTH10000#definemin(X,Y)((X)(Y)?(X):(Y))#includeFLOAT.H#includeWINDOWS.H#includeTIME.H2#includeMATH.H#includealgorithm#includeIOSTREAMusingnamespacestd;structpoint{doublex;doubley;};pointpoints[LENGTH*2];//pointtempLeft[LENGTH];//pointtempRight[LENGTH];//排序intcmpp(pointa,pointb){if(a.x!=b.x)returna.xb.x;returna.yb.y;}//求距离的平方，在这不用求出距离，直接求出平方少计算一次，效果相同doubleDistence(pointa,pointb){return(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;in;i++)for(intj=i+1;j=n;j++){temp=Distence(p[i],p[j]);if(tempminDist){minDist=temp;index1=i;index2=j;}}3returnsqrt(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]);doubled3=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].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))sqrt(d);j++){if(Distence(p[i],p[j])=d)d=Distence(p[i],p[j]);}}//for(i=begin;i=m;i++)//if((p[m].x-p[i].x)=sqrt(d))//tempLeft[k++]=p[i];//将m左侧与m水平距离小于d的点放入tempLeft中4//for(i=m+1;i=end;i++)//if((p[i].x-p[m].x)=sqrt(d))//tempRight[l++]=p[i];//将m右侧与m水平距离小于d的点放入tempRight中////将tempLeft和tempRight按y升序排列//sort(tempLeft,tempLeft+k,cmpy);//sort(tempRight,tempRight+l,cmpy);//doublemd=DBL_MAX;//for(i=0;ik;i++)//for(j=0;jl&&fabs(tempLeft[i].y-tempRight[j].y)=sqrt(d);j++)//{//if(Distence(tempLeft[i],tempRight[j])=md)//md=Distence(tempLeft[i],tempRight[j]);//}returnd;}//主函数voidmain(){LARGE_INTEGERbegin,end,frequency;intn;intindex1,index2;doubleforcedist,divdist;cout输入随机点个数：;cinn;coutendl;//生成随机数srand(time(0));for(inti=0;in;i++){points[i].x=rand();points[i].y=rand();}//蛮力法求最近对时间QueryPerformanceFrequency(&frequency);QueryPerformanceCounter(&begin);forcedist=ClosestPoints(n,points,index1,index2);QueryPerformanceCounter(&end);5cout最短距离是：forcedist两个点是：(points[index1].x,points[index1].y)和(points[index2].x,points[index2].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在点的个数比较少的时候，蛮力法所用时间时间比分治法少，点数比较多的情况下，分治法的优势就很明显了，所用时间明显比蛮力法少。2.在输入一个点的时候程序会崩溃，因为返回值是无穷大，分治法的合并过程中会出错。63.分治法中，借鉴别人的做法，没有产生P1和P2两个子点集，这样节省了空间，而且将整个点集排序之后就没有必要划分成两个点集。上述代码中被注释部分是将整个点集划分成两个子集的做法。