分治法最近對(duì)問題.doc

《分治法最近對(duì)問題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告學(xué)號(hào)：姓名：日期：得分：一、實(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ì)問題，就是將一個(gè)問題分解兩個(gè)子問題，

2、然后遞歸處理子問題，然后合并?？赡軆蓚€(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ù)雜性可由遞推式表示：。由以上分析：合并子問題的解的時(shí)間。進(jìn)而可得分治法求最近

3、對(duì)問題的時(shí)間復(fù)雜度為：。三、源程序及注釋：#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;}//分治法求最近對(duì)問題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中各點(diǎn)x坐標(biāo)的中位數(shù)for(i=0;i<(n+1)/2;i++){S1[j1].x=S[i].x;S1[j1].y=S[i].y;j1++;}//構(gòu)造S1中點(diǎn)的坐標(biāo)小于mfor(i=(n+1)/2;i

6、[k1].y=S1[i].y;k1++;}//構(gòu)造P1為S1中點(diǎn)的坐標(biāo)與m的距離小于d的點(diǎn)集for(i=0;i

7、s);//求最小距離}}returnmin(d0,d);}}//蠻力法求最近對(duì)問題5doubleClosestPoints2(PointS[],intn){doubled0=MAXN;for(inti=0;i