中南大學(xué)204算法試卷及答案分析報告

1、中南大學(xué)考試試卷2013 - 2014 學(xué)年 下 學(xué)期 時間100分鐘2014 年6月6日算法分析與設(shè)計 課程48學(xué)時丄學(xué)分 考試形式：閉 卷專業(yè)年級：12級計算機、信安、物聯(lián)本科生，總分 100分，占總評成績70 %注：此頁不作答題紙，請將答案寫在答題紙上一、簡答題（本題30分，每小題5分）1、陳述算法在最壞情況下的時間復(fù)雜度和平均時間復(fù)雜度；這兩種評估算法復(fù)雜性的方 法各自有什么實際意義？1 最壞情況下的時間復(fù)雜度稱最壞時間復(fù)雜度。一般不特別說明，討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度。意義：最壞情況下的時間復(fù)雜度是算法在任何輸入實例上運行時間的上界，這就保證了算法的運行時間不會比任何

2、更長2 平均時間復(fù)雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的期望運行時間。意義：在輸入不同的情況下算法的運行時間復(fù)雜度可能會發(fā)生變化。平均時間復(fù)雜度給出了算法的期望運行時間，有助于算法好壞的評價以及在不同算法 之間比較時有一個統(tǒng)一標準2、簡單描述分治法的基本思想。分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問 題的解。3、何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，我們就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動態(tài)規(guī)劃算法解決問題

3、提供了重要線索。4、何謂P、NR NPC問題P（Polynomial問題）：也即是多項式復(fù)雜程度的問題。NP就是Non-deterministicPolynomial的問題，也即是多項式復(fù)雜程度的非確定性問題。NPQNP Complete）問題，這種問題只有把解域里面的所有可能都窮舉了之后才能得出 答案，這樣的問題是 NP里面最難的問題，這種問題就是NPC問題。5、試比較回溯法與分支限界法。1、引言1.1回溯法回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，則 跳過對該結(jié)點為根的子樹的搜索，逐層向

4、其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按 深度優(yōu)先策略搜索。這種以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法。1.2分支限界法分支限界法是以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹，在每一個活結(jié)點處，計算一個函數(shù)值，并根據(jù)函數(shù)值，從當前活結(jié)點表中選擇一個最有利的結(jié)點作為擴 展結(jié)點，使搜索朝著解空間上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解，這種 方法稱為分支限界法。2、回溯法的基本思想用回溯法解問題時，應(yīng)明確定義問題的解空間。問題的解空間至少應(yīng)包含問題的一 個解。之后還應(yīng)將解空間很好的組織起來，使得能用回溯法方便的搜索整個解空間。在 組織解空間時常用到兩種典型的解空間樹，即子集樹和排列樹

5、。確定了解空間的組織結(jié) 構(gòu)后，回溯法從開始結(jié)點出發(fā)，以深度優(yōu)先方式搜索整個解空間。這個開始結(jié)點成為活 結(jié)點，同時也成為當前的擴展結(jié)點。在當前的擴展結(jié)點處，搜索向縱深方向移至一個新 結(jié)點。這個新結(jié)點就成為新的活結(jié)點，并成為當前擴展結(jié)點。如果在當前的擴展結(jié)點處 不能再向縱深方向移動，則當前擴展結(jié)點就成為死結(jié)點。此時，應(yīng)往回移動至最近的一 個活結(jié)點處，并使這個活結(jié)點成為當前的擴展結(jié)點?；厮莘ㄒ赃@種工作方式遞歸的在解 空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點時為止。3、分支限界法的基本思想用分支限界法解問題時，同樣也應(yīng)明確定義問題的解空間。之后還應(yīng)將解空間很好 的組織起來。分支限界法也有兩種

6、組織解空間的方法，即隊列式分支限界法和優(yōu)先隊列 式分支限界法。兩者的區(qū)別在于：隊列式分支限界法按照隊列先進先出的原則選取下一 個節(jié)點為擴展節(jié)點，而優(yōu)先隊列式分支限界法按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級 最高的節(jié)點成為當前擴展節(jié)點。分支限界法常以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點 一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導(dǎo)致不可行解 或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。此后，從活結(jié)點 表中取下一結(jié)點成為當前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程。這個過程一直持續(xù)到找 到所需的

7、解或活結(jié)點表為空時為止。4、回溯法的設(shè)計原理在設(shè)計一個回溯算法時，通常按照以下步驟進行：（1）針對所給問題，定義問題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。在一般情況下用遞歸方法實現(xiàn)回溯法的基本框架如下：void backtrack （ int t ）if （ t>n ） output （ x）；elsefor （int i=f （n, t）； i<=g （ n, t）； i+） xt=h （i）；if(constraint(t) &&bound (t) backtrack (t+1 );其中：

8、t表示遞歸深度，output (x)記錄或輸出得到的可行解x, f (n, t )和g(n，t)分別表示在當前擴展結(jié)點處未搜索過的子樹的起始編號和終止編號，h (i )表示當前擴展結(jié)點處的第i個可選值，constraint(t )和bound (t)表示當前擴展結(jié)點的約束函數(shù)和限界函數(shù)。5、分支限界法的設(shè)計原理在設(shè)計一個分支限界算法時，通常按照以下步驟進行：(1) 針對所給問題，定義問題的解空間；(2) 確定易于搜索的解空間結(jié)構(gòu)；(3) 以廣度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。6、回溯法與分支限界法的差異及應(yīng)用回溯法與分支定界法都是在問題的解空間上搜索問題解的算法。但是

9、兩者是有區(qū)別的：首先，求解目標不同：一般而言，回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是盡快地找出滿足約束條件的一個解。其次，搜索方法不同：由于求解目標不同，導(dǎo)致分支限界法與回溯法對解空間的搜索方式也不同，回溯法 采用深度優(yōu)先方法搜索解空間，而分支限界法一般采用用廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間。再次，對擴展結(jié)點的擴展方式不同：在搜索解空間書中兩者的主要區(qū)別在于它們對當前擴展結(jié)點所采用的擴展方式不同。在回溯法中，如果當前的擴展結(jié)點不能夠再向縱深方向移動，則當前擴展結(jié)點就成 為死結(jié)點，此時應(yīng)回溯到最近的一個活結(jié)點處，并使此活結(jié)點成為擴展結(jié)點。而在分支

10、 限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一 次性產(chǎn)生其所有兒子結(jié)點。最后，存儲空間的要求不同：分支限界法的存儲空間比回溯法大得多，因此當內(nèi)存容量有限時，回溯法成功的可能性更大。下面結(jié)合具體的實例來說明何種情況下比較適合采用回溯法，何種情況下比較適合采用分支限界法：適合采用回溯法的問題：最典型的代表如n后問題，即在n*n個格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列 或同一斜線上的棋子。對于n后問題，解與解之間不存在優(yōu)劣的區(qū)別。必須要搜索到葉節(jié)點時才能確定出一組解。這種情況下，我們采用回溯法來解決時，采用排列樹的

11、解空 間結(jié)構(gòu)，在最壞的情況下，其堆棧的深度不會超過n。而采用分支限界法時，由于解之間不存在優(yōu)劣關(guān)系，故不可能用限界函數(shù)剪枝，需要較大的存儲空間。適合采用分支限界法的問題：最典型的代表如布線問題，即印刷電路板將布線區(qū)域戈U分成n*m個方格陣列。要求確定連接方格a的中點到方格b的中點的最短布線方案。在布線時，電路只能沿直線或直角布線。為了避免線路相交，已布了線的方格做了封鎖 標記，其他線路不允許穿過被封鎖的方格。此問題，如果采用回溯法來解決時，為了找 到最短路徑，必須把整個區(qū)域的所有路徑逐一搜索后才能得到最優(yōu)解，這使得算法效率 較低。而如果用分支限界法來解決，則可以保證找到的解是最短的布線方案，因

12、為如果 存在一條由a至b的更短的路徑，b結(jié)點一定會更早地被加入到活結(jié)點隊列中并得到處 理。6、貪心法是一種通過多步選擇，試圖獲得最優(yōu)解的方法。貪心法每次選擇的原則是什么？ 請舉例說明。設(shè)計貪心算法的三個步驟將最優(yōu)化問題轉(zhuǎn)化為這樣的形式：對其做出一次選擇后，只剩下一個子問題需要求解（比較重要的一步）證明作出貪心選擇后，原問題總是存在最優(yōu)解，即貪心選擇總是安全的證明作出貪心選擇后，剩余的子問題滿足性質(zhì)：其最優(yōu)解與貪心選擇組合即可得 到原問題的最優(yōu)解，這樣就得到了最優(yōu)子結(jié)構(gòu)兩個關(guān)鍵因素1. 貪心選擇性質(zhì)：可以通過做出局部最優(yōu)（貪心）選擇來構(gòu)造全局最優(yōu)解；即每個步驟做出貪心選擇能生成全局最優(yōu)解【視不同

13、具體問題進行證明，沒有普遍適用的方法】2. 最優(yōu)子結(jié)構(gòu)：一個問題的最優(yōu)解包含其子問題的最優(yōu)解經(jīng)典最優(yōu)化問題的兩個變形0-1背包問題：一個正在搶劫的小偷發(fā)現(xiàn)了n個商品，第i個商品價值vi美元，重wi磅，vi和wi都是整數(shù)；小偷想盡可能拿走價值更多的商品，但是他的背包最多能容納W磅的商品，W是一個整數(shù)【對每個商品，不能拿走一部分，要么完整拿走，要么留下） 分數(shù)背包問題：條件和0-1背包問題一樣，但對每個商品，小偷可以拿走一部分兩個問題都有最優(yōu)子結(jié)構(gòu)，很相似，但是貪心算法可以求解分數(shù)背包問題，而不能求解0-1背包問題分數(shù)背包問題：計算每個商品的每磅價值vi/wi，每次選擇每磅價值最高的商品即可0-1

14、背包問題：因為小偷無法裝滿背包，空閑空間降低了方案的有效每磅價值； 當我們考慮一個商品食肉裝入背包，需要比較包含此商品的子問題的解和不包含它的子問題的解，然后才能做出選擇當然，由于兩個問題都有最優(yōu)子結(jié)構(gòu)，所以能用動態(tài)規(guī)劃算法進行求解。/拓展/二、簡答題(本題 25分，每小題5分)1、簡單描述分治法的基本思想。2、簡述動態(tài)規(guī)劃方法所運用的最優(yōu)化原理。3、何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？4、簡單描述回溯法基本思想。5、何謂P、NP NPC'可題二、簡答題(本題 25分，每小題5分)1、分治法的基本思想 是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題， 這些子 問題互相獨立且與原問題相同；對這 k個子

15、問題分別求解。如果子問題的規(guī)模仍然 不夠小，則再劃分為 k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很 容易求出其解為止；將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解， 自底向上逐步求出原來問題的解。2、“最優(yōu)化原理”用數(shù)學(xué)化的語言來描述：假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個決策D1, D2,，Dn,如若這個決策序列是最優(yōu)的，對于任何一個整數(shù)k, 1 < k<n，不論前面k個決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當 前狀態(tài)，即以后的決策 Dk+1, Dk+2,，Dn也是最優(yōu)的。3、 某個問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)

16、性質(zhì)。4、回溯法的基本思想 是在一棵含有問題全部可能解的狀態(tài)空間樹上進行深度優(yōu)先搜索，解為葉子結(jié)點。搜索過程中，每到達一個結(jié)點時，則判斷該結(jié)點為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對該子樹的搜索，退回到 上層父結(jié)點，繼續(xù)下一步深度優(yōu)先搜索過程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài) 空間樹，再進行搜索，而是在搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。5、P(Polynomial問題)：也即是多項式復(fù)雜程度的問題。NP就是Non-deterministicPolynomial的問題，也即是多項式復(fù)雜程度的非確定性問題。NPC(NP Complete)問題，這種

17、問題只有把解域里面的所有可能都窮舉了之后才能得出 答案，這樣的問題是NP里面最難的問題，這種問題就是NPC問題。/二、選擇題(14分，每題2分)1. 下述表達不正確的是 。A. n2/2 + 2 n的漸進表達式上界函數(shù)是0(2)B . n2/2 + 2 n的漸進表達式下界函數(shù)是Q(2 n)C. logn3的漸進表達式上界函數(shù)是O(logn) D . logn3的漸進表達式下界函數(shù)是Q(n 3)logn 3的漸進表達式下界函數(shù)是O（logn）2. 下列算法中通常以自底向上的方式求解最優(yōu)解的是 A.動態(tài)規(guī)劃法B.貪心法C.回溯法3. 下面關(guān)于NP問題說法正確的是A. NP問題都是不可能解決的問題B

18、. P類問題包含在 NP類問題中B. NP完全問題是P類問題的子集D. NP 類問題包含在 P類問題中首先這些p和 叩都是用來描述解決一個問題需要的時間和它輸入規(guī)模之間的關(guān)系P問題：一個問題可以在多項式（0（門你）的時間復(fù)雜度內(nèi)解決例如：n個數(shù)的排序（不超過 0（nA2）NP問題：一個問題的解可以在多項式的時間內(nèi)被證實或證偽例如：典型的子集求和問題，給定一個整數(shù)集合求是否存在一個非空子集它的和為零。 如給定集合s=-1,3,2,-5,6，很明顯子集32-5能滿足問題，并且驗證該解只需要 線性時間復(fù)雜度就能被證實。NP-hard 問題：任意np問題都可以在多項式時間內(nèi)歸約為該問題。歸約的意思是為

19、了解決問題 A,先將問題A歸約為另一個問題B,解決問題B同時也間接解決了問題 A。例如，停機問題。NPC'可題：既是NP問題，也是 NP-hard問題。例如，SAT問題（第一個NPC問題）。該問題的基本意思是，給定一系列布爾變量以及 它的約束集，是否存在一個解使得它的輸出為真。相互關(guān)系：顯然，所有P問題都是NP問題，反之則不一定。npc問題是np問題的子集，也是p問 題和np問題的差異所在。如果找到一個多項式內(nèi)能被解決的npc問題的解決方法，那么 P=NP4. 下列算法中不能解決 0/1背包問題的是A.貪心法B.動態(tài)規(guī)劃C.回溯法D.分支限界法5. 是貪心算法與動態(tài)規(guī)劃算法的共同點。A

20、.重疊子問題 B .構(gòu)造最優(yōu)解 C .貪心選擇性質(zhì)D.最優(yōu)子結(jié)構(gòu)性質(zhì)貪心算法的基本要素貪心算法通過一系列的選擇得到問題的解。它所做出的每一選擇都是當前狀態(tài)下局部最好選擇，即貪心選擇?？梢杂秘澬乃惴ㄇ蠼獾膯栴}一般具有兩個重要性質(zhì)：(1) 貪心選擇性質(zhì)。所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解能通過一系列局部 最優(yōu)的選擇(即貪心選擇)來達到。(2) 最優(yōu)子結(jié)構(gòu)性質(zhì)。與動態(tài)規(guī)劃算法相同，最優(yōu)子結(jié)構(gòu)性質(zhì)是一個問題可用貪心算法求解的關(guān)鍵特征。6. 以下關(guān)于判定問題難易處理的敘述中正確的是 。A. 可以由多項式時間算法求解的問題是難處理的B. 需要超過多項式時間算法求解的問題是易處理的C可以由多項式時間算

21、法求解的問題是易處理的D.需要超過多項式時間算法求解的問題是不能處理的7. n個同學(xué)拎著水桶在一個水龍頭前面排隊打水，水桶有大有小，水桶必須打滿水，水流恒定。如下說法不正確？A. 讓水桶大的人先打水，可以使得每個人排隊時間之和最小B. 讓水桶小的人先打水，可以使得每個人排隊時間之和最小C. 讓水桶小的人先打水，在某個確定的時間t內(nèi)，可以讓盡可能多的人打上水D. 若要在盡可能短的時間內(nèi)，n個人都打完水，按照什么順序其實都一樣三、解答題(30分)1. 用貪心法求下圖的最大生成樹 (5分)8貪心算法最小生成樹設(shè)G = (V,E)是無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。E中的每一條邊(v,w)的權(quán)為cvw。如果

22、G的子圖G'是一棵包含 G的所有頂點的樹，則稱G為G的生成樹。生成樹上各邊權(quán)的總和稱為生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。構(gòu)造最小生成樹的兩種方法：Prim算法和Kruskal算法。、最小生成樹的性質(zhì)設(shè)G =(V,E)是連通帶權(quán)圖，這樣的邊中，(u,v)的權(quán)cuv 中一條邊。這個性質(zhì)有時也稱為U是V的真子集。如果(u,v) E,且u U,v V-U,且在所有 最小，那么一定存在 G的一棵最小生成樹，它意(u,v)為其MST性質(zhì)。二、Prim算法設(shè)G = (V,E)是連通帶權(quán)圖，V = 1,2,n。構(gòu)造G的最小生成樹Prim算法的基本 思想是：首先置S

23、= 1，然后，只要S是V的真子集，就進行如下的貪心選擇：選取滿 足條件i S,j V - S,且cij 最小的邊，將頂點j添加到S中。這個過程一直 進行到S = V時為止。在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。如下帶權(quán)圖：生成過程：1 -> 3 : 13 -> 6 : 46 -> 4: 23 -> 2 : 52 -> 5 : 3實現(xiàn)：三、Kruskal算法當圖的邊數(shù)為 e時，Kruskal算法所需的時間是 O(eloge)。當e = Q (nA2)時，Kruskal 算法比Prim算法差；但當 e =0(門人2)時，Kruskal算法比Prim算法

24、好得多。給定無向連同帶權(quán)圖G = (V,E),V= 1,2,.,n 。Kruskal算法構(gòu)造G的最小生成樹的基本思想是：(1)首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權(quán)從小大排序。(2 )從第一條邊開始，依邊權(quán)遞增的順序檢查每一條邊。并按照下述方法連接兩個不同的連通分支：當查看到第k條邊(v,w)時，如果端點v和w分別是當前兩個不同的連通分支T1和T2的端點是，就用邊(v,w)將T1和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看k+1條邊。這個過程一個進行到只剩下一個連通分支時為止。此時，已構(gòu)成G的一棵最小生成樹。Kruskal算法的選邊過程：1 -> 3:14 -> 6:22 -> 5:33 -> 4:42 -> 3:5兩種算法代碼見教材2. 對數(shù)組A=15 , 29, 135,18, 32, 1 , 27, 25, 5，寫出用快速排序算法（按升序排序） 的第一