算法分析與設(shè)計作業(yè)參考答案

1、算法分析與設(shè)計作業(yè)參考答案作業(yè)一一、名詞解釋：1 .遞歸算法：直接或間接地調(diào)用自身的算法稱為遞歸算法。2 .程序：程序是算法用某種程序設(shè)計語言的具體實現(xiàn)。二、簡答題：1 .算法需要滿足哪些性質(zhì)？簡述之。算法是若干指令的有窮序列，滿足性質(zhì)：1）輸入：有零個或多個外部量作為算法的輸入。2）輸出：算法產(chǎn)生至少一個量作為輸出。3）確定性：組成算法的每條指令清晰、無歧義。4）有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限。2 .簡要分析分治法能解決的問題具有的特征。分析分治法能解決的問題主要具有如下特征：1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；2）該問題可以分解為若干個規(guī)模較小

2、的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；3）利用該問題分解出的子問題的解可以合并為該問題的解；4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。3 .簡要分析在遞歸算法中消除遞歸調(diào)用，將遞歸算法轉(zhuǎn)化為非遞歸算法的方法。將遞歸算法轉(zhuǎn)化為非遞歸算法的方法主要有：1）采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2）用遞推來實現(xiàn)遞歸函數(shù)。3）通過Cooper變換、反演變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限。三、算法編寫及算法

3、應(yīng)用分析題:1 .冒泡排序算法的基本運算如下:fori-1ton-1doforj-1ton-idoifaj<aj+1then交換aj、aj+1;分析該算法的時間復(fù)雜性。解答：排序算法的基本運算步為元素比較，冒泡排序算法的時間復(fù)雜性就是求比較次數(shù)與n的關(guān)系。1）設(shè)比較一次花時間1;(n i)i)殳n 1)2）內(nèi)循環(huán)次數(shù)為：n-i次，（i=1,n）,花時間為：1nj13）外循環(huán)次數(shù)為：n-1,花時間為：T（n）（n2 .設(shè)計一個分治算法計算一棵二叉樹的高度。i1解答：算法思想：對于二叉樹T,若為空樹，則其高度為0;否則，分別求其左子樹和右子樹的高度，最大者加1即為樹T勺高度。其描述如下：in

4、tBTLength（BTT）/為了便于描述，假定二叉樹類型為BT。T的左子樹為T.lchild,右子樹為T.rchildif(T=NULL)return0;/T為空樹returnmax(BTLength(T.lchild),BTLength(T.rchild)+13 .設(shè)計一個分治算法來判定給定的兩棵二叉樹T1和T2是否相同。解答：算法思想：對于兩棵二叉樹T1和T2,若其根結(jié)點值相同，且其左右子樹分別對應(yīng)相同，則T1=T2;否則T1WT2。其描述如下：booleanBTEQUAL(BTT1，BTT2)/為了便于描述，假定二叉樹類型為BT。二叉樹T的左子樹為T.Ichild,右子樹為T.rchi

5、ld。二叉樹T的根結(jié)點值T.data。if(T1=NULL&&T2=NULL)returnTrue;/均為空樹if(T1&&T2&&T1.data=T2.data&&BTEQUALT(1.lchild,T2.lchild)&&BTEQUAL(T1.rchild,T2.rchild)returnTrue;returnFalse;4 .給出一個分治算法來找出n個元素的序列中的第2大元素，并分析算法的時間復(fù)雜度。解答：算法思想：當(dāng)序列A1.n中元素的個數(shù)n=2時，通過直接比較即可找出序列的第2大元素。當(dāng)n>2時，先

6、求出序列A1.n-1中的第1大元素x1和第2大元素x2；然后，通過2次比較即可在三個元素x1x2和An中找出第2大元素，該元素即為A1.n中的第2大元素。算法描述如下：SecondElement(Alow.high,max1,max2)/假設(shè)主程序中調(diào)用該過程條件為high-low>=2if(hight-low=2)if(Alow<Ahight)max2=Alow;max1=Ahigh;elsemax2=Ahigh;max1=Alow;elseSecondElement(Alow.high,x1,x2);if(x1<=An)max2=max1;max1=An;elseif(x

7、2>=An)max2=x2;max1=x1;elsemax2=An;max1=x1;該算法的時間復(fù)雜度滿足如下遞歸方程：T(n)=T(n-1)+2；T(2)=1。解得T(n)=2n-3。作業(yè)二一、名詞解釋：1、MST性質(zhì)：G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)巳且uU,vV-U,且在所有這樣的邊中，(u,v)的權(quán)cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質(zhì)稱為MST性質(zhì)。2、子問題的重疊性質(zhì)：遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次，這種性質(zhì)稱為子問題的重疊性質(zhì)。二、簡答題：1、簡述動態(tài)規(guī)劃算法求

8、解的基本要素。動態(tài)規(guī)劃算法求解的基本要素包括：1)最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提；2)動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果，即重疊子問題。2、備忘錄方法和動態(tài)規(guī)劃算法相比有何異同？簡述之。備忘錄方法是動態(tài)規(guī)劃算法的變形。與動態(tài)規(guī)劃算法一樣，備忘錄方法用表格保存已解決的子問題的答案，在下次需要解此問題時，只要簡單地查看該子問題的解答，而不必重新計算。備忘錄方法與動態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂向下的，而動態(tài)規(guī)劃算法則是自底向上遞歸的。因此，備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)

9、相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同的子問題的重復(fù)求解，而直接遞歸方法沒有此功能。3、貪心算法求解的問題主要具有哪些性質(zhì)？簡述之。貪心算法求解的問題一般具有二個重要的性質(zhì)：一是貪心選擇性質(zhì)，這是貪心算法可行的第一個基本要素；另一個是最優(yōu)子結(jié)構(gòu)性質(zhì)，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法求解的關(guān)鍵特征。三、算法編寫及算法應(yīng)用分析題：1、設(shè)計求解如下最大子段和問題的動態(tài)規(guī)劃算法。只需給出其遞推計算公式即可。最大子段和問題：給定由n個整數(shù)(可能為負(fù)整數(shù))組成的序列a1a2an,求該序列形如2i<k<jak的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)

10、時定義其最大子段和為0。依次定義，所求的最優(yōu)值為max0,maxiwiwjwnNiwkwjak。解答：下面給出求解該問題的動態(tài)規(guī)劃算法中的遞推計算公式。記b(j)=max1<i<j2i<k<jak,iwjwn,則所求最大子段和為maxiwjwnb(j)。而計算bj的遞推計算公式為：b(0)=0，b(j)=maxb(j-1)+aj,aj,iwjwn。該算法的時間復(fù)雜度為O(n);空間復(fù)雜度為O(n)。2、關(guān)于多段圖問題。設(shè)G=(V,E)是一個賦權(quán)有向圖，其頂點集V被劃分成k>2個不相交的子集Vi：1ik,其中，Vi和Vk分別只有一個頂點s(稱為源)和一個頂點t(稱為

11、匯)，圖中所有的邊(u,v),uVi,vMi。求由s到t的最小成本路徑。a) 給出使用動態(tài)規(guī)劃算法求解多段圖問題的基本思想。b) 使用上述方法求解如下多段圖問題。V1V2V3V4V57,7 29,67,1024,126 : 9516,2/3彳 3s 17318,8115,101142,12 41,122 12 t111解：(1)基本思想：設(shè)P(i,j)是從Vi中的節(jié)點j到匯點t的最小成本路徑，Cost(i,j)是其成本。則C0st0Amimc(j,h)+C0st(i+1,h)|hVi+1,(j,h)E。邊界條件是(1)若八工,則cost(h,t)=0；(2)cost(k-1,j)=c(j,t)

12、°(2)求解過程可以表示為:V1V2V3V4V5其中每個節(jié)點標(biāo)示的序偶(p,q)中，p表示節(jié)點到t的成本，q表示后繼節(jié)點的編號。從而，最優(yōu)路徑為:1271012和1361012,成本為16。3、最優(yōu)二元歸并問題：已知將兩個分別包含a個和b個記錄的已分類文件歸并在一起得到一個分類文件需作a+b次記錄移動?，F(xiàn)有n個已分類文件F1,F1,?,Fn,它們的記錄個數(shù)分別為l1,l2,?,ln?，F(xiàn)在考慮使用二元歸并模式將這n個文件歸并成一個分類文件，要求記錄移動次數(shù)最少。設(shè)計一個貪心算法來求解一種最優(yōu)的二元歸并(即記錄移動次數(shù)最少的二元歸并)。解答：(1)貪心準(zhǔn)則：依次將文件序列中記錄最少的兩個

13、文件進(jìn)行歸并成一個文件，直到文件序列中只剩下一個文件為止。(2)貪心算法：AlgorithmBINARYTREE輸入：n個單結(jié)點二元樹列表L,這些棵樹的根結(jié)點的權(quán)分別為l1,l2,?,lno輸出：一棵最優(yōu)二元歸并樹LBeginFori-1Ton-1DoGETNODE(T)/該過程產(chǎn)生一個新結(jié)點TLCHILD(T)-LEAST(L)將表L中其根權(quán)最小的樹取出并作為T的左孩子RCHILD(T)-LEAST(L)將表L中其根權(quán)最小的樹取出并作為T的右孩子WEIGHT(T)-WEIGHT(LCHILD(T)+WEIGHT(RCHILD(T)RepeatReturn(L)End.4、帶限期的作業(yè)調(diào)度問題

14、：n個作業(yè)需要在一臺機器上處理，每個作業(yè)可在單位時間內(nèi)完成。每個作業(yè)i都有一個截止期限di>0(di為整數(shù))，當(dāng)且僅當(dāng)作業(yè)i在它的截止期限之前被完成，獲得pi>0的效益。一種可行的調(diào)度方案為n個作業(yè)的一個子集J，其中J中的每個作業(yè)都能在各自的截止期限內(nèi)完成。該可行調(diào)度方案的效益是J中作業(yè)的效益之和。試設(shè)計貪心算法求效益最大的可行調(diào)度方案(即最優(yōu)調(diào)度方案)。解答：(1)貪心準(zhǔn)則：從J=開始，不斷添加作業(yè)到J中。每次加入J的作業(yè)是保證J是可行的前提下使得J中效益達(dá)到最大。即，按照pi由大到小的次序來考慮作業(yè)。(2)貪心算法：AlgorithmJOBSCHEDULE輸入：n個作業(yè)的截至期

15、限d1,d2,?,dn和相應(yīng)的效益值p1,p2,?,pn。輸出：效益最大可行調(diào)度方案J(作業(yè)子集)Begin將作業(yè)按照效益值排序使得p1>p2>?>pn,相應(yīng)的截至期限為d1,d2,?,dn。J=1Fori2TonDoIf(JUi中所有作業(yè)都能在它們的截至期限內(nèi)完成)ThenJJUiEndifRepeatEnd.作業(yè)三一、名詞解釋：1. 多機調(diào)度問題：多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。同時約定每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。2. 優(yōu)先隊列式分支限界法：優(yōu)先

16、隊列式分支限界法是將活結(jié)點表組織成一個優(yōu)先隊列，按照優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當(dāng)前擴展結(jié)點。在優(yōu)先隊列式分支限界法中，一旦有一個葉結(jié)點成為當(dāng)前擴展結(jié)點，則可以斷言該葉結(jié)點所相應(yīng)的解即為最優(yōu)解。二、簡答題：1. 簡述回溯法的基本思想。回溯法的基本做法是搜索，在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。2. 簡要分析分支限界法與回溯法的異同。1)求解目標(biāo)：回溯法的求解目標(biāo)是找出解

17、空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。2)搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。3. 常見的分支限界法有哪些？簡述之。常見的兩種分支限界法：1)隊列式(FIFO)分支限界法：將活結(jié)點表組織成一個隊列，并按照隊列的先進(jìn)先出(FIFO)原則選取下一個結(jié)點為擴展結(jié)點；2)優(yōu)先隊列式分支限界法：將活結(jié)點表組織成一個優(yōu)先隊列，按照優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當(dāng)前擴展結(jié)點。在優(yōu)先隊列式分支限界法中，一旦有一個葉結(jié)

18、點成為當(dāng)前擴展結(jié)點，則可以斷言該葉結(jié)點所相應(yīng)的解即為最優(yōu)解。、算法編寫及算法應(yīng)用分析題：1.分派問題一般陳述如下：給n個人分派n件工作，把工作j分派給第i個人的代價是COST(,j)(非負(fù)實數(shù))。要求設(shè)計一個回溯算法，在給每個人分派一件不同工作的前提下使得總代價最小。按照回溯法求解問題的基本步驟，請你完成幾個任務(wù)：給出解的一般形式，寫出解空間。以n=4為例畫出表示解空間的狀態(tài)空間樹。并指出樹中哪些結(jié)點是解結(jié)點？提出一個在深度優(yōu)先搜索狀態(tài)空間樹時用于剪枝的剪枝函數(shù)(用文字描述)。解答：解的形式：(x1,x2,?,xn),其中xi=1,2,?,n表示給第i個人安排的工作號。解空間為(x1,x2,?

19、,xn)|xi=1,2,?,n,1wiwn。n=4的狀態(tài)空間樹為高度為4的滿4叉樹。圖<略>。圖中葉結(jié)點是解結(jié)點。剪枝操作有二。一是基于約束條件的剪枝操作：若當(dāng)前給第i個人分配的工作號已被分配，則剪枝。另一個是基于目標(biāo)值的剪枝操作：若當(dāng)前給第i個人分配的工作號未被分配，但是目前已分配的總成本大于或者等于已有的某個分配方案的成本則剪枝。2.設(shè)計一個回溯算法來求解k-著色問題：給定無向圖G=<V,E>,要求使用k種顏色來給圖中每個結(jié)點著色(每個結(jié)點使用k種顏色之一)，使得沒有兩個相鄰的結(jié)點顏色相同。給出解向量的形式，并畫出當(dāng)n=3,k=3時的搜索樹。給出剪枝操作。最壞情況下

20、你的算法在搜索樹上會生成多少個結(jié)點？分析算法的時間復(fù)雜度。解答：解向量的形式為(x1,x2,?,xn),其中xi=1,2,3表示圖中第i個結(jié)點所著的顏色(iwiwn)。當(dāng)n=3,k=3時搜索樹為高度為3的滿3叉樹。剪枝操作如下：當(dāng)搜索到結(jié)點X=(x1,x2,?,xi)時，如果圖中第i結(jié)點所著色xi與前1,2,?,i-1結(jié)點所作的顏色無沖突，即圖中這些結(jié)點中與結(jié)點i有邊相連的結(jié)點所著顏色都不是xi,則不剪枝，否則剪枝(即搜索跳過對子樹X的搜索)。該算法的最壞時間復(fù)雜度是與搜索樹中結(jié)點個數(shù)和在每個結(jié)點處花費的時間都有關(guān)。搜索樹中結(jié)點個數(shù)為O(kn),而在搜索中每個結(jié)點處花費的時間為O(n),因此最

21、壞時間復(fù)雜度是O(nkn)。3.對于下圖使用Dijkstra算法求由頂點a到其他各個頂點的最短路徑。并給出求各個頂點對之間的最短路徑的算法思想。解：用Vi表示已經(jīng)找到最短路徑的頂點，V2表示與Vi中某個頂點相鄰接且不在Vi中的頂點；Ei表示加入到最短路徑中的邊，E2為與Vi中的頂點相鄰接且距離最短的路徑。步驟V1V2E1E21.abab2.a,bdabbd3.a,b,dc,fab,bddc,df4.a,b,d,cfab,bddf5.a,b,c,d,feab,bd,dc,dffe6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,ghab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,hab,bd,de,df