算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告電梯調(diào)度

1、XXXX大學(xué)算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告 院 （系）： 年 級： 姓 名： 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 研究方向： 互聯(lián)網(wǎng)與網(wǎng)絡(luò)技術(shù) 指導(dǎo)教師： X X X X 大 學(xué)目 錄 TOC o 1-3 h z u HYPERLINK l _Toc502322076 題目1 電梯調(diào)度 PAGEREF _Toc502322076 h 1 HYPERLINK l _Toc502322077 1.1 題目描述 PAGEREF _Toc502322077 h 1 HYPERLINK l _Toc502322078 1.2 算法文字描述 PAGEREF _Toc502322078 h 1 HYPERLINK l

2、_Toc502322079 1.3 算法程序流程 PAGEREF _Toc502322079 h 4 HYPERLINK l _Toc502322080 1.4 算法的程序?qū)崿F(xiàn)代碼 PAGEREF _Toc502322080 h 8 HYPERLINK l _Toc502322081 題目2 切割木材 PAGEREF _Toc502322081 h 10 HYPERLINK l _Toc502322082 題目描述 PAGEREF _Toc502322082 h 10 HYPERLINK l _Toc502322083 算法文字描述 PAGEREF _Toc502322083 h 10 HYP

3、ERLINK l _Toc502322084 算法程序流程 PAGEREF _Toc502322084 h 11 HYPERLINK l _Toc502322085 算法的程序?qū)崿F(xiàn)代碼 PAGEREF _Toc502322085 h 15 HYPERLINK l _Toc502322086 題目3 設(shè)計(jì)題 PAGEREF _Toc502322086 h 17 HYPERLINK l _Toc502322087 題目描述 PAGEREF _Toc502322087 h 17 HYPERLINK l _Toc502322088 3.2 輸入要求 PAGEREF _Toc502322088 h 17

4、 HYPERLINK l _Toc502322089 輸出要求 PAGEREF _Toc502322089 h 17 HYPERLINK l _Toc502322090 樣例輸入 PAGEREF _Toc502322090 h 17 HYPERLINK l _Toc502322091 樣例輸出 PAGEREF _Toc502322091 h 17 HYPERLINK l _Toc502322092 測試樣例輸入 PAGEREF _Toc502322092 h 17 HYPERLINK l _Toc502322093 測試樣例輸出 PAGEREF _Toc502322093 h 18 HYPER

5、LINK l _Toc502322094 算法實(shí)現(xiàn)的文字描述 PAGEREF _Toc502322094 h 18 HYPERLINK l _Toc502322095 算法程序流程 PAGEREF _Toc502322095 h 19 HYPERLINK l _Toc502322096 算法的程序?qū)崿F(xiàn)代碼 PAGEREF _Toc502322096 h 20 HYPERLINK l _Toc502322097 算法分析與設(shè)計(jì)課程總結(jié) PAGEREF _Toc502322097 h 23 HYPERLINK l _Toc502322098 參考文獻(xiàn) PAGEREF _Toc502322098 h

6、 24題目1 電梯調(diào)度1.1 題目描述一棟高達(dá)31層的寫字樓只有一部電梯，其中電梯每走一層需花費(fèi)4秒，并且在每一層樓?？康臅r(shí)間為10秒，乘客上下一樓需要20秒，在此求解最后一位乘客到達(dá)目的樓層的最短時(shí)間以及具體的?？坑?jì)劃。例如：此刻電梯?？啃枨鬄? 5 10（有三位乘客，他們分別想去4樓、5樓和10樓），如果在每一層樓都停靠則三位乘客到達(dá)辦公室所需要的時(shí)間為3*4=12秒、4*4+10=26秒、4*9+2*10=56秒，則最后一位乘客到達(dá)辦公室的時(shí)間為56秒，相應(yīng)的?？坑?jì)劃為4 5 10均停靠。對于此測試用例電梯?？坑?jì)劃方案：4 10，這樣到第4樓的乘客所需時(shí)間為3*4=12秒，到第5樓的乘客

7、所需時(shí)間為3*4+20=32秒，到第10樓的乘客所需時(shí)間為9*4+10=46秒，即最后到達(dá)目的樓層的顧客所需時(shí)間為46秒。輸入要求：輸入的第1行為整數(shù)n f1 f2 fn，其中n表示有n層樓需要?？浚琻=0表示沒有更多的測試用例，程序終止運(yùn)行。f1 f2 fn表示需要停靠的樓層（n=30，2=f1f2fn=31），每一個(gè)數(shù)字都用一個(gè)空格隔開。輸出要求：對于每一個(gè)測試用例，第1行輸出最后一位乘客到達(dá)目的樓層所需時(shí)間，第2行輸出?？看螖?shù)和相應(yīng)的?？糠桨?，每一個(gè)數(shù)字用一個(gè)空格隔開。1.2 算法文字描述程序?qū)崿F(xiàn)的算法思想，將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到遠(yuǎn)問題的解

8、。與分治法不同的是，適合用動態(tài)規(guī)劃發(fā)求解的子問題往往不是相互獨(dú)立。若用分治法求解這類問題，則分解的子問題數(shù)目太多，以至于最后解決原問題需要耗費(fèi)指數(shù)時(shí)間。然而，不同子問題的數(shù)目常常是多項(xiàng)式量級。在分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。如果能夠保存已解決的子問題的答案，而在需要時(shí)在找出以求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。為了達(dá)到這個(gè)目的，可以采用一個(gè)表來記錄所有已解決的子問題的答案。不管子問題以后是否被使用，只要他被計(jì)算過，就將其結(jié)果填入表中。動態(tài)規(guī)劃算法適合求解最優(yōu)化問題，設(shè)計(jì)動態(tài)規(guī)劃算法的具體步驟如下： eq oac(,1)找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)； eq

9、 oac(,2)遞歸地定義最優(yōu)值； eq oac(,3)以自底向上的方式計(jì)算最優(yōu)值； eq oac(,4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。例如：給定金額n以及1，2,5分硬幣，求找n的最少硬幣數(shù)。對于大于1分的找零理所當(dāng)然可以找零1分，大于2分和5分的找零與此類似，那么找零時(shí)就有三種選擇，即找零后剩余金額為n-1，n-2，n-5，這三種選擇總的找零數(shù)最少的方案即為所求解的方案。顯然，最終的找零方案與執(zhí)行當(dāng)前選擇后剩余的金額的找零相關(guān)，即金額n的最優(yōu)找零方案包含了金額n-1，n-2，n-5的最優(yōu)找零方案，于是可得如下狀態(tài)轉(zhuǎn)移方程：Fn=minFn-1+1Fn-2+1Fn-5+1具體的求解

10、過程：初始化F(1)=1,F(2),F(5)=1F(1)1F(2)1F(3)minF(2)+1,F(1)+1=2F(4)minF(2)+1,F(3)+1=2F(5)1F(6)minF(1)+1,F(4)+1,F(1)+1=2F(n)minF(n-1)+1,F(n-2)+1,F(n-5)+1算法設(shè)計(jì)思路及求解過程思路：題目所描述的整個(gè)過程是“并行的”，而且所有人到達(dá)各自樓層的用時(shí)只與最晚到達(dá)的人有關(guān)。由于去各個(gè)樓層的具體數(shù)目對結(jié)果沒有影響，所以可以將“電梯還剩i個(gè)人”表述成“電梯里面的乘客還要去i個(gè)樓層”。電梯從第1層開始向上運(yùn)行，任意時(shí)刻的狀態(tài)都可以由“電梯當(dāng)前所處樓層”和“電梯里面都有哪些乘

11、客確定”，初始狀態(tài)為“電梯在1樓”和“所有乘客都在電梯上”。在電梯運(yùn)行的每一個(gè)階段都需要作出相應(yīng)的決策，哪些乘客乘坐電梯到目的層，哪些乘客選擇爬樓梯到達(dá)目的地。決策后，電梯里面的乘客被分成兩部分：乘客留在電梯里面繼續(xù)上升；乘客離開電梯走樓梯到達(dá)。求當(dāng)前狀態(tài)下電梯里面的乘客所有人到達(dá)目的所需要的最短時(shí)間，只需要找到一個(gè)最優(yōu)決策，使得下電梯的乘客和留在電梯中的乘客最晚到達(dá)時(shí)間越短越好，這個(gè)最短時(shí)間就是當(dāng)前狀態(tài)下的最優(yōu)解。如果假設(shè)決策后留在電梯里面的乘客到達(dá)各自樓層所需要的時(shí)間為T1，離開電梯的各自到達(dá)目的地所需時(shí)間為T2，則minmax(T1,T2)就是當(dāng)前狀態(tài)的最優(yōu)解，其中T1可以由“當(dāng)前層數(shù)+

12、1”和“決策后剩下的人”確定的狀態(tài)得到；T2則為下電梯走樓梯到達(dá)目的走樓梯最多的那一位乘客所花時(shí)間。如果去第k層的乘客選擇在當(dāng)前樓層下電梯，那么第1，2k-1層的乘客也應(yīng)該選擇在此時(shí)下電梯（如 REF _Ref502258057 h 圖 1所示），這樣就可以得到當(dāng)前決策下的一個(gè)最優(yōu)解。為了進(jìn)一步處理停靠請求，對樓層按從高到低進(jìn)行排序，并以此進(jìn)行編號，如此可以避免在求解過層中處理不連續(xù)的請求，如：圖 SEQ 圖 * ARABIC 1 解題結(jié)論1無論電梯當(dāng)前位于何處2nk3第k樓的乘客選擇在此下電梯k-1k層以下的乘客此刻都應(yīng)離開電梯4，5，10。使用i,j兩個(gè)參數(shù)表示電梯當(dāng)前的狀態(tài)，即電梯在第i

13、層，電梯中有j位乘客。綜上所述，可得如下狀態(tài)轉(zhuǎn)移方程：fi,j=minmaxt1,t2t1=fi+1,k+tEle+tStop 0kjt2=maxfl-i*tPeo k+1ljf(i,j)表示電梯在第i層樓時(shí)，電梯中j個(gè)人都到達(dá)目的地所需要的最短時(shí)間。具體求解過程：第一步：計(jì)算初始狀態(tài)f(topFloor,1),f(topFloor,2),f(topFloor,n);第二步：根據(jù)狀態(tài)轉(zhuǎn)移方程計(jì)算f(i,j);第三步：根據(jù)計(jì)算最優(yōu)值時(shí)記錄的信息求解最優(yōu)解。1.3 算法程序流程圖 SEQ 圖 * ARABIC 2 Input函數(shù)流程圖圖 SEQ 圖 * ARABIC 3 solve函數(shù)流程圖圖 S

14、EQ 圖 * ARABIC 4 main函數(shù)流程圖圖 SEQ 圖 * ARABIC 5 calculate函數(shù)流程圖圖 SEQ 圖 * ARABIC 6 tStay函數(shù)流程圖圖 SEQ 圖 * ARABIC 7 tLeave函數(shù)流程圖1.4 算法的程序?qū)崿F(xiàn)代碼# include# include# include#include# include#includeusing namespace std;const int maxN=30,maxF=31;/ 電梯上一層樓所需時(shí)間，電梯每次?？繒r(shí)長，人走一層樓所需時(shí)間const int ve=4,st=10,vw=20;int n,fmaxN+1;

15、/數(shù)據(jù)讀取bool input() cinn; if(n=0) return false; / 注意：f1.n中樓層數(shù)從高到低排列 for(int i=n;i=1;i-) cinfi; return true;int dpmaxF+1maxN+1,nextJmaxF+1maxN+1;/ 目前電梯在第currF層, 第L層到第R層乘客離開電梯/ 函數(shù)返回這些離開電梯的乘客中最晚到達(dá)目的層所需時(shí)間int tLeave(int currF,int l,int r) if(lr) return 0; / 僅需考慮兩端, 無論此刻電梯在何處, 第l-r層花時(shí)間最多的 / 一定是離電梯當(dāng)前所在樓層最遠(yuǎn)的乘

16、客 return max(abs(currF-fl),abs(currF-fr)*vw;/ 現(xiàn)在電梯在第i層, 電梯里面本來有j位乘客, 離開電梯的乘客剩下jj位int tStay(int i,int j,int jj) / 沒有乘客離開,電梯不停 if(j=jj | i=1) return dpi+1jj +ve; / 所有人都離開電梯 else if(jj=0) return 0; / 一般情況，電梯在第i層?？?else return dpi+1jj+ve+st;/void calculate() / 邊界：電梯在頂樓時(shí)所有人都必須下電梯 int topFloor=f1; for(int

17、 j=1;j=1;i-) / i表示電梯此刻所在位置 for(int j=1;j=n;j+) dpij=numeric_limits:max(); for(int jj=0;jjtmp) dpij=tmp; / jj以前的乘客均離開電梯 nextJij=jj; coutdp1nendl;/ 重構(gòu)最優(yōu)解void rebuildSolution() vector stops; int j=nextJ1n,topFloor=f1; for(int i=2;i=topFloor;i+) if(nextJij!=j) stops.push_back(i); j=nextJij; if(j=0) brea

18、k; coutstops.size(); for(int i=0;istops.size();i+) cout stopsi; coutendl;void solve() memset(dp,0,sizeof(dp); memset(nextJ,0,sizeof(nextJ); calculate(); rebuildSolution();題目2 切割木材2.1題目描述一個(gè)木匠從木材公司買了一批木材，每塊木材的長度均相同，但由于制作家具時(shí)所需的木塊長度各不相同，因此需要把這些木材切割成長度不同的木塊。同時(shí)每次切割時(shí)由于鋸子本身有一定的寬度，因此每切割一次就會浪費(fèi)掉一些木料。請?jiān)O(shè)計(jì)一個(gè)程序使木匠

19、能夠用最少的木材切割出所需的木塊。輸入描述：輸入有若干個(gè)測試樣例，每個(gè)測試樣例占一行。每行由若干個(gè)整數(shù)構(gòu)成，第一個(gè)整數(shù)為所購買的木塊的長度L（0L=30000）,第二個(gè)整數(shù)為鋸子的寬度W（0W=1000）,其后的若干個(gè)整數(shù)分別表示制作家具時(shí)需要的木塊的長度。輸出描述： 每個(gè)測試樣例輸出一行，為一個(gè)整數(shù)N，表示制作家具時(shí)需要購買的木塊的數(shù)量。樣例輸入：1000 100 250 250 500 650 10001000 50 200 250 250 500 650 970樣例輸出：34算法文字描述此題目是裝載問題的一個(gè)變種，與裝載問題不同的是此問題沒有給出“船”數(shù)量，但是給出了船的載重量，因此仍舊

20、可以借鑒解裝載問題的思路，即讓每一根原材料可以切出更多符合要求的木料，類似于裝載問題中“將第一艘輪船盡可能地裝滿”，即保證切割以后剩余的原材料是最少的。算法具體描述如下：Step 1：聲明求解結(jié)果變量res=0，剩余未切割木料數(shù)量count=n，當(dāng)前已切割木料長度和cw=0，目前最大切割長度bestW=0，求解標(biāo)記數(shù)組visitedn，當(dāng)前最優(yōu)求解數(shù)組nVisitedn，問題求解狀態(tài)記錄數(shù)組res_arrn，鋸口寬度sw；Step 2：當(dāng)剩余未切割木料數(shù)量count大于0時(shí)，利用回溯法進(jìn)行最大子集和求解。當(dāng)in-1時(shí)，搜索左子樹的條件：當(dāng)前節(jié)點(diǎn)未被訪問且cw+datain-1時(shí)，獲得一種切割方

21、案，若此次求解結(jié)果優(yōu)于已得求解結(jié)果，即bestWcw，使用nVisited數(shù)組記錄當(dāng)前求解狀態(tài)，同時(shí)更新bestW的值；Step 4：利用回溯法完成1次木料切割后，更當(dāng)前問題求解狀態(tài)res_arr數(shù)組，根據(jù)最新的求解狀態(tài)更新未切割木料數(shù)量count，同時(shí)res+，若count=0則求解結(jié)束，否則重復(fù)2,3,4直至count=0。算法程序流程圖 SEQ 圖 * ARABIC 8 main函數(shù)流程圖圖 SEQ 圖 * ARABIC 9 input函數(shù)流程圖圖 SEQ 圖 * ARABIC 10 solve函數(shù)流程圖圖 SEQ 圖 * ARABIC 11 backtrack函數(shù)流程圖算法的程序?qū)崿F(xiàn)代

22、碼# include# include# include# define MAX_SAMPLE_LENGTH 50/*回溯法求解*/int* in=(int *)malloc(MAX_SAMPLE_LENGTH*sizeof(int);int* data=(int *)malloc(MAX_SAMPLE_LENGTH*sizeof(int);bool* visited=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof(bool);bool* nVisited=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof(bool);bool* r

23、es_arr=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof(bool);int w; / 原材料長度 int n; / 數(shù)據(jù)元素個(gè)數(shù) int sw; / 鋸口寬度 int cw; / 當(dāng)前已鋸木頭長度和 int res; / 求解結(jié)果 int bestW; / 當(dāng)前求解最大值 bool input() bool flag=true; /初始化數(shù)據(jù)保存數(shù)組 memset(in,0,MAX_SAMPLE_LENGTH*sizeof(int); memset(visited,false,MAX_SAMPLE_LENGTH*sizeof(bool); memset(r

24、es_arr,false,MAX_SAMPLE_LENGTH*sizeof(bool); memset(nVisited,false,MAX_SAMPLE_LENGTH*sizeof(bool); / 記錄輸入數(shù)據(jù)個(gè)數(shù) n=0; / 讀取數(shù)據(jù)-原材料(木頭)長度 scanf(%d,&w); if(0=w) flag=false; / 鋸口寬度 scanf(%d,&sw); while(flag) scanf(%d,data+n); n+; char ch=getchar(); if(ch=n) break; return flag;void backtrack(int i,int k) if(

25、in-1) if(bestWcw) / 記錄最優(yōu)值 bestW=cw; / 記錄當(dāng)前最優(yōu)解 for(int i=0;in;i+) nVisitedi=visitedi; return ; / 進(jìn)入右子樹條件 if(!res_arri&cw+datai+k*sw0) / 初始化,cw當(dāng)前已鋸木頭長度和, / count剩余未鋸木頭數(shù)量,bestW本次求解最大長度和 cw=0,count=0,bestW=0; backtrack(0,0); for(int i=0;i(2,1)-(3,1)-(4,2)-(5,3)7119 812 10 74 15 23 1917 8 21 12 1632 25 2

26、4 28 31 278 5 9 10 11 13 153.7測試樣例輸出113(1,1)-(2,1)-(3,2)-(4,3)-(5,3)-(6,4)-(7,5)3.8算法實(shí)現(xiàn)的文字描述動態(tài)規(guī)劃采用自底向上逐層分階段決策第1次決策，針對第4層如果最優(yōu)路徑經(jīng)過6，則從第4層到第5層應(yīng)該經(jīng)過12，則第4+第5層的最大路徑為6+12=18如果最優(yōu)路徑經(jīng)過14，則從第4層到第5層應(yīng)該經(jīng)過13，則第4+第5層的最大路徑為13+14=27這樣實(shí)際上將5階數(shù)塔變?yōu)?階數(shù)塔問題了。逐層向上遞推，最后得到問題的最優(yōu)解根據(jù)題意，待處理的數(shù)據(jù)規(guī)模同數(shù)塔的層數(shù)有關(guān)，同時(shí)數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)與層數(shù)相同，所以可以使用二維數(shù)組da

27、ta存儲待處理節(jié)點(diǎn)數(shù)值，只有一半的節(jié)點(diǎn)有數(shù)值，實(shí)際上是一個(gè)下三角矩陣。可以較為容易地得到問題狀態(tài)轉(zhuǎn)移方程：di,j=datai,j i=ndi,j=maxdi+1,j,di+1,j+1+datai,j 1inStep 1：聲明變量數(shù)塔層數(shù)n，待處理數(shù)據(jù)節(jié)點(diǎn)數(shù)值數(shù)組datann,結(jié)果（狀態(tài)）數(shù)組dnn;Step 2：輸入數(shù)塔層數(shù)n，維數(shù)組data和d分配內(nèi)存空間；Step 3：初始化第n層結(jié)果（狀態(tài)）數(shù)組值；Step 4：根據(jù)狀態(tài)轉(zhuǎn)移方程求解d(i,j)，其中i從n-1到1，j從1到i；Step 5：輸出d(1,1)；Step 6：根據(jù)數(shù)組d求解具體路徑并輸出。3.9算法程序流程圖 SEQ 圖 * ARABIC 13 main函數(shù)流程圖圖 SEQ 圖 * ARABIC 14 tower_walk函數(shù)流程圖#include#include#include#includeusing namespace std;int* data=NULL;/存儲數(shù)塔原始數(shù)據(jù)int* dp=NULL;/狀態(tài)值記錄 int n;/塔的層數(shù)/*動態(tài)規(guī)劃實(shí)現(xiàn)數(shù)塔求解*/void tower_walk() int index1=0,index2=0; / dp初始化 for