算法設(shè)計與分析復(fù)習(xí)題目及參考答案

1、.一。選擇題1、二分搜索算法是利用（   A      ）實現(xiàn)的算法。A、分治策略   B、動態(tài)規(guī)劃法   C、貪心法    D、回溯法2、下列不是動態(tài)規(guī)劃算法基本步驟的是（   A    ）。A、找出最優(yōu)解的性質(zhì)   B、構(gòu)造最優(yōu)解   C、算出最優(yōu)解   D、定義最優(yōu)解3、最大效益優(yōu)先是（  A 

2、;        ）的一搜索方式。A、分支界限法      B、動態(tài)規(guī)劃法    C、貪心法    D、回溯法4、在下列算法中有時找不到問題解的是（ B       ）。A、蒙特卡羅算法    B、拉斯維加斯算法   C、舍伍德算法   D、數(shù)值概率算法5. 回溯法解旅行售貨員問

3、題時的解空間樹是（ B      ）。A、子集樹B、排列樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹6下列算法中通常以自底向上的方式求解最優(yōu)解的是（   B      ）。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法7、衡量一個算法好壞的標準是（C ）。A 運行速度快 B 占用空間少 C 時間復(fù)雜度低 D 代碼短8、以下不可以使用分治法求解的是（D ）。A 棋盤覆蓋問題 B 選擇問題 C 歸并排序 D 0/1背包問題9. 實現(xiàn)循環(huán)賽日程表利用的算法是（

4、0;   A      ）。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法10、下列隨機算法中運行時有時候成功有時候失敗的是（C ）A 數(shù)值概率算法 B 舍伍德算法 C 拉斯維加斯算法 D 蒙特卡羅算法11下面不是分支界限法搜索方式的是（     D     ）。A、廣度優(yōu)先B、最小耗費優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先12下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（     

5、; D   ）。A、備忘錄法B、動態(tài)規(guī)劃法C、貪心法D、回溯法13.備忘錄方法是那種算法的變形。（ B ）A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法14哈弗曼編碼的貪心算法所需的計算時間為（   B     ）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）15分支限界法解最大團問題時，活結(jié)點表的組織形式是（    B    ）。A、最小堆B、最大堆 C、棧D、數(shù)組16最長公共子序列算法利用的算法是（

6、0;   B       ）。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法17實現(xiàn)棋盤覆蓋算法利用的算法是（     A      ）。A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法18.下面是貪心算法的基本要素的是（      C     ）。A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、定義最優(yōu)解19

7、.回溯法的效率不依賴于下列哪些因素（ D ）A.滿足顯約束的值的個數(shù) B. 計算約束函數(shù)的時間 C. 計算限界函數(shù)的時間 D. 確定解空間的時間20.下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（    B    ）A遞歸函數(shù)B.剪枝函數(shù) C。隨機數(shù)函數(shù)D.搜索函數(shù)21、下面關(guān)于NP問題說法正確的是（B ）A NP問題都是不可能解決的問題B P類問題包含在NP類問題中C NP完全問題是P類問題的子集D NP類問題包含在P類問題中22、蒙特卡羅算法是（   B   

8、   ）的一種。A、分支界限算法      B、概率算法    C、貪心算法    D、回溯算法23.下列哪一種算法不是隨機化算法（    C     ）A. 蒙特卡羅算法B. 拉斯維加斯算法C.動態(tài)規(guī)劃算法D.舍伍德算法24. （   D         ）是貪心算法與動態(tài)規(guī)劃

9、算法的共同點。A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、最優(yōu)子結(jié)構(gòu)性質(zhì)25. 矩陣連乘問題的算法可由（          B）設(shè)計實現(xiàn)。A、分支界限算法      B、動態(tài)規(guī)劃算法    C、貪心算法    D、回溯算法26. 分支限界法解旅行售貨員問題時，活結(jié)點表的組織形式是（   A    ）。A、最小堆B、最大堆 C

10、、棧D、數(shù)組27、Strassen矩陣乘法是利用（    A     ）實現(xiàn)的算法。A、分治策略   B、動態(tài)規(guī)劃法   C、貪心法    D、回溯法29、使用分治法求解不需要滿足的條件是（A ）。A 子問題必須是一樣的B 子問題不能夠重復(fù)C 子問題的解可以合并D 原問題和子問題使用相同的方法解30、下面問題（B ）不能使用貪心法解決。A 單源最短路徑問題 B N皇后問題 C 最小花費生成樹問題 D 背包問題31、下列算法中不能解決0/1背包問題

11、的是（A ）A 貪心法 B 動態(tài)規(guī)劃 C 回溯法 D 分支限界法32、回溯法搜索狀態(tài)空間樹是按照（C ）的順序。A 中序遍歷 B 廣度優(yōu)先遍歷 C 深度優(yōu)先遍歷 D 層次優(yōu)先遍歷33、下列隨機算法中運行時有時候成功有時候失敗的是（C ）A 數(shù)值概率算法 B 舍伍德算法 C 拉斯維加斯算法 D 蒙特卡羅算法34實現(xiàn)合并排序利用的算法是（     A    ）。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法35下列是動態(tài)規(guī)劃算法基本要素的是（  D     ）

12、。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子問題重疊性質(zhì)36下列算法中通常以自底向下的方式求解最優(yōu)解的是（    B     ）。A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法37采用廣度優(yōu)先策略搜索的算法是（     A      ）。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法38、合并排序算法是利用（   A      ）實

13、現(xiàn)的算法。A、分治策略   B、動態(tài)規(guī)劃法   C、貪心法    D、回溯法39、在下列算法中得到的解未必正確的是（  B      ）。A、蒙特卡羅算法    B、拉斯維加斯算法   C、舍伍德算法   D、數(shù)值概率算法40、背包問題的貪心算法所需的計算時間為（  B      ）A、O（n2n） 

14、0;   B、O（nlogn）    C、O（2n）      D、O（n）41實現(xiàn)大整數(shù)的乘法是利用的算法（      C   ）。A、貪心法B、動態(tài)規(guī)劃法C、分治策略D、回溯法420-1背包問題的回溯算法所需的計算時間為（  A      ）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）43采用最大效益優(yōu)先搜索方式的算法是（&#

15、160;  A        ）。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法44貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是（  B         ）。A、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解D、定義最優(yōu)解45. 實現(xiàn)最大子段和利用的算法是（     B      ）。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D

16、、回溯法46.優(yōu)先隊列式分支限界法選取擴展結(jié)點的原則是（     C      ）。A、先進先出B、后進先出C、結(jié)點的優(yōu)先級D、隨機47.背包問題的貪心算法所需的計算時間為（   B     ）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）48、廣度優(yōu)先是（    A       ）的一搜索方式。A、分支界限法

17、      B、動態(tài)規(guī)劃法    C、貪心法    D、回溯法49、舍伍德算法是（    B     ）的一種。A、分支界限算法      B、概率算法    C、貪心算法    D、回溯算法50、在下列算法中有時找不到問題解的是（  B   

18、60;  ）。A、蒙特卡羅算法    B、拉斯維加斯算法   C、舍伍德算法   D、數(shù)值概率算法51下列哪一種算法是隨機化算法（    D     ）A. 貪心算法B. 回溯法C.動態(tài)規(guī)劃算法D.舍伍德算法52. 一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（   B          ）。A、重疊子問題

19、B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解53采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復(fù)雜度為 ( B ) 。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）54. 以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 ( D ) 。A、分支界限算法      B、概率算法    C、貪心算法    D、回溯算法55. 實現(xiàn)最長公共子序列利用的算法是（     B  

20、    ）。A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法56、算法是由若干條指令組成的有窮序列，而且滿足以下性質(zhì)（ D ）（1） 輸入：有0個或多個輸入（2） 輸出：至少有一個輸出（3） 確定性：指令清晰，無歧義（4） 有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行時間有限 A (1)(2)(3) B(1)(2)(4) C(1)(3)(4) D (1) (2)(3)(4)57、函數(shù)32n+10nlogn的漸進表達式是( B ).A. 2n B. 32n C. nlogn D. 10nlogn58、大整數(shù)乘法算法是( A ).算法A.分治 B.貪心C.動態(tài)規(guī)劃 D.窮舉59、

21、用動態(tài)規(guī)劃算法解決最大字段和問題，其時間復(fù)雜性為( B ).A.logn B.n C.n2 D.nlogn60、解決活動安排問題，最好用（B ）算法A.分治 B.貪心C.動態(tài)規(guī)劃 D.窮舉61、設(shè)f(N),g(N)是定義在正數(shù)集上的正函數(shù),如果存在正的常數(shù)C和自然數(shù)N0,使得當NN0時有f(N)Cg(N),則稱函數(shù)f(N)當N充分大時有下界g(N),記作f(N)(g(N),即f(N)的階( A )g(N)的階.A.不高于 B.不低于C.等價于 D.逼近62、回溯法在解空間樹T上的搜索方式是( A ).A.深度優(yōu)先 B.廣度優(yōu)先 C.最小耗費優(yōu)先 D.活結(jié)點優(yōu)先63、回溯算法和分支限界法的問題的

22、解空間樹不會是(D ).A.有序樹 B.子集樹C.排列樹 D.無序樹64、在對問題的解空間樹進行搜索的方法中,一個活結(jié)點最多有一次機會成為活結(jié)點的是( B ).A.回溯法 B.分支限界法C.回溯法和分支限界法 D.回溯法求解子集樹問題65、從活結(jié)點表中選擇下一個擴展結(jié)點的不同方式將導(dǎo)致不同的分支限界法,以下除( C )之外都是最常見的方式.A.隊列式分支限界法 B.優(yōu)先隊列式分支限界法C.棧式分支限界法 D.FIFO分支限界法二、 填空題 1.算法的復(fù)雜性有 時間 復(fù)雜性和 空間 復(fù)雜性之分。2、程序是 算法     用某種程序設(shè)計語言的具體實

23、現(xiàn)。3、算法的“確定性”指的是組成算法的每條 指令 是清晰的，無歧義的。4.矩陣連乘問題的算法可由 動態(tài)規(guī)劃 設(shè)計實現(xiàn)。5、拉斯維加斯算法找到的解一定是 正確解。6、算法是指解決問題的 一種方法 或 一個過程 。7、從分治法的一般設(shè)計模式可以看出，用它設(shè)計出的程序一般是 遞歸算法 。8、問題的 最優(yōu)子結(jié)構(gòu)性質(zhì) 是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。9、以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 回溯法 。10、數(shù)值概率算法常用于 數(shù)值問題 的求解。11、計算一個算法時間復(fù)雜度通?？梢杂嬎?循環(huán)次數(shù) 、 基本操作的頻率 或計算步。12、利用概率的性質(zhì)計算近似值的隨機算法是_數(shù)值概率算法，

24、運行時以一定的概率得到正確解的隨機算法是_蒙特卡羅算法_。14、解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是 動態(tài)規(guī)劃 ，需要排序的是 回溯法 ，分支限界法 。15、使用回溯法進行狀態(tài)空間樹裁剪分支時一般有兩個標準：約束條件和目標函數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標函數(shù)的界進行裁剪的是 0/1背包問題 ，只使用約束條件進行裁剪的是 N皇后問題 。16、 貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。17、矩陣連乘問題的算法可由 動態(tài)規(guī)劃 設(shè)計實現(xiàn)。18、拉斯維加斯算法找到的解一定

25、是 正確解。19.貪心算法的基本要素是 貪心選擇 質(zhì)和 最優(yōu)子結(jié)構(gòu) 性質(zhì) 。21. 動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干 子問題 ，先求解 子問題 ，然后從這些 子問題 的解得到原問題的解。22.算法是由若干條指令組成的有窮序列，且要滿足輸入、 輸出 、確定性和 有限性 四條性質(zhì)。23、大整數(shù)乘積算法是用 分治法 來設(shè)計的。24、以廣度優(yōu)先或以最小耗費方式搜索問題解的算法稱為 分支限界法 。25、舍伍德算法總能求得問題的 一個解 。26、 貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。27.快速排序算法是基于 分治策略 的一種排序算法。28.動態(tài)

26、規(guī)劃算法的兩個基本要素是. 最優(yōu)子結(jié)構(gòu) 性質(zhì)和 重疊子問題 性質(zhì) 。 30.回溯法是一種既帶有 系統(tǒng)性 又帶有 跳躍性 的搜索算法。 31.分支限界法主要有 隊列式（FIFO） 分支限界法和 優(yōu)先隊列式 分支限界法。32分支限界法是一種既帶有 系統(tǒng)性 又帶有 跳躍性 的搜索算法。33回溯法搜索解空間樹時，常用的兩種剪枝函數(shù)為 約束函數(shù) 和 限界函數(shù) 。34.任何可用計算機求解的問題所需的時間都與其 規(guī)模 有關(guān)。35.快速排序算法的性能取決于 劃分的對稱性 。36. Prim算法利用 貪心 策略求解 最小生成樹 問題，其時間復(fù)雜度是 O(n2) 。37. 圖的m著色問題可用 回溯 法求解，其解空

27、間樹中葉子結(jié)點個數(shù)是 mn ，解空間樹中每個內(nèi)結(jié)點的孩子數(shù)是 m 。三、算法填空1.背包問題的貪心算法void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; for (i=1;i<=n;i+) xi=0; float c=M; for (i=1;i<=n;i+) if (wi>c) break; xi=1; c - =wi; if (i<=n) xi=c/wi;2.最大子段和: 動態(tài)規(guī)劃算法int MaxSum(int n, int a) int sum=0, b=0； /sum存

28、儲當前最大的bj, b存儲bj for(int j=1； j<=n； j+) if (b>0) b+= aj ； else b=ai; ； /一旦某個區(qū)段和為負，則從下一個位置累和 if(b>sum) sum=b; return sum； 3.快速排序template<class Type>void QuickSort (Type a, int p, int r) if (p<r) int q=Partition(a,p,r); QuickSort (a,p,q-1); /對左半段排序 QuickSort (a,q+1,r); /對右半段排序 4.排列問題T

29、emplate <class Type>void perm(Type list, int k, int m ) /產(chǎn)生listk:m的所有排列 if(k=m) /只剩下一個元素 for (int i=0;i<=m;i+) cout<<listi; cout<<endl; else /還有多個元素待排列，遞歸產(chǎn)生排列 for (int i=k; i<=m; i+) swap(listk，listi); perm(list,k+1;m); swap(listk,listi); 5.給定已按升序排好序的n個元素a0:n-1，現(xiàn)要在這n個元素中找出一特定

30、元素x。 據(jù)此容易設(shè)計出二分搜索算法：template<class Type> int BinarySearch(Type a, const Type& x, int l, int r) while (l<=r ) int m = (l+r)/2); if (x = am) return m; if (x < am) r = m-1; else l = m+1; return -1; 6、合并排序描述如下：template<class Type>void Mergesort(Type a , int left, int right)if (left&

31、lt;right)int i=( left+right)/2;Mergesort(a, left, i );Mergesort(a, i+1, right);Merge(a,b, left,i,right);/合并到數(shù)組bCopy(a,b, left,right ); /復(fù)制到數(shù)組a 7、以下是計算xm的值的過程int power ( x, m )/計算xm的值并返回。y=( 1 );i=m;While(i- - >0) y=y*x; (return y) 四、問答題1.用計算機求解問題的步驟：1、問題分析2、數(shù)學(xué)模型建立3、算法設(shè)計與選擇4、算法指標5、算法分析6、算法實現(xiàn)7

32、、程序調(diào)試8、結(jié)果整理文檔編制2. 算法定義：算法是指在解決問題時，按照某種機械步驟一定可以得到問題結(jié)果的處理過程3.算法的三要素1、操作2、控制結(jié)構(gòu)3、數(shù)據(jù)結(jié)構(gòu)4. 算法具有以下5個屬性：有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。確定性：算法中每一條指令必須有確切的含義。不存在二義性。只有一個入口和一個出口可行性：一個算法是可行的就是算法描述的操作是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定對象的集合。輸出：一個算法有一個或多個輸出，這些輸出同輸入有著某些特定關(guān)系的量。5. 算法設(shè)計的質(zhì)量指標：正確性：

33、算法應(yīng)滿足具體問題的需求；可讀性：算法應(yīng)該好讀，以有利于讀者對程序的理解；健壯性：算法應(yīng)具有容錯處理，當輸入為非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。效率與存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般這兩者與問題的規(guī)模有關(guān)。經(jīng)常采用的算法主要有迭代法、分治法、貪婪法、動態(tài)規(guī)劃法、回溯法、分支限界法6. 迭代法: 也稱“輾轉(zhuǎn)法”，是一種不斷用變量的舊值遞推出新值的解決問題的方法。7.利用迭代算法解決問題，需要做好以下三個方面的工作：1)、確定迭代模型。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變

34、量，這個變量就是迭代變量。2)、建立迭代關(guān)系式。所謂迭代關(guān)系式，指如何從變量的前一個值推出其下一個值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通常可以使用遞推或倒推的方法來完成。3)、對迭代過程進行控制。在什么時候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復(fù)執(zhí)行下去。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個確定的值，可以計算出來；另一種是所需的迭代次數(shù)無法確定。對于前一種情況，可以構(gòu)建一個固定次數(shù)的循環(huán)來實現(xiàn)對迭代過程的控制；對于后一種情況，需要進一步分析出用來結(jié)束迭代過程的條件。8.分治法的基本思想是：將一個規(guī)模為n的問題分解為k個

35、規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。9.分治法所能解決的問題一般具有以下幾個特征： （1）該問題的規(guī)?？s小到一定的程度就可以容易地解決； （2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)； （3）利用該問題分解出的子問題的解可以合并為該問題的解； （4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。 10、分治法的基本步驟 分治法在每一層遞歸上都有三個步驟： （1）分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題； （2）解決：若子問題規(guī)模較小

36、而容易被解決則直接解，否則遞歸地解各個子問題； （3）合并：將各個子問題的解合并為原問題的解。11. 動態(tài)規(guī)劃的基本思想前文主要介紹了動態(tài)規(guī)劃的一些理論依據(jù)，我們將前文所說的具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的動態(tài)規(guī)劃稱為標準動態(tài)規(guī)劃，這種標準動態(tài)規(guī)劃是在研究多階段決策問題時推導(dǎo)出來的，具有嚴格的數(shù)學(xué)形式，適合用于理論上的分析。在實際應(yīng)用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃的實質(zhì)是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將

37、問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。由此可知，動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)解。貪心法的當前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的（即不包含公共的子問題），因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。不足之處：如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優(yōu)解；如果各子問題是不獨立的，則分

38、治法要做許多不必要的工作，重復(fù)地解公共的子問題。解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)（最大或最?。┲档慕?。若存在若干個取最優(yōu)值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優(yōu)解，但與分治法和貪心法不同的是，動態(tài)規(guī)劃允許這些子問題不獨立，（亦即各子問題可包含公共的子問題）也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結(jié)果保存起來，避免每次碰到時都要重復(fù)計算。因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重

39、復(fù)。動態(tài)規(guī)劃法的關(guān)鍵就在于，對于重復(fù)出現(xiàn)的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。12、動態(tài)規(guī)劃算法的基本步驟設(shè)計一個標準的動態(tài)規(guī)劃算法，通常可按以下幾個步驟進行：（1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的（即無后向性），否則問題就無法用動態(tài)規(guī)劃求解。 （2）選擇狀態(tài)：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當然，狀態(tài)的選擇要滿足無后效性。 （3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階

40、段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來了。但事實上，我們常常是反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決策。 （4）寫出規(guī)劃方程（包括邊界條件）：動態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達式。一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡單的。動態(tài)規(guī)劃的主要難點在于理論上的設(shè)計，一旦設(shè)計完成，實現(xiàn)部分就會非常簡單。根據(jù)動態(tài)規(guī)劃的基本方程可以直接遞歸計算最優(yōu)值，但是一般將其改為遞推計算。實際應(yīng)用當中經(jīng)常不顯式地按照上面步驟設(shè)計動態(tài)規(guī)劃，而是按以下幾個步驟進行：（1）分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 （2）遞歸地定義最優(yōu)值。

41、 （3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計算出最優(yōu)值。 （4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。 步驟（1）（3）是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省略，若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟（4）。此時，在步驟（3）中計算最優(yōu)值時，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速地構(gòu)造出一個最優(yōu)解?？偨Y(jié)：動態(tài)規(guī)劃實際上就是最優(yōu)化的問題，是指將原問題的大實例等價于同一最優(yōu)化問題的較小實例，自底向上的求解最小實例，并將所求解存放起來，存放的結(jié)果就是為了準備數(shù)據(jù)。與遞歸相比，遞歸是不斷的調(diào)用子程序求解，是自頂向下的調(diào)用

42、和求解。13. 分治法與動態(tài)規(guī)劃法的相同點是：將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。兩者的不同點是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨立的。14. 回溯法      回溯法也稱為試探法，該方法首先暫時放棄關(guān)于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當發(fā)現(xiàn)當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探

43、。如果當前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。15. 分支限界法：這是一種用于求解組合優(yōu)化問題的排除非解的搜索算法。類似于回溯法，分枝定界法在搜索解空間時，也經(jīng)常使用樹形結(jié)構(gòu)來組織解空間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小耗費方法來搜索這些樹。因此，可以很容易比較回溯法與分枝定界法的異同。相對而言，分枝定界算法的解空間比回溯法大得多，因此當內(nèi)存容量有限時，回溯法成功的可能性更大。 算法思想：分枝限界（

44、branch and bound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對E-節(jié)點的擴充方式。每個活節(jié)點有且僅有一次機會變成E-節(jié)點。當一個節(jié)點變?yōu)镋-節(jié)點時，則生成從該節(jié)點移動一步即可到達的所有新節(jié)點。在生成的節(jié)點中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點，其余節(jié)點加入活節(jié)點表，然后從表中選擇一個節(jié)點作為下一個E-節(jié)點。從活節(jié)點表中取出所選擇的節(jié)點并進行擴充，直到找到解或活動表為空，擴充過程才結(jié)束。 有兩種常用的方法可用來選擇下一個E-節(jié)點（雖然也可能存在其他的方法）： 1) 先進先出（F I F O） 即從活節(jié)點表中取出節(jié)點的順序與加入節(jié)點的順序相同，因此活 節(jié)點表的性質(zhì)

45、與隊列相同。 2) （優(yōu)先隊列）最小耗費或最大收益法在這種模式中，每個節(jié)點都有一個對應(yīng)的耗費或收益。如果查找 一個具有最小耗費的解，則活節(jié)點表可用最小堆來建立，下一個E-節(jié)點就是具有最小耗費 的活節(jié)點；如果希望搜索一個具有最大收益的解，則可用最大堆來構(gòu)造活節(jié)點表，下一個 E-節(jié)點是具有最大收益的活節(jié)點16. 分支限界法與回溯法的相同點是：都是一種在問題的解空間樹T中搜索問題解的算法。不同點：（1）求解目標不同； （2）搜索方式不同； （3）對擴展結(jié)點的擴展方式不同； （4）存儲空間的要求不同。17. 分治法所能解決的問題一般具有的幾個特征是：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；

46、 （2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì); （3）利用該問題分解出的子問題的解可以合并為該問題的解； （4）原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。18. 用分支限界法設(shè)計算法的步驟是：(1)針對所給問題，定義問題的解空間（對解進行編碼）； (2)確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解） ； (3)以廣度優(yōu)先或以最小耗費（最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。19. 常見的兩種分支限界法的算法框架：（1）隊列式(FIFO)分支限界法：按照隊列先進先出（FIFO）原則選取下一個節(jié)點為擴展節(jié)點。

47、（2）優(yōu)先隊列式分支限界法：按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點。20. 回溯法中常見的兩類典型的解空間樹是子集樹和排列樹。當所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集樹。這類子集樹通常有2n個葉結(jié)點，遍歷子集樹需O(2n)計算時間 。當所給的問題是確定n個元素滿足某種性質(zhì)的排列時，相應(yīng)的解空間樹稱為排列樹。這類排列樹通常有n!個葉結(jié)點。遍歷排列樹需要O(n!)計算時間。21. 分支限界法的搜索策略是： 在擴展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當前的活結(jié)點表中選擇下一個擴展結(jié)點。為了有效地選擇下一擴展結(jié)點，加速搜索的

48、進程，在每一個活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)函數(shù)值，從當前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。22. 請敘述動態(tài)規(guī)劃算法與貪心算法的異同。共同點：都需要最優(yōu)子結(jié)構(gòu)性質(zhì)，都用來求有優(yōu)化問題。不同點：動態(tài)規(guī)劃：每一步作一個選擇依賴于子問題的解。 貪心方法：每一步作一個選擇不依賴于子問題的解。動態(tài)規(guī)劃方法的條件：子問題的重疊性質(zhì)。 可用貪心方法的條件：最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)。動態(tài)規(guī)劃：自底向上求解； 貪心方法： 自頂向下求解。可用貪心法時，動態(tài)規(guī)劃方法可能不適用； 可用動態(tài)規(guī)劃方法時，貪心法可能不適用。23. 請

49、說明動態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。答：最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問題的最優(yōu)解包含子問題的最優(yōu)解。動態(tài)規(guī)劃方法是自底向上計算各個子問題的最優(yōu)解，即先計算子問題的最優(yōu)解，然后再利用子問題的最優(yōu)解構(gòu)造大問題的最優(yōu)解，因此需要最優(yōu)子結(jié)構(gòu).24. 請說明：(1)優(yōu)先隊列可用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)？(2)優(yōu)先隊列插入算法基本思想？(3)優(yōu)先隊列插入算法時間復(fù)雜度？ 答：（1）堆。 （2）在小根堆中，將元素x插入到堆的末尾，然后將元素x的關(guān)鍵字與其雙親的關(guān)鍵字比較，若元素x的關(guān)鍵字小于其雙親的關(guān)鍵字，則將元素x與其雙親交換，然后再將元素x與其新雙親的關(guān)鍵字相比，直到元素x的關(guān)鍵字大于雙親的關(guān)鍵字，或元素x到根為

50、止。（3）O( log n) 25. 衡量算法時間效率的方法有哪兩種？請敘述。答：有事前分析法和事后分析法兩種。事后分析法：先將算法用程序設(shè)計語言實現(xiàn)，然后度量程序的運行時間。事前分析法：算法的時間效率是問題規(guī)模的函數(shù)，假如，隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和函數(shù)f(n)的增長率相同，則可記作： T(n)=(f(n)稱T(n)為算法的漸進時間復(fù)雜度。簡稱時間復(fù)雜度。26. 在算法復(fù)雜性分析中，O、這三個記號的意義是什么？在忽略常數(shù)因子的情況 下，O、分別提供了算法運行時間的什么界？答：如果存在兩個正常數(shù)c和N0,對于所有的NN0，有|f(N)|C|g(N)|，則記作：f(N)= O(

51、g(N)。這時我們說f(N)的階不高于g(N)的階。若存在兩個正常數(shù)C和自然數(shù)N0，使得當N N0時有|f(N)|C|g(N)|，記為f(N)=(g(N)。這時我們說f(N)的階不低于g(N)的階。如果存在正常數(shù)c1，c2和n0，對于所有的nn0，有c1|g(N)| |f(N)| c2|g(N)| 則記作 f(N)= (g,(N)O、分別提供了算法運行時間的上界、下界、平均27. 概率算法很多算法的每一個計算步驟都是固定的，而概率算法允許算法在執(zhí)行的過程中隨機選擇下一個計算步驟。許多情況下，當算法在執(zhí)行過程中面臨一個選擇時，隨機性選擇常比最優(yōu)選擇省時。因此概率算法可在很大程度上降低算法的復(fù)雜度

52、。 28.概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結(jié)果可能會有相當大的差別。29概率算法大致分為四類:數(shù)值概率算法，蒙特卡羅（Monte Carlo）算法，拉斯維加斯（Las Vegas）算法和舍伍德（Sherwood）算法。 30.數(shù)值概率算法常用于數(shù)值問題的求解。這類算法所得到的往往是近似解。而且近似解的精度隨計算時間的增加不斷提高。在許多情況下，要計算出問題的精確解是不可能或沒有必要的，因此用數(shù)值概率算法可得到相當滿意的解。 31.蒙特卡羅算法用于求問題的準確解。對于許多問題來說，近似解毫無意義。例如

53、，一個判定問題其解為“是”或“否”，二者必居其一，不存在任何近似解答。又如，我們要求一個整數(shù)的因子時所給出的解答必須是準確的，一個整數(shù)的近似因子沒有任何意義。用蒙特卡羅算法能求得問題的一個解，但這個解未必是正確的。求得正確解的概率依賴于算法所用的時間。算法所用的時間越多，得到正確解的概率就越高。蒙特卡羅算法的主要缺點就在于此。一般情況下，無法有效判斷得到的解是否肯定正確。 32.拉斯維加斯算法不會得到不正確的解，一旦用拉斯維加斯算法找到一個解，那么這個解肯定是正確的。但是有時候用拉斯維加斯算法可能找不到解。與蒙特卡羅算法類似。拉斯維加斯算法得到正確解的概率隨著它用的計算時間的增加而提高。對于所

54、求解問題的任一實例，用同一拉斯維加斯算法反復(fù)對該實例求解足夠多次，可使求解失效的概率任意小。 33.舍伍德算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性算法在最壞情況下的計算復(fù)雜性與其在平均情況下的計算復(fù)雜性有較大差別時，可以在這個確定算法中引入隨機性將它改造成一個舍伍德算法，消除或減少問題的好壞實例間的這種差別。舍伍德算法精髓不是避免算法的最壞情況行為，而是設(shè)法消除這種最壞行為與特定實例之間的關(guān)聯(lián)性。舍伍德算法  sherwood algorithm 舍伍德算法 一類概率算法的代稱。此類算法總能給出所求問題的正確的解。.當解決某一問題的確定性算法的平均情形

55、復(fù)雜性比最壞情形復(fù)雜性低得多時，通過引入隨機性來試圖減少甚至消除“好”、“壞”實體之間這種時間上的差別，以期望較小的運行時間。例 . 五、算法設(shè)計與分析題1用動態(tài)規(guī)劃策略求解最長公共子序列問題： （1）給出計算最優(yōu)值的遞歸方程。 （2）給定兩個序列X=B,C,D,A，Y=A,B,C,B，請采用動態(tài)規(guī)劃策略求出其最長公共子序列，要求給出過程。答：(1) (2)0 0 0 00 0 1 1 10 0 1 2 20 0 1 2 20 1 1 2 2 最長公共子序列：2對下列各組函數(shù)f (n) 和g (n)，確定f (n) = O (g (n) 或f (n) =(g (n)或f(n) =(g(n)，并簡要說明理由。(1) f(n)=2n； g(n)=n! (2) f(n)=； g (n)=log n2 (3) f(n)=100； g(n)=log100 (4) f(n)=n3； g