分治法最近對問題.doc

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

1、《算法設計與分析》實驗報告學號：姓名：日期：得分：一、實驗內容：分治法和蠻力法求最近對問題及其時間復雜度比較。二、所用算法的基本思想及復雜度分析：1.蠻力法求最近對問題：1）基本思想：分別計算每一對點之間的距離，然后找出距離最小的那一對，為了避免對同一對點計算兩次距離，只考慮的那些點對。2）復雜度分析：對于此算法，主要就是算兩個點的歐幾里得距離。注意到在求歐幾里得距離時，避免了求平方根操作，其原因是：如果被開方的數越小，則它的平方根也越小。所以復雜度就是求平方，求執(zhí)行次數為：;即時間復雜度為。2.分治法求最近對問題：1）基本思想：用分治法解決最近點對問題，就是將一個問題分解兩個子問題，

2、然后遞歸處理子問題，然后合并。可能兩個點在每個子問題中，也可能兩個點分別在兩個子問題中，就這兩種情況。則基本過程為：找一條中垂線(坐位集合坐標的中位數)把個元素分成左右兩部分元素，然后分別求得兩邊的最短距離,，然后取兩者中的最小者記為，在中線兩邊分別取的距離，記錄該距離范圍內點的個數，中線左邊有個元素，右邊有個元素，分別將兩邊的點按y坐標升序排列，在左邊集合中每一個點，找右邊集合的點，找到與之距離小于的點，更新最短距離，直到循環(huán)結束，即可求出最短距離。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