算法設(shè)計與分析復習題

1、算法設(shè)計與分析復習題1、分治法的基本思想：是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。2、貪心選擇性質(zhì)：指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，3、什么是剪枝函數(shù)：回溯法搜索解空間樹時，通常采用兩種策略避免無效搜索，提高回溯法的搜索效率。其一是用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹；其二是用限界函數(shù)剪去得不到最優(yōu)解的子樹。這兩類函數(shù)統(tǒng)稱為剪枝函數(shù)。4、分支限界法的基本思想：(1)分支限界法常以廣度優(yōu)先或以最小耗費(最大效益)優(yōu)先的方式搜索問題的解空間樹。(2)在分支限界法中，每一個

2、活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。(3)此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴展過程，這個過程一直持續(xù)到找到所需的解或活結(jié)點表這空時為止。5、什么是算法的復雜性：是該算法所需要的計算機資源的多少，它包括時間和空間資源。6、最優(yōu)子結(jié)構(gòu)性質(zhì)：該問題的最優(yōu)解包含著其子問題的最優(yōu)解。7、回溯法：是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法。這在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，先判斷該

3、結(jié)點是否包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。8、什么是分支定界法：對有約束條件的最優(yōu)化問題所有可行解定向、適當?shù)剡M行搜索。將可行解空間不斷地劃分為越來越小的子集（分支），并為每一個子集的解計算一個上界和下界（定界）。9、算法滿足的性質(zhì)：輸入、輸出、確定性、有限性。10、遞歸算法的優(yōu)點：結(jié)構(gòu)清晰，可讀性強，容易用數(shù)學歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。11、回溯法效率的因素：（1）產(chǎn)生xk的時間。（2）滿足顯約束的xk值的個數(shù)。（3）計算約束函數(shù)constraint的時間。

4、（4）計算上界函數(shù)bound的時間。（5）滿足約束函數(shù)和上界函數(shù)約束的所有xk的個數(shù)12、最常見的分支限界法有兩種：隊列式（FIFO）分支限界法和優(yōu)先隊列式分支限界法。13、 什么是算法, 算法具有的特性是什么？是解決問題的方法和過程, 1） 輸入0個或多個信息 2） 輸出至少一個信息 3） 確定性：組成算法的每個指令是清晰的，無二義的，整個過程是確定的 4） 有限性：14、 什么是動態(tài)規(guī)劃法：將問題分解成多級或許多子問題，然后順序求解子問題，前一個子問題的解為后一個子問題的求解提供有用的信息。15、 什么是貪心法：從問題某一初始或推測值出發(fā)，一步步的攀登給定目標，盡可能快的去逼近更好的解，當

5、達到某一步不能繼續(xù)時終止。16、遞歸算法的缺點：運行效率較低，耗費的計算時間和占用的存儲空間都多。為了達到此目的，根據(jù)具體程序的特點對遞歸調(diào)用工作棧進行簡化，盡量減少棧操作，壓縮棧存儲空間以達到節(jié)省計算時間和存儲空間的目的。17、合并排序的時間復雜度是：T(n)=O(nlogn)。18、快速排序的時間復雜度是：T(n)=O(nlogn)。19、動態(tài)規(guī)劃算法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。20、貪心算法的基本要素：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。選擇題1、二分搜索算法是利用（分治策略 ）實現(xiàn)的算法。A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法2、下列不是動態(tài)規(guī)劃算法基本步驟的是

6、（D ）。A、找出最優(yōu)解的性質(zhì) B、構(gòu)造最優(yōu)解 C、算出最優(yōu)解 D、定義最優(yōu)解3、下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（c ）。A、備忘錄法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法4、最大效益優(yōu)先是（C ）的搜索方式。A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法5、0-1背包問題的回溯算法所需的計算時間為（ b）O（n2n） B、O（nlogn） C、O（2n） D、O（n）簡答題1、寫出設(shè)計流水作業(yè)調(diào)度算法的主要步驟。2、舉例說明貪心算法與動態(tài)規(guī)劃算法的的主要差別。3、寫出用回溯法搜索子集樹的一般算法。4、簡述利用貪心算法解決“單源最短路徑”問題的基本思想。5、簡述分治法

7、的基本思想。6、寫出設(shè)計動態(tài)規(guī)劃算法的主要步驟。7、簡述分支限界法與回溯法的異同。8、寫出用回溯法搜索排列樹的算法。算法題：01背包問題：給定n種物品和一背包，物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)該如何裝入背包中物品的總價值最大？寫出用分支限界算法解決該問題的算法。例題1.選擇范例（1）分支限界法與回溯法都是在問題的解空間樹T上搜索問題的解，二者（）。A求解目標不同，搜索方式相同B求解目標不同，搜索方式也不同C求解目標相同，搜索方式不同D求解目標相同，搜索方式也相同（2）下列是動態(tài)規(guī)劃算法基本要素的是（ ）。A、最優(yōu)子結(jié)構(gòu) B、構(gòu)造最優(yōu)解 C、算出最優(yōu)解 D、定義最優(yōu)解（3）

8、Strassen矩陣乘法是利用（ ）實現(xiàn)的算法。A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法（4）下面不是分支界限法搜索方式的是（ ）。A、廣度優(yōu)先 B、最小耗費優(yōu)先 C、最大效益優(yōu)先 D、深度優(yōu)先2.判斷范例（1）所有的遞歸函數(shù)都能找到對應(yīng)的非遞歸定義。（2）滿足最優(yōu)子結(jié)構(gòu)性質(zhì)必滿足貪心選擇性質(zhì)。（3）滿足貪心選擇性質(zhì)必滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。（4）狀態(tài)空間樹中，只有展開了所有子結(jié)點的結(jié)點才稱為死結(jié)點。(5)變治法是基于變換的思想。分兩個階段工作，即“變”階段和“治”階段.變治法的三種類型：1)實例化簡(instance simplification)2)改變表現(xiàn)(representat

9、ion change)3)問題化簡(problem reduction)。例如AVL樹，多路查找樹都是實例化簡的具體應(yīng)用。(6)時空權(quán)衡是指在算法的設(shè)計中，對算法的時間和空間作出權(quán)衡。常見的以空間換取時間的方法有：輸入增強（計數(shù)排序，串匹配算法的改進）預構(gòu)造（散列法，B樹） (7)動態(tài)規(guī)劃算法基本思想是將待求解問題分解成若干個子問題，并且經(jīng)分解得到的子問題是互相獨立的。求解時有些子問題被重復計算了許多次。2解釋下面術(shù)語哈密爾頓環(huán)貪心算法分枝限界方法0/1背包問題算法3.簡答范例簡述回溯法求解問題的一般步驟。簡述狀態(tài)空間樹的廣度優(yōu)先展開方法。狀態(tài)空間樹中的活結(jié)點、E-結(jié)點、死結(jié)點簡述用回溯法設(shè)計

10、算法的步驟。舉例說明最小生成樹在實際中的應(yīng)用。4.分析設(shè)計題上課反復講、反復強調(diào)的幾個問題，要求懂原理，會設(shè)計（關(guān)鍵是思路，表達方法可以是語言、偽代碼、代碼），會進行復雜度分析。建議：答題時不要把所有的東西寫一大段，適當分步驟、分要點，如XXX算法原理做什么，怎么做做什么，怎么做做什么，怎么做等8. 以下是分數(shù)背包問題的貪心算法算法 GREEDY_KANPSACK輸入：表示背包容量的實數(shù)C, 物品數(shù)n, 表示n個物品的體積和價值的實數(shù)數(shù)組s1.n和v1.n。輸出：裝入背包物品的最大總價值maxv和相應(yīng)的最優(yōu)解x1.n。 for i=1 to n yi=vi/si /求n個物品的單位體積價值y1.n。 end for /對y1.n按降序地址排序，排序結(jié)果返回到數(shù)組d1.n /中, 使得yd1=yd2=ydn。 d=sort(y, n) for i=1 to n xi=0 /對x1.n初始化。 i=1; maxv=0; rc=C /以下rc表示當前背包的剩余容量。while _ a