算法設(shè)計與分析課程大作業(yè)

::與信息工程?？婆c技術(shù)41、描述 42、分析 43.的描述 54、部分實現(xiàn) 65.86、時空效率分析 8二貪心多機81、描述 82、分析 99計復(fù)雜性分析 1112三回溯批1212131415時間復(fù)雜性分析 15四比較 16五課程學(xué)習(xí)總結(jié) 、從而提運行效益的關(guān)鍵環(huán)節(jié)之一。把各個分配到車間現(xiàn)有的設(shè)備上并確定它們的先后次序這是一項復(fù)雜的工本文就排序進行了研究通過對幾個經(jīng)典算法的分析討論總結(jié)了各個算法對的求解過程并給出了每個算法的復(fù)雜及性能分析。關(guān)鍵詞；動態(tài)規(guī)劃；貪心算法；回溯法；1、描述給定n個，每個有兩工序，分別在兩臺機器上處理。臺機器次只能處理工序并且工序旦開始就必須進行下去直到完成個只有在機器1上的處理完成以后才能由機器2處理。假設(shè)已知i在機器j上需要的處理時間為。就是要求確定個的處理順序使得盡快完成這n 個。2、分析直觀上，個最優(yōu)M1上會有機器空閑和積2種情況。在M1S中M2還在加tS所。T(N,0)。由的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，T(N,0)

min{ai1in

T(N

{i},bi

)}（1）

T(S

}ba})}i

i i2）N。將規(guī)?？s小。S2M1完max{t-ai,0}。3. 算法描述分析知流水定存滿足Johnson法則且易由下面算法確定。流水Johnson算法：令N1

|],2},N2

|],2}；將依非減序；將依非增序；接種Johnson法則。4、部分算法實現(xiàn)intFlowShop(intn,inta[],intb[],intc[]){inti;Jobtype*d=newJobtype[n];for(i=0;i<n;i++){d[i].key=a[i]>b[i]?b[i]:a[i];//按Johnson法則分別取對應(yīng)的b[i]或a[i]值作為關(guān)鍵字d[i].job=a[i]<=b[i];//給符合條件a[i]<b[i]的放入到N1子集標記為trued[i].index=i;}//對數(shù)組d按關(guān)鍵字升序進行排序intj=0,k=n-1;for(i=0;i<n;i++){if(d[i].job){c[j++]=d[i].index;//將排過序的數(shù)組d，取其中作業(yè)序號屬于N1的從前面進入}else{c[k--]=d[i].index;//屬于N2的從后面進入，從而實現(xiàn)N1的非減序排序，N2的非增序排序}}}j=a[c[0]];k=j+b[c[0]];for(i=1;i<n;i++){j+=a[c[i]];12]誰后完kj<k?k+b[c[i]]:j+b[c[i]];//計算優(yōu)加工}deleted;returnk;}: 6、時空效率分析Flowshop的主要計算時間花在對作業(yè)集的排序上。wb所需要的計算時間為O(og)然是。二．貪心算法解多機調(diào)度1、描述nm臺機器加工處理完成。約定，每個作業(yè)均可在任何NP,用貪心選擇策略有時可以設(shè)計出較好的近似算法。::2、算法分析貪心算法只需按順序以數(shù)組方式提供各作業(yè)的加工時間和機器近的機器，所需要的加工時間，即為最長作業(yè)所需時間。若作業(yè)數(shù)大于機器臺數(shù)，將作業(yè)按加工時間的多少降序排序，以mm個機器，最小堆頂是即m部分算法實現(xiàn)typedefstructNodetypedefstructNode{ intID,avail;}manode;//ID號 avail每次作業(yè)的初始時間manodemachine[N];jobnodejob[N];/*找出下個作業(yè)執(zhí)行機器*/manode*Find_min(manodea[],intm){ manode*temp=for(inti=1;i<m;i++){if(a[i].avail<temp->avail)temp=&a[i]; }returntemp; }/* voidSort(jobnodet[]intn){ jobnodetemp;for(inti=0;i<n-1;i++)for(intj=n-1;j>i;j--){ if(job[j].time>job[j-1].time){ temp=job[j];job[j]=job[j-job[j-1]=temp;}}}voidmain(){for(i=0;i<n;i++){ cin>>job[i].time;job[i].ID=i+1; ()\n");cin>>m;for(i=0;i<m;i++)//給機器進行編號并初始化{ machine[i].ID=i+1;machine[i].avail=0; putchar('\n');if(n<=m){{printf("!\n"); return;}Sort(job,n);for(i=0;i<n;i++){ma=Find_min(machine,m);printf(":M%d%d->%d%d\n",putchar('\n');printf(":%d\n",temp);}n≤m 有以次安排各法要o(1)。n>m ，排序耗O(nlogn)。初始化堆要。和put運共耗O(nlogm),因此法O(nlogn+nlogm)=O(nlogn)。: 三．回溯法解決批作業(yè)調(diào)度描述入：NMt[i],t[i]=xi個任務(wù)完成需要時間x，出：bestx[i]=xi個任務(wù)分::x：NMt[i]:ix[i]=j:Res[i]=j:ijtime_machine[i]:i1、搜索從開始點（根點）DFS搜索整2、每搜索完條time_min和Res[i]序列，開始結(jié)同同也成擴展點擴展點處向縱方向移至新點，并成新活點，也成擴展點。3、如3、如擴展點處不能再向縱方向擴展，則擴展點就成死點?；铧c成擴展點；直至找到或全部部分算法實現(xiàn)boolplacetest(intk){inttime_max_K=time_machine[1];for(inti=2;i<=K;i++){if(time_machine[i]>time_max_K)time_max_K=time_machine[i];}if(time_max_K>time_min)returnfalse;elsereturntrue;}voidBacktrack(intk,intt[],intx[]){if(k>N){inttime_max_K=time_machine[1];for(inti=2;i<=K;i++){if(time_machine[i]>time_max_K)time_max_K=time_machine[i];}if(time_max_K<time_min){time_min=time_max_K;for(inti=1;i<=N;i++)Res[i]=x[i] } }else{for(inti=1;i<=K;i++): {x[k{x[ki;//ki上面if(placetest(k)){time_machine[i]+=t[k];Backtrack(k+1,t,x);time_machine[i]-=t[k];}}運行結(jié)果時間復(fù)雜性分析題目:輸油管道問題題目:輸油管道問題由于沒有使用限界函數(shù)進行優(yōu)化，算法時間和空間復(fù)雜度呈指由于沒有使用限界函數(shù)進行優(yōu)化，算法時間和空間復(fù)雜度呈指數(shù) 級增長。所以該算法不適合較大規(guī)模的計算級增長。所以該算法不適合較大規(guī)模的計算。 藍線表示機器數(shù)一定 M=3時，n增大時求解最佳調(diào)度對所消耗的時 間，該趨勢隨著指數(shù)增加。 四．作業(yè)調(diào)度算法比較 算法這是在只有兩臺設(shè)備情況下的最優(yōu)排序算法，同時說明工件的第一道工序和最后一道工序的加工時間對排序的影響是主要的。貪心算法只需按順序以數(shù)組方式提供各作業(yè)的加工時間和機O(nlogn)。算法解作業(yè)調(diào)度問題兩個問題不同，兩個是求所有作業(yè)在