分治法最近对问题.doc

《分治法最近对问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》实验报告学号：姓名：日期：得分：一、实验内容：分治法和蛮力法求最近对问题及其时间复杂度比较。二、所用算法的基本思想及复杂度分析：1.蛮力法求最近对问题：1）基本思想：分别计算每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑的那些点对。2）复杂度分析：对于此算法，主要就是算两个点的欧几里得距离。注意到在求欧几里得距离时，避免了求平方根操作，其原因是：如果被开方的数越小，则它的平方根也越小。所以复杂度就是求平方，求执行次数为：;即时间复杂度为。2.分治法求最近对问题：1）基本思想：用分治法解决最近点对问题，就是将一个问题分解两个子问题，

2、然后递归处理子问题，然后合并。可能两个点在每个子问题中，也可能两个点分别在两个子问题中，就这两种情况。则基本过程为：找一条中垂线(坐位集合坐标的中位数)把个元素分成左右两部分元素，然后分别求得两边的最短距离,，然后取两者中的最小者记为，在中线两边分别取的距离，记录该距离范围内点的个数，中线左边有个元素，右边有个元素，分别将两边的点按y坐标升序排列，在左边集合中每一个点，找右边集合的点，找到与之距离小于的点，更新最短距离，直到循环结束，即可求出最短距离。2）复杂度分析：应用分治法求解含有个点的最近对问题，其时间复杂性可由递推式表示：。由以上分析：合并子问题的解的时间。进而可得分治法求最近

3、对问题的时间复杂度为：。三、源程序及注释：#include5#include#include#include#includeusingnamespacestd;#defineeps1e-8#defineMAXN10000000#defineN5000structPoint{doublex,y;};PointS[N*2],S1[N],S2[N],P1[N],P2[N];doubleDistance(Pointa,Pointb){returnsqrt((a.x-b.x)*(a.x-b.x)+(a.y-

4、b.y)*(a.y-b.y));}intcmp1(Pointa,Pointb){returna.xb?b:a;}//分治法求最近对问题doubleClosestPoints1(PointS[],intn){inti,j,m;if(n<2)returnMAXN;else{doubled0=MAXN;doubled,d1,d2;intk1=0;intk2=0;intj1=0;intj2=0;sort(S,S+n,cmp1);Point

5、p=S[n/2];5m=p.x;//m=S中各点x坐标的中位数for(i=0;i<(n+1)/2;i++){S1[j1].x=S[i].x;S1[j1].y=S[i].y;j1++;}//构造S1中点的坐标小于mfor(i=(n+1)/2;i

6、[k1].y=S1[i].y;k1++;}//构造P1为S1中点的坐标与m的距离小于d的点集for(i=0;i

7、s);//求最小距离}}returnmin(d0,d);}}//蛮力法求最近对问题5doubleClosestPoints2(PointS[],intn){doubled0=MAXN;for(inti=0;i