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

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

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

5、ld。二叉樹T的根結點值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大元素，并分析算法的時間復雜度。解答：算法思想：當序列A1.n中元素的個數n=2時，通過直接比較即可找出序列的第2大元素。當n>2時，先

6、求出序列A1.n-1中的第1大元素x1和第2大元素x2；然后，通過2次比較即可在三個元素x1x2和An中找出第2大元素，該元素即為A1.n中的第2大元素。算法描述如下：SecondElement(Alow.high,max1,max2)/假設主程序中調用該過程條件為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;該算法的時間復雜度滿足如下遞歸方程：T(n)=T(n-1)+2；T(2)=1。解得T(n)=2n-3。作業二一、名詞解釋：1、MST性質：G=(V,E)是連通帶權圖，U是V的真子集。如果(u,v)巳且uU,vV-U,且在所有這樣的邊中，(u,v)的權cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質稱為MST性質。2、子問題的重疊性質：遞歸算法求解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次，這種性質稱為子問題的重疊性質。二、簡答題：1、簡述動態規劃算法求

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

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

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

11、匯)，圖中所有的邊(u,v),uVi,vMi。求由s到t的最小成本路徑。a) 給出使用動態規劃算法求解多段圖問題的基本思想。b) 使用上述方法求解如下多段圖問題。V1V2V3V4V57,7 29,67,1024,126 : 9516,2/3彳 3s 17318,8115,101142,12 41,122 12 t111解：(1)基本思想：設P(i,j)是從Vi中的節點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其中每個節點標示的序偶(p,q)中，p表示節點到t的成本，q表示后繼節點的編號。從而，最優路徑為:1271012和1361012,成本為16。3、最優二元歸并問題：已知將兩個分別包含a個和b個記錄的已分類文件歸并在一起得到一個分類文件需作a+b次記錄移動。現有n個已分類文件F1,F1,?,Fn,它們的記錄個數分別為l1,l2,?,ln。現在考慮使用二元歸并模式將這n個文件歸并成一個分類文件，要求記錄移動次數最少。設計一個貪心算法來求解一種最優的二元歸并(即記錄移動次數最少的二元歸并)。解答：(1)貪心準則：依次將文件序列中記錄最少的兩個

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

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

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

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

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

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

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

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

21、壞時間復雜度是O(nkn)。3.對于下圖使用Dijkstra算法求由頂點a到其他各個頂點的最短路徑。并給出求各個頂點對之間的最短路徑的算法思想。解：用Vi表示已經找到最短路徑的頂點，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