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

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

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

3、應(yīng)用分析題:1 .冒泡排序算法的基本運(yùn)算如下:fori-1ton-1doforj-1ton-idoifaj<aj+1then交換aj、aj+1;分析該算法的時(shí)間復(fù)雜性。解答：排序算法的基本運(yùn)算步為元素比較，冒泡排序算法的時(shí)間復(fù)雜性就是求比較次數(shù)與n的關(guān)系。1）設(shè)比較一次花時(shí)間1;(n i)i)殳n 1)2）內(nèi)循環(huán)次數(shù)為：n-i次，（i=1,n）,花時(shí)間為：1nj13）外循環(huán)次數(shù)為：n-1,花時(shí)間為：T（n）（n2 .設(shè)計(jì)一個(gè)分治算法計(jì)算一棵二叉樹的高度。i1解答：算法思想：對(duì)于二叉樹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è)計(jì)一個(gè)分治算法來判定給定的兩棵二叉樹T1和T2是否相同。解答：算法思想：對(duì)于兩棵二叉樹T1和T2,若其根結(jié)點(diǎn)值相同，且其左右子樹分別對(duì)應(yīng)相同，則T1=T2;否則T1WT2。其描述如下：booleanBTEQUAL(BTT1，BTT2)/為了便于描述，假定二叉樹類型為BT。二叉樹T的左子樹為T.Ichild,右子樹為T.rchi

5、ld。二叉樹T的根結(jié)點(diǎn)值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 .給出一個(gè)分治算法來找出n個(gè)元素的序列中的第2大元素，并分析算法的時(shí)間復(fù)雜度。解答：算法思想：當(dāng)序列A1.n中元素的個(gè)數(shù)n=2時(shí)，通過直接比較即可找出序列的第2大元素。當(dāng)n>2時(shí)，先

6、求出序列A1.n-1中的第1大元素x1和第2大元素x2；然后，通過2次比較即可在三個(gè)元素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;該算法的時(shí)間復(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)為其中一條邊。這個(gè)性質(zhì)稱為MST性質(zhì)。2、子問題的重疊性質(zhì)：遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次，這種性質(zhì)稱為子問題的重疊性質(zhì)。二、簡(jiǎn)答題：1、簡(jiǎn)述動(dòng)態(tài)規(guī)劃算法求

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

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

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

11、匯)，圖中所有的邊(u,v),uVi,vMi。求由s到t的最小成本路徑。a) 給出使用動(dòng)態(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é)點(diǎn)j到匯點(diǎn)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其中每個(gè)節(jié)點(diǎn)標(biāo)示的序偶(p,q)中，p表示節(jié)點(diǎn)到t的成本，q表示后繼節(jié)點(diǎn)的編號(hào)。從而，最優(yōu)路徑為:1271012和1361012,成本為16。3、最優(yōu)二元?dú)w并問題：已知將兩個(gè)分別包含a個(gè)和b個(gè)記錄的已分類文件歸并在一起得到一個(gè)分類文件需作a+b次記錄移動(dòng)?，F(xiàn)有n個(gè)已分類文件F1,F1,?,Fn,它們的記錄個(gè)數(shù)分別為l1,l2,?,ln?，F(xiàn)在考慮使用二元?dú)w并模式將這n個(gè)文件歸并成一個(gè)分類文件，要求記錄移動(dòng)次數(shù)最少。設(shè)計(jì)一個(gè)貪心算法來求解一種最優(yōu)的二元?dú)w并(即記錄移動(dòng)次數(shù)最少的二元?dú)w并)。解答：(1)貪心準(zhǔn)則：依次將文件序列中記錄最少的兩個(gè)

13、文件進(jìn)行歸并成一個(gè)文件，直到文件序列中只剩下一個(gè)文件為止。(2)貪心算法：AlgorithmBINARYTREE輸入：n個(gè)單結(jié)點(diǎn)二元樹列表L,這些棵樹的根結(jié)點(diǎn)的權(quán)分別為l1,l2,?,lno輸出：一棵最優(yōu)二元?dú)w并樹LBeginFori-1Ton-1DoGETNODE(T)/該過程產(chǎn)生一個(gè)新結(jié)點(diǎn)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個(gè)作業(yè)需要在一臺(tái)機(jī)器上處理，每個(gè)作業(yè)可在單位時(shí)間內(nèi)完成。每個(gè)作業(yè)i都有一個(gè)截止期限di>0(di為整數(shù))，當(dāng)且僅當(dāng)作業(yè)i在它的截止期限之前被完成，獲得pi>0的效益。一種可行的調(diào)度方案為n個(gè)作業(yè)的一個(gè)子集J，其中J中的每個(gè)作業(yè)都能在各自的截止期限內(nèi)完成。該可行調(diào)度方案的效益是J中作業(yè)的效益之和。試設(shè)計(jì)貪心算法求效益最大的可行調(diào)度方案(即最優(yōu)調(diào)度方案)。解答：(1)貪心準(zhǔn)則：從J=開始，不斷添加作業(yè)到J中。每次加入J的作業(yè)是保證J是可行的前提下使得J中效益達(dá)到最大。即，按照pi由大到小的次序來考慮作業(yè)。(2)貪心算法：AlgorithmJOBSCHEDULE輸入：n個(gè)作業(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. 多機(jī)調(diào)度問題：多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。同時(shí)約定每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。2. 優(yōu)先隊(duì)列式分支限界法：優(yōu)先

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

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

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

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

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

21、壞時(shí)間復(fù)雜度是O(nkn)。3.對(duì)于下圖使用Dijkstra算法求由頂點(diǎn)a到其他各個(gè)頂點(diǎn)的最短路徑。并給出求各個(gè)頂點(diǎn)對(duì)之間的最短路徑的算法思想。解：用Vi表示已經(jīng)找到最短路徑的頂點(diǎn)，V2表示與Vi中某個(gè)頂點(diǎn)相鄰接且不在Vi中的頂點(diǎn)；Ei表示加入到最短路徑中的邊，E2為與Vi中的頂點(diǎn)相鄰接且距離最短的路徑。步驟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