算法分析與設(shè)計期末

下面程序段的所需要的計算時間為（）。intMaxSum(intn,int*a,int&besti,int&bestj)intMaxSum(intn,int*a,int&besti,int&bestj){ intsum=0; for(inti=1;i<=n;i++){ intthissum=0; for(intj=i;j<=n;j++){ thissum+=a[j]; if(thissum>sum) { sum=thissum; besti=i; bestj=j; } } } returnsum;}有11個待安排的活動，它們具有下表所示的開始時間與結(jié)束時間，如果以貪心算法求解這些活動的最優(yōu)安排（即為活動安排問題：在所給的活動集合中選出最大的相容活動子集合），得到的最大相容活動子集合為活動（{1，4，8，11}）。141413121110987654f[i]122886535031S[i]1110987654321i所謂貪心選擇性質(zhì)是指（所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到）。所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指（問題的最優(yōu)解包含了其子問題的最優(yōu)解）。回溯法是指（具有限界函數(shù)的深度優(yōu)先生成法）。6.用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為（O(h(n))）。7.回溯法的算法框架按照問題的解空間一般分為（子集樹）算法框架與（排列樹）算法框架。8.用回溯法解0/1背包問題時，該問題的解空間結(jié)構(gòu)為（子集樹）結(jié)構(gòu)。9.用回溯法解批處理作業(yè)調(diào)度問題時，該問題的解空間結(jié)構(gòu)為（排列樹）結(jié)構(gòu)。10.用回溯法解0/1背包問題時，計算結(jié)點(diǎn)的上界的函數(shù)如下所示，請在空格中填入合適的內(nèi)容：TypepKnap<Typew,Typep>::TypepKnap<Typew,Typep>::Bound(inti){//計算上界Typewcleft=c-cw;//剩余容量Typepb=cp;//結(jié)點(diǎn)的上界//以物品單位重量價值遞減序裝入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//裝滿背包if(i<=n)（b+=p[i]/w[i]*cleft）;returnb;}11.用回溯法解布線問題時，求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為的方格陣列，擴(kuò)展每個結(jié)點(diǎn)需O(1)的時間，L為最短布線路徑的長度，則算法共耗時(O(mn))，構(gòu)造相應(yīng)的最短距離需要（O(L)）時間。for(inti=0;i<NumOfNbrs;i++){for(inti=0;i<NumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){//該方格未標(biāo)記grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成布線Q.Add(nbr);}}12.用回溯法解圖的m著色問題時，使用下面的函數(shù)OK檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個兒子所相應(yīng)的顏色的可用性，則需耗時（漸進(jìn)時間上限）（O（mn））。BoolColor::OK(intk)BoolColor::OK(intk){//for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}13.旅行售貨員問題的解空間樹是（排列樹）。證明題1.一個分治法將規(guī)模為n的問題分成k個規(guī)模為n／m的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費(fèi)1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有：通過迭代法求得T（n）的顯式表達(dá)式為：試證明T（n）的顯式表達(dá)式的正確性。2.舉反例證明0/1背包問題若使用的算法是按照pi/wi的非遞減次序考慮選擇的物品，即只要正在被考慮的物品裝得進(jìn)就裝入背包，則此方法不一定能得到最優(yōu)解（此題說明0/1背包問題與背包問題的不同）。證明：舉例如：p={7,4,4},w={3,2,2},c=4時，由于7/3最大，若按題目要求的方法，只能取第一個，收益是7。而此實(shí)例的最大的收益應(yīng)該是8，取第2，3個。3.求證：O(f(n))+O(g(n))=O(max{f(n),g(n)})。證明：對于任意f1(n)O(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對所有nn1，有f1(n)c1f(n)。類似地，對于任意g1(n)O(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對所有nn2，有g(shù)1(n)c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對所有的nn3，有f1(n)+g1(n)c1f(n)+c2g(n)c3f(n)+c3g(n)=c3(f(n)+g(n))c32max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).4.求證最優(yōu)裝載問題具有貪心選擇性質(zhì)。（最優(yōu)裝載問題：有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。設(shè)集裝箱已依其重量從小到大排序，(x1,x2,…,xn)是最優(yōu)裝載問題的一個最優(yōu)解。又設(shè)。如果給定的最優(yōu)裝載問題有解，則有。）證明：解答題機(jī)器調(diào)度問題。問題描述：現(xiàn)在有n件任務(wù)和無限多臺的機(jī)器，任務(wù)可以在機(jī)器上得到處理。每件任務(wù)的開始時間為si，完成時間為fi，si<fi。[si，fi]為處理任務(wù)i的時間范圍。兩個任務(wù)i，j重疊指兩個任務(wù)的時間范圍區(qū)間有重疊，而并非指i，j的起點(diǎn)或終點(diǎn)重合。例如：區(qū)間[1，4]與區(qū)間[2，4]重疊，而與[4，7]不重疊。一個可行的任務(wù)分配是指在分配中沒有兩件重疊的任務(wù)分配給同一臺機(jī)器。因此，在可行的分配中每臺機(jī)器在任何時刻最多只處理一個任務(wù)。最優(yōu)分配是指使用的機(jī)器最少的可行分配方案。問題實(shí)例：若任務(wù)占用的時間范圍是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，則按時完成所有任務(wù)最少需要幾臺機(jī)器？（提示：使用貪心算法）畫出工作在對應(yīng)的機(jī)器上的分配情況。2.已知非齊次遞歸方程：，其中，b、c是常數(shù)，g(n)是n的某一個函數(shù)。則f(n)的非遞歸表達(dá)式為：。現(xiàn)有Hanoi塔問題的遞歸方程為：，求h(n)的非遞歸表達(dá)式。解：利用給出的關(guān)系式，此時有：b=2,c=1,g(n)=1,從n遞推到1，有：3.單源最短路徑的求解。問題的描述：給定帶權(quán)有向圖（如下圖所示）G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個頂點(diǎn)，稱為源?，F(xiàn)在要計算從源到所有其它各頂點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。解法：現(xiàn)采用Dijkstra算法計算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。請將此過程填入下表中。4432110030maxint10-{1}初始dist[5]dist[4]dist[3]dist[2]uS迭代4.請寫出用回溯法解裝載問題的函數(shù)。裝載問題：有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且。裝載問題要求確定是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。解：voidbacktrack(inti){//搜索第i層結(jié)點(diǎn)if(i>n)//到達(dá)葉結(jié)點(diǎn)更新最優(yōu)解bestx,bestw;return;r-=w[i];if(cw+w[i]<=c){//搜索左子樹x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}if(cw+r>bestw){x[i]=0;//搜索右子樹backtrack(i+1);}r+=w[i];}5.用分支限界法解裝載問題時，對算法進(jìn)行了一些改進(jìn)，下面的程序段給出了改進(jìn)部分；試說明斜線部分完成什么功能，以及這樣做的原因，即采用這樣的方式，算法在執(zhí)行上有什么不同。////檢查左兒子結(jié)點(diǎn)Typewt=Ew+w[i];//左兒子結(jié)點(diǎn)的重量if(wt<=c){//可行結(jié)點(diǎn)if(wt>bestw)bestw=wt;//加入活結(jié)點(diǎn)隊(duì)列if(i<n)Q.Add(wt);}//檢查右兒子結(jié)點(diǎn)if(Ew+r>bestw&&i<n)Q.Add(Ew);//可能含最優(yōu)解Q.Delete(Ew);//取下一擴(kuò)展結(jié)點(diǎn)解答：斜線標(biāo)識的部分完成的功能為：提前更新bestw值；這樣做可以盡早的進(jìn)行對右子樹的剪枝。具體為：算法Maxloading初始時將bestw設(shè)置為0，直到搜索到第一個葉結(jié)點(diǎn)時才更新bestw。因此在算法搜索到第一個葉子結(jié)點(diǎn)之前，總有bestw=0，r>0故Ew+r>bestw總是成立。也就是說，此時右子樹測試不起作用。為了使上述右子樹測試盡早生效，應(yīng)提早更新bestw。又知算法最終找到的最優(yōu)值是所求問題的子集樹中所有可行結(jié)點(diǎn)相應(yīng)重量的最大值。而結(jié)點(diǎn)所相應(yīng)得重量僅在搜索進(jìn)入左子樹是增加，因此，可以在算法每一次進(jìn)入左子樹時更新bestw的值。7.最長公共子序列問題：給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列Xi和Yj的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：在程序中，b[i][j]記錄C[i][j]的值是由哪一個子問題的解得到的。請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCSLength完成計算最優(yōu)值的功能。voidvoidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}函數(shù)LCS實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列。請?zhí)顚懗绦蛑械目崭?，以使函?shù)LCS完成構(gòu)造最長公共子序列的功能（請將b[i][j]的取值與（1）中您填寫的取值對應(yīng)，否則視為錯誤）。voidvoidLCS(inti，intj，char*x，int**b){if(i==0||j==0)retur