分治法最近对问题

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

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

3、对问题的时间复杂度为：。3、 源程序及注释：#include<iostream>#include<cstring>#include<cmath>#include<algorithm>#include<time.h>using namespace std;#define eps 1e-8#define MAXN 10000000#define N 5000struct Pointdouble x,y;Point SN*2,S1N,S2N,P1N,P2N;double Distance(Point a,Point b) return sq

4、rt(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);int cmp1(Point a, Point b)return a.x<b.x;int cmp2(Point a, Point b)return a.y<b.y;double min(double a,double b)return a>b?b:a;/分治法求最近对问题double ClosestPoints1(Point S,int n)int i,j,m;if (n<2) return MAXN; elsedouble d0=MAXN;double d,d1,d2;int k1=0

5、;int k2=0;int j1=0;int j2=0;sort(S,S+n,cmp1);Point p=Sn/2;m=p.x;/m=S中各点x坐标的中位数for(i=0;i<(n+1)/2;i+)S1j1.x=Si.x;S1j1.y=Si.y;j1+;/构造S1中点的坐标小于mfor(i=(n+1)/2;i<n;i+)S2j2.x=Si.x;S2j2.y=Si.y;j2+;/构造S2中点的坐标大于md1=ClosestPoints1(S1,j1);d2=ClosestPoints1(S2,j2);d=min(d1,d2);for (i=0;i<j1;i+)if (m-S1i

6、.x<d)P1k1.x=S1i.x;P1k1.y=S1i.y;k1+;/构造P1为S1中点的坐标与m的距离小于d的点集for (i=0;i<j1;i+)if (S2i.x-m<d)P2k2.x=S2i.x;P2k2.y=S2i.y;k2+;/构造P2为S2中点的坐标与m的距离小于d的点集sort(P1,P1+k1,cmp2);/将P1中的点按y坐标升序排列sort(P2,P2+k2,cmp2);/将P2中的点按y坐标升序排列for(i=0;i<k1;i+)for(j=0;j<k2;j+)double ans=Distance(P1i,P2j);d0=min(d0,

7、ans);/求最小距离return min(d0,d);/蛮力法求最近对问题double ClosestPoints2(Point S,int n) double d0=MAXN; for(int i=0;i<n;i+) for(int j=i+1;j<n;j+) double d=Distance(Si,Sj);if(d<d0)d0=d; return d0;/测试两种算法int main()int n=5000;int i;srand(unsigned)time(NULL);for(i=0;i<n;i+)Si.x=rand()/(double)(RAND_MAX/1

8、0000);Si.y=rand()/(double)(RAND_MAX/10000); /产生随机点集clock_t start1,end1,start2,end2;start1=clock();double d1=ClosestPoints1(S,n);end1=clock();start2=clock();double d2=ClosestPoints2(S,n);end2=clock();cout<<"分治法求最近对问题运行时间及结果"<<endl<<double(end1-start1)/CLOCKS_PER_SEC<<

9、;" "<<d1<<endl;cout<<"蛮力法求最近对问题运行时间及结果"<<endl<<double(end2-start2)/CLOCKS_PER_SEC<<" "<<d2<<endl;return 0;4、 运行输出结果：比较运行结果，得出结论，分治法与蛮力法所求结果相同，从运行时间上来讲分治法运行远远快于蛮力法。五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：1.课本只给出了伪代码，具体的实验要靠自己动手上机反复实验才能完成。要通过赋简单值法来初步检验程序的是否正确，再以相同数据检验两种方法的运行结果是否一致来进一步判断程序是否正确，同时使得两种算法的比较更加公平，实验更有可信度。2.要比较分治法和蛮力法求最近对问题的时间复杂度，就要两者各自的运行时间。