分治法最近對(duì)問題(共5頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告學(xué) 號(hào)： 姓 名： 日 期： 得 分： 1、 實(shí)驗(yàn)內(nèi)容：分治法和蠻力法求最近對(duì)問題及其時(shí)間復(fù)雜度比較。二、所用算法的基本思想及復(fù)雜度分析：1.蠻力法求最近對(duì)問題：1） 基本思想：分別計(jì)算每一對(duì)點(diǎn)之間的距離，然后找出距離最小的那一對(duì)，為了避免對(duì)同一對(duì)點(diǎn)計(jì)算兩次距離，只考慮的那些點(diǎn)對(duì)。2）復(fù)雜度分析：對(duì)于此算法，主要就是算兩個(gè)點(diǎn)的歐幾里得距離。注意到在求歐幾里得距離時(shí)，避免了求平方根操作，其原因是：如果被開方的數(shù)越小，則它的平方根也越小。所以復(fù)雜度就是求平方，求執(zhí)行次數(shù)為：;即時(shí)間復(fù)雜度為。2.分治法求最近對(duì)問題：1）基本思想：用分治法解決最近點(diǎn)對(duì)問

2、題，就是將一個(gè)問題分解兩個(gè)子問題，然后遞歸處理子問題，然后合并?？赡軆蓚€(gè)點(diǎn)在每個(gè)子問題中，也可能兩個(gè)點(diǎn)分別在兩個(gè)子問題中，就這兩種情況。則基本過程為：找一條中垂線(坐位集合坐標(biāo)的中位數(shù))把個(gè)元素分成左右兩部分元素，然后分別求得兩邊的最短距離,，然后取兩者中的最小者記為，在中線兩邊分別取的距離，記錄該距離范圍內(nèi)點(diǎn)的個(gè)數(shù)，中線左邊有個(gè)元素，右邊有個(gè)元素，分別將兩邊的點(diǎn)按y坐標(biāo)升序排列，在左邊集合中每一個(gè)點(diǎn)，找右邊集合的點(diǎn)，找到與之距離小于的點(diǎn)，更新最短距離，直到循環(huán)結(jié)束，即可求出最短距離。2）復(fù)雜度分析：應(yīng)用分治法求解含有個(gè)點(diǎn)的最近對(duì)問題，其時(shí)間復(fù)雜性可由遞推式表示：。由以上分析：合并子問題的解的

3、時(shí)間。進(jìn)而可得分治法求最近對(duì)問題的時(shí)間復(fù)雜度為：。3、 源程序及注釋：#include<iostream>#include<cstring>#include<cmath>#include<algorithm>#include<time.h>using namespace std;#define eps 1e-8#define MAXN #define N 5000struct Pointdouble x,y;Point SN*2,S1N,S2N,P1N,P2N;double Distance(Point a,Point b) retu

4、rn sqrt(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;/分治法求最近對(duì)問題double ClosestPoints1(Point S,int n)int i,j,m;if (n<2) return MAXN; elsedouble d0=MAXN;double d,d1,d2;int

5、 k1=0;int k2=0;int j1=0;int j2=0;sort(S,S+n,cmp1);Point p=Sn/2;m=p.x;/m=S中各點(diǎn)x坐標(biāo)的中位數(shù)for(i=0;i<(n+1)/2;i+)S1j1.x=Si.x;S1j1.y=Si.y;j1+;/構(gòu)造S1中點(diǎn)的坐標(biāo)小于mfor(i=(n+1)/2;i<n;i+)S2j2.x=Si.x;S2j2.y=Si.y;j2+;/構(gòu)造S2中點(diǎn)的坐標(biāo)大于md1=ClosestPoints1(S1,j1);d2=ClosestPoints1(S2,j2);d=min(d1,d2);for (i=0;i<j1;i+)if (

6、m-S1i.x<d)P1k1.x=S1i.x;P1k1.y=S1i.y;k1+;/構(gòu)造P1為S1中點(diǎn)的坐標(biāo)與m的距離小于d的點(diǎn)集for (i=0;i<j1;i+)if (S2i.x-m<d)P2k2.x=S2i.x;P2k2.y=S2i.y;k2+;/構(gòu)造P2為S2中點(diǎn)的坐標(biāo)與m的距離小于d的點(diǎn)集sort(P1,P1+k1,cmp2);/將P1中的點(diǎn)按y坐標(biāo)升序排列sort(P2,P2+k2,cmp2);/將P2中的點(diǎn)按y坐標(biāo)升序排列for(i=0;i<k1;i+)for(j=0;j<k2;j+)double ans=Distance(P1i,P2j);d0=mi

7、n(d0,ans);/求最小距離return min(d0,d);/蠻力法求最近對(duì)問題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;/測(cè)試兩種算法int main()int n=5000;int i;srand(unsigned)time(NULL);for(i=0;i<n;i+)Si.x=rand()/(double)(RAND_

8、MAX/10000);Si.y=rand()/(double)(RAND_MAX/10000); /產(chǎn)生隨機(jī)點(diǎn)集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<<"分治法求最近對(duì)問題運(yùn)行時(shí)間及結(jié)果"<<endl<<double(end1-start1)/CLOCKS_PER_SEC&l

9、t;<" "<<d1<<endl;cout<<"蠻力法求最近對(duì)問題運(yùn)行時(shí)間及結(jié)果"<<endl<<double(end2-start2)/CLOCKS_PER_SEC<<" "<<d2<<endl;return 0;4、 運(yùn)行輸出結(jié)果：比較運(yùn)行結(jié)果，得出結(jié)論，分治法與蠻力法所求結(jié)果相同，從運(yùn)行時(shí)間上來(lái)講分治法運(yùn)行遠(yuǎn)遠(yuǎn)快于蠻力法。五、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題、采取的措施及獲得的相關(guān)經(jīng)驗(yàn)教訓(xùn)：1.課本只給出了偽代碼，具體的實(shí)驗(yàn)要靠自己動(dòng)手上機(jī)反復(fù)實(shí)驗(yàn)才能完成。要通過賦簡(jiǎn)單值法來(lái)初步檢驗(yàn)程序的是否正確，再以相同數(shù)據(jù)檢驗(yàn)兩種方法的運(yùn)行結(jié)果是否一致來(lái)進(jìn)一步判斷程序是否正確，同時(shí)使得兩種算法的比較更加公平，實(shí)驗(yàn)更有可信度。2.要比較分治法和蠻力法求最近對(duì)問題的時(shí)間復(fù)雜度，就要兩者各自的運(yùn)行時(shí)間。為此，必須要有