算法分析與復(fù)雜性理論-實(shí)驗(yàn)報(bào)告-求最近點(diǎn)對(duì)的問(wèn)題

1、深圳 大學(xué)實(shí) 驗(yàn)報(bào)告課程名稱：算法分析與復(fù)雜性理論實(shí)驗(yàn)項(xiàng)目名稱：實(shí)驗(yàn)二分治法求最近點(diǎn)對(duì)問(wèn)題學(xué)院：計(jì)算機(jī)與軟件學(xué)院專業(yè)：軟件工程指導(dǎo)教師：楊烜報(bào)告人：文成學(xué)號(hào):2150230509 班級(jí)：15級(jí)軟工學(xué)術(shù)型實(shí)驗(yàn)時(shí)間：2015-10-22實(shí)驗(yàn)報(bào)告提交時(shí)間：2015-10-24教務(wù)部制實(shí)驗(yàn)?zāi)康呐c要求：實(shí)驗(yàn)?zāi)康模?1) 掌握分治法思想。(2) 學(xué)會(huì)最近點(diǎn)對(duì)問(wèn)題求解方法。實(shí)驗(yàn)要求1. 在blackboard提交電子版實(shí)驗(yàn)報(bào)告，注意實(shí)驗(yàn)報(bào)告的書寫，整體排版。2. 實(shí)驗(yàn)報(bào)告的實(shí)驗(yàn)步驟部分需詳細(xì)給出算法思想與實(shí)現(xiàn)代碼之間的關(guān)系解釋，不可直接粘貼代碼(直接粘貼代碼者視為該部分內(nèi)容缺失)。3. 實(shí)驗(yàn)報(bào)告樣式可從表格

2、下載學(xué)生適用在校生管理-實(shí)踐教學(xué)-實(shí)驗(yàn)：深圳大學(xué)學(xué)生實(shí)驗(yàn)報(bào)告)4. 源代碼作為實(shí)驗(yàn)報(bào)告附件上傳。5. 在實(shí)驗(yàn)課需要現(xiàn)場(chǎng)運(yùn)行驗(yàn)證。實(shí)驗(yàn)內(nèi)容:1. 對(duì)于平面上給定的 N個(gè)點(diǎn)，給出所有點(diǎn)對(duì)的最短距離，即，輸入是平面上的N個(gè)點(diǎn)，輸出是N點(diǎn)中具有最短距離的兩點(diǎn)。2. 要求隨機(jī)生成N個(gè)點(diǎn)的平面坐標(biāo)，應(yīng)用蠻力法編程計(jì)算出所有點(diǎn)對(duì)的最短距離。3. 要求隨機(jī)生成N個(gè)點(diǎn)的平面坐標(biāo)，應(yīng)用分治法編程計(jì)算出所有點(diǎn)對(duì)的最短距離。4. 分別對(duì)N=100,1000,10000,100000，統(tǒng)計(jì)算法運(yùn)行時(shí)間，比較理論效率與實(shí)測(cè)效率的差異，同時(shí)對(duì)蠻力法和分治法的算法效率進(jìn)行分析和比較。5. 利用Unity3D輸出分治算法中間每

3、個(gè)步驟的計(jì)算結(jié)果，并增設(shè)help按鈕，詳細(xì)解釋算法思想。算法思想提示1. 預(yù)處理：根據(jù)輸入點(diǎn)集S中的x軸和y軸坐標(biāo)進(jìn)行排序，得到X和Y,很顯然此時(shí)X和Y中的點(diǎn)就是S中的點(diǎn)。2. 點(diǎn)數(shù)較少時(shí)的情形1 kd = g直接計(jì)Ji1V直揍計(jì)葺 »只有一個(gè)點(diǎn)* A只有兩個(gè)點(diǎn)* A只有三個(gè)點(diǎn)3. 點(diǎn)數(shù)|S|>3時(shí)，將平面點(diǎn)集 S分割成為大小大致相等的兩個(gè)子集Sl和Sr,選取一個(gè)垂直線L作為分割直線，考慮 Xl和Xr, Yl和Yr,這里還需要排序嗎？實(shí)驗(yàn)過(guò)程及內(nèi)容:（實(shí)驗(yàn)代碼已作為附件提交，名為“算法實(shí)驗(yàn)二.cpp 了當(dāng)點(diǎn)的數(shù)量小于3時(shí)，直接計(jì)算，當(dāng)點(diǎn)的個(gè)數(shù)大于3時(shí)，采用分治法當(dāng)N=1時(shí)只有一

4、個(gè)直” E:O +PROJECT、算法克驗(yàn)二'Debug' 算法實(shí)驗(yàn)二 exe"-請(qǐng)輸入點(diǎn)的個(gè)數(shù)：1請(qǐng)輸入各個(gè)點(diǎn)的坐標(biāo)：1 1最近點(diǎn)對(duì)的距離為無(wú)窮大！ Press any key to continue捜狗拼音輸入法全：當(dāng)N=2時(shí)只有兩個(gè)點(diǎn)，最近點(diǎn)對(duì)就是這兩個(gè)點(diǎn)測(cè)試數(shù)據(jù)為（1,1）（ 2,2）預(yù)期結(jié)果為d=1.414與預(yù)期結(jié)果相同使用 蠻力法 求最近點(diǎn)對(duì)，核心代碼如下"求距離平方的函數(shù)double Distinyui5h2(Node atNode b)return (a .x-b_x-b_x) + (a .y-b-if) *(a_yb .y);"蠻

5、力法求最近對(duì)void BruteForceCconst NLlst & L,CloseNode & cnode,int begin,int end) <For(int i=t)egin;i<=end;i*+) For(int j-i*1;j<-end;j*+)<double space = Distinyuish2(L，datai,L.dat日j)： iF<spdce<cnode«spaceb)<cnode .a-L.data1; cnode,b=L-dataj; cnode space=space;（計(jì)算兩點(diǎn)之間的距離，分別

6、將每個(gè)點(diǎn)與其它點(diǎn)的距離求出來(lái)，找出最近點(diǎn)距離）當(dāng)N>3時(shí)，使用分治法的情況核心代碼如下:else/當(dāng)23時(shí)進(jìn)行分治<APOIHT *SL-nev fi_POINT(high-low)/2+1; 匸FDIHT *SR-neu nIPOINT(high-low)/2;"=(high-low)/2 ；哦組以碼界劃夯為廚半j=k=t);for(i=B;i<=high-lou;i*+)<if(Vi*indeK<=n)SLj + *-ViJ ；"收集左邊子集中的最近點(diǎn)對(duì)else SRkt+=Yi ;"H煤右邊子集中的最近點(diǎn)對(duì)> closes

7、tCX,SL,low,m,31,bl5dl);/if 算左邊子集的最近點(diǎn)對(duì)closes t(X,Sfi,m+1,tiigh,ar.br,dr);/計(jì)算右集的巖疋點(diǎn)對(duì) iF(dl<dr)i=al;b=bl;d=dl;else<a=ar;b=tjr ；d=dr;POIlfT *2=new POI NThigti-low+1 ;k=o；For(i=B;i<=t»igh-lcw;i*+)/收集距離中線?礙小于d的元素，保存SU數(shù)組科 <lf(Fabs(Xn.x-Vl.x)<d>Zk-X=V1.x;Zk-.y=Vi.j|；for(i-l;l<k;l+)

8、<far(j=i>1;(-y-Zij+)<n-mst(2i,zj)；if(dl<d>a = 2iJ；b 2jJ； ri = d) 當(dāng)N=6時(shí)，給定一組測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)與與預(yù)期結(jié)果相同。下面隨機(jī)生成N個(gè)點(diǎn)的平面坐標(biāo)，求解最近點(diǎn)對(duì)。并計(jì)算時(shí)間產(chǎn)生隨機(jī)數(shù)代碼：srand(unsignedNULL);i nt n;cout<Cl§輸入點(diǎn)的個(gè)數(shù)； cin>>n；/cout«-Sf輸入各個(gè)點(diǎn)的坐標(biāo)：POINT *X=new P0iHTn;for(int i=0;i<n;i+)<Xi .x=rand()100;Xl.p>r

9、and()iioo；timet timel,time2; /計(jì)算時(shí)間代碼tinel-time(NULL);"方法調(diào)用前設(shè)置一個(gè)tinel 得到的就毎抄 t2-GetTickcount()；"這樣得到的就是臺(tái)秒time2=time(NULL);/方蛙調(diào)用前設(shè)置一個(gè) tine2 /cout«,tine2:,«double(tine2)«endl; cout<<"耗時(shí)為"認(rèn)doubl己l)"«endl;/統(tǒng)計(jì)時(shí)間為 tine2-tine1分治法例舉:數(shù)據(jù)處理分析:擴(kuò)大N的規(guī)模做測(cè)試n10100100

10、010000100000蠻力法1秒9秒57秒/分治法1秒9秒30秒/由以上數(shù)據(jù)可知，隨著 N的增大，分治法效率比蠻力法效率越來(lái)越高。蠻力法求解最近對(duì)問(wèn)題的過(guò)程是：分別計(jì)算每一對(duì)點(diǎn)之間的距離，然后找出距離最小的那一對(duì)，為了避免對(duì)同一對(duì)點(diǎn)計(jì)算兩次距離，只考慮ivj的那些點(diǎn)對(duì)(Pi, Pj)。其實(shí)也就是組合的問(wèn)題， 即從n個(gè)點(diǎn)中選取兩個(gè)點(diǎn)的所有組合情況的問(wèn)題，共有(n*(n-1)種情況。因此時(shí)間復(fù)雜度為：n 4 nn -1T(n)二 二 2=2 (n -i)= n(n -1)=0(n2)i =1 j=t+i#治法求解含有n個(gè)點(diǎn)的最近對(duì)問(wèn)題，其時(shí)間復(fù)雜性可由下面的遞推式表示：T(n) = 2T(n 2) f(n)合并子問(wèn)題的解的時(shí)間 f(n) = 0(n)，根據(jù)通用分治遞推式可得T(n)=0(nlog2 n)。實(shí)驗(yàn)結(jié)論與體會(huì):分治法的思想就是將一個(gè)規(guī)模為 n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題， 這些子問(wèn) 題互相獨(dú)立且與原問(wèn)題相同。遞歸地解這些子問(wèn)題，然后將各個(gè)子問(wèn)題解合并得到原問(wèn) 題的解。通過(guò)本次試驗(yàn)我對(duì)分治法有了更深的了解。利用