分治算法求解二維極大點問題的求解

分治算法求解二維極大點問題成員分工：源程序文件——李鳳媛文檔：二維極大點問題描述、分治算法求解二維極大點問題的算法思想、算法描述蒙慧穎算法實現(xiàn)一一李橋秀實驗環(huán)境、實驗結(jié)果——馬迪文檔格式一一李樂本課題PPT——劉思志、李樂利用PPT對課題完成情況做介紹——李鳳媛一、 二維極大點問題的描述在二維空間中，如果X1>X2且Y1>Y2,那么稱點(X1,Y1)支配點(X2,Y2)。如果一個點沒有其他點支配，那么稱其為極大者。己知有n個點的集合，求極大點問題是指找出在n個點中的所有極大點。二、 分治算法求解二維極大點問題的算法思想通過分治策略來解決二維極大點問題。首先找出垂直于x軸的中位線L，用它劃分整個點集為兩個子集，分別用SL和SR表示中線L的左邊點集合和右邊點集合。然后分別找出SL和SR的極大點。找出SL和SR的極大點后將它們合并求出總點集的極大點，由于在SR中點的x值總是大于SL中每個點的x值，所以SR中的極大點合并后仍是極大點，而SL中的極大點需滿足y值不小于SR中極大點的最大y值才是合并后的極大點。三、 算法描述：步驟1：如果S只含一個點，那么輸出該點為極大點；否則找一條垂直于x軸的直線L，它劃分點集合為兩個子集合SL和SR，每個子集含有n/2個點。步驟2：遞歸地找出SL和SR的極大點。步驟3：將SL和SR的極大點投影到直線L上，并根據(jù)它們的y值排序這些點。對投影進(jìn)行線性掃描，如果SL中的極大點的y值小于SR中某個極大點的y值，那么舍棄它。四、 算法實現(xiàn)用預(yù)排序分治策略求解二維極大點問題，首先定義結(jié)構(gòu)體數(shù)組用來保存點的坐標(biāo)。使用隨機函數(shù)、計時函數(shù)來生成點的坐標(biāo)集并記錄運行時間。然后對坐標(biāo)集按照x值大小進(jìn)行冒泡排序，并用for循環(huán)為SL、SR兩個點集賦值，定義printf函數(shù)用for循環(huán)輸出S、SL、SR中點的坐標(biāo)，再分別遞歸求出SL、SR的極大點再將極大點輸出并記錄在集合m中，合并時for循環(huán)輸出m中SR的極大點，對集合m中SL的極大點按y值大小進(jìn)行冒泡排序，并輸出m中比SR的極大點的最大y值大的SL的極大點。時間復(fù)雜度：因為在算法實現(xiàn)時用到了冒泡排序，而其他部分的時間復(fù)雜度均少于O(n2).，故整個程序的時間復(fù)雜度為O(n2).五、 實驗環(huán)境Win10系統(tǒng)Inteli7-7700HQCPU@2.80GHz處理器，內(nèi)存8192MBRAM編譯器環(huán)境(Dev-C++)六、實驗結(jié)果對程序進(jìn)行編譯運行，輸出案例：根據(jù)附表算法代碼(以下數(shù)據(jù)皆為隨機生成數(shù)據(jù))，我們可以得到以下輸出:請輸入總元素個數(shù)：5第1個元素的坐標(biāo)xy：(15967,19417)第2個元素的坐標(biāo)xy：(28311,28424)第3個元素的坐標(biāo)xy：(5416,18462)第4個元素的坐標(biāo)xy：(11304,630)第5個元素的坐標(biāo)xy：(19645,18692)S:(5416,18462)(11304,630)(15967,19417)(19645,18692)(28311,28424)SR:(15967,19417)(19645,18692)(28311,28424)SL:(5416,18462)(11304,630)SR極大點：(28311,28424)SL極大點：(5416,18462)(11304,630)總極大點：(28311,28424)Totaltime(運行時間):4ms分治策略求二維極大點問題規(guī)模與運行時間的關(guān)系:

表1分治策略求二維極大點問題規(guī)模與運行時間的關(guān)系運行規(guī)模(n)運行時間(ms)12228620165055100127500746100015372000304750007629不同運行規(guī)模(n)下的運行時間(ms)9UUU76298000/m間日時7000/_60005000行運4000304730001537^/2000746100022 6 16 55 127 012 8 20 50 100 500 1000運行規(guī)模(n)20005000圖1不同運行規(guī)模(n)下的運行時間(ms)附錄（源程序代碼）#include<cstdlib>#include<ctime>#include<iostream>usingnamespacestd;clock_tstart,end;//clock_t是用來保存時間的數(shù)據(jù)類型constintN=10005;intn; 〃輸入點的個數(shù)ints=0; //用于存儲數(shù)組m中元素個數(shù)intt=0; //m中SR點集極大點中的最大y值對應(yīng)的下標(biāo)intc=0;//SR點集中極大點個數(shù)，即SR點集中極大點在點集m中的最大下標(biāo)+1structpoint(doublex,y;};structpointS[N],SL[N],SR[N],m[N];//分別定義數(shù)組S[N],SL[N],SR[N],m[N]存儲原始點集、左側(cè)點集、右側(cè)點集、總極大點voidsortx(intn);voidprintf();voidfenzhiSR(inta,intb);voidfenzhiSL(inta,intb);voidhebing();intmain()(inti;start=clock(); //程序開始計時unsignedseed; 〃定義無符號類型的seedseed=time(0); 〃調(diào)用time函數(shù)獲取種子值srand(seed); 〃用srand函數(shù)為隨機數(shù)生成器提供一個種子cout<<"請輸入總元素個數(shù)："；cin>>n;for(i=0;i<n;i++)//用函數(shù)隨機為n個點賦值(cout<<"第"<<i+1<<"個元素的坐標(biāo)xy：";S[i].x=rand(); 〃生成隨機數(shù)并作為該點的x值賦值給S[i].xS[i].y=rand(); 〃生成隨機數(shù)并作為該點的x值賦值給S[i].ycout<<”("<<S[i].x<<”,"<<S[i].y<<”)”<<endl;}sortx(n); //將點集S中的點按x值從小到大排序for(i=0;i<n;i++)//分治策略將點集S按x的大小劃分為SR、SL左右兩部分(if(i<n/2)SL[i]=S[i];elseSR[i-n/2]=S[i];}printf(); 〃輸出S、SL、SR中的點cout<<endl<<"SR極大點："；fenzhiSR(0,1); //遞歸求SR中極大點并打印cout<<endl<<"SL極大點："；fenzhiSL(0,1); //遞歸求SL中極大點并打印cout<<endl<<"總極大點："；hebing();end=clock(); //程序結(jié)束用時doubleendtime=(double)(end-start); //程序結(jié)束用時時間-開始計時時間得出運行時間cout<<endl<<"Totaltime:"<<endtime<<"ms";//輸出運行時間單位為msreturn0;voidsortx(intn)//對S中的點按x值從小到大排序inti,j;doubletx,ty;for(j=n-l;j>0;j-)(for(i=0;i<j;i++)(if(S[i].x>S[i+l].x)(tx=S[i+l].x;ty=S[i+l].y;S[i+l]=S[i];S[i].x=tx;S[i].y=ty;voidprintf()//輸出S、SL、SR中的點{inti;cout?"S:";for(i=0;i<n;i++)cout?"("?S[i].x?","?S[i].y<<")";cout?endl?"SR:";for(i=0;i<(n+l)/2;i++)cout?"("?SR[i].x?","?SR[i].y<<")";cout?endl?"SL:";for(i=0;i<n/2;i++)cout<<”("<<SL[i].x<<”,"<<SL[i].y<<”)”;voidfenzhiSR(inta,intb)//分治用遞歸求SR中極大點并打印(if(n==1)(m[s]=SR[a];s++;cout<<”("<<SR[a].x<<”,"<<SR[a].y<<”)”;}elseif(a==(n-1)/2)(m[s]=SR[a];s++;cout<<”("<<SR[a].x<<”,"<<SR[a].y<<”)”;}elseif((SR[a].y>SR[b].y)&&(b==(n-1)/2))(m[s]=SR[a];s++;cout<<”("<<SR[a].x<<”,"<<SR[a].y<<”)”;fenzhiSR(a+1,a+2);}elseif(SR[a].y>SR[b].y)fenzhiSR(a,b+1);elsefenzhiSR(a+1,a+2);c=s; //SR點集中極大點個數(shù)，即SR點集中極大點在點集m中的最大下標(biāo)+1for(inti=0;i<s-1;i++) 〃找到SR點集極大點中的最大y值{if(m[i].y<m[i+1].y)t=i+1;}voidfenzhiSL(inta,intb)//分治用遞歸求SL中極大點并打印(if(n==1)return;elseif(a==(n-2)/2)(m[s]=SL[a];s++;cout<<”("<<SL[a].x<<”,"<<SL[a].y<<”)”;return;}elseif((SL[a].y>SL[b].y)&&(b==(n-2)/2))(m[s]=SL[a];s++;cout<<”("<<SL[a].x<<”,"<<SL[a].y<<”)”;fenzhiSL(a+1,a+2);}elseif(SL[a].y>SL[b].y)fenzhiSL(a,b+1);elsefenzhiSL(a+1,a+2);}voidhebing()〃合并SR、SL中的極大點求出總極大點(inti,j;doubletx,ty;for(i=0;i<c;i++) 〃輸出m中SR的極大點cout<<”("<<m[i].x<<”,"<<m[i].y<<”)”;if(n==1)return;else{for(j=s-2;