1、.一。選擇題1、二分搜索算法是利用（A）實(shí)現(xiàn)的算法。A、分治策略B 、動(dòng)態(tài)規(guī)劃法C、貪心法D 、回溯法2、下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（A）。A、找出最優(yōu)解的性質(zhì)B 、構(gòu)造最優(yōu)解C 、算出最優(yōu)解D、定義最優(yōu)解3、最大效益優(yōu)先是（A）的一搜索方式。A、分支界限法B 、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法4、在下列算法中有時(shí)找不到問(wèn)題解的是（B）。A、蒙特卡羅算法B 、拉斯維加斯算法C、舍伍德算法D 、數(shù)值概率算法5.回溯法解旅行售貨員問(wèn)題時(shí)的解空間樹(shù)是（B）。A、子集樹(shù)B、排列樹(shù)C、深度優(yōu)先生成樹(shù)D、廣度優(yōu)先生成樹(shù)6下列算法中通常以自底向上的方式求解最優(yōu)解的是（B）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、

2、貪心法D、回溯法7、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C ）。A 運(yùn)行速度快 B 占用空間少 C 時(shí)間復(fù)雜度低 D 代碼短8、以下不可以使用分治法求解的是（D ）。A 棋盤(pán)覆蓋問(wèn)題 B 選擇問(wèn)題 C 歸并排序 D 0/1背包問(wèn)題9.實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（A）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法10、下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是（C ）A 數(shù)值概率算法 B 舍伍德算法 C 拉斯維加斯算法D 蒙特卡羅算法11下面不是分支界限法搜索方式的是（D）。A、廣度優(yōu)先B、最小耗費(fèi)優(yōu)先C、最大效益優(yōu)先D、深度優(yōu)先12 下 列 算 法 中 通 常 以 深 度 優(yōu) 先 方 式 系 統(tǒng)

3、搜 索 問(wèn) 題 解 的 是（D）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法13. 備忘錄方法是那種算法的變形。 （B）.A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法14哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為（B）。A、O（n2n）B、 O（ nlogn ）C、O（2n）D、O（n）15分支限界法解最大團(tuán)問(wèn)題時(shí)， 活結(jié)點(diǎn)表的組織形式是 （B）。A、最小堆B、最大堆C、棧D、數(shù)組16最長(zhǎng)公共子序列算法利用的算法是（B）。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法17實(shí)現(xiàn)棋盤(pán)覆蓋算法利用的算法是（A）。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法18. 下面是貪心算法的基本要素的是（C）。

4、A、重疊子問(wèn)題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、定義最優(yōu)解19. 回溯法的效率不依賴于下列哪些因素（D）A. 滿足顯約束的值的個(gè)數(shù)B.計(jì)算約束函數(shù)的時(shí)間C. 計(jì)算限界函數(shù)的時(shí)間D.確定解空間的時(shí)間20. 下面哪種函數(shù)是回溯法中為避免無(wú)效搜索采取的策略（B）A遞歸函數(shù)B. 剪枝函數(shù)C。隨機(jī)數(shù)函數(shù)D.搜索函數(shù)21、下面關(guān)于 NP問(wèn)題說(shuō)法正確的是（ B ）A NP問(wèn)題都是不可能解決的問(wèn)題B P 類(lèi)問(wèn)題包含在 NP類(lèi)問(wèn)題中C NP完全問(wèn)題是 P 類(lèi)問(wèn)題的子集D NP類(lèi)問(wèn)題包含在 P 類(lèi)問(wèn)題中22、蒙特卡羅算法是（B）的一種。A、分支界限算法B 、概率算法C、貪心算法D 、回溯算法23. 下列哪一種算法

5、不是隨機(jī)化算法（C）A. 蒙特卡羅算法 B. 拉斯維加斯算法 C.動(dòng)態(tài)規(guī)劃算法 D. 舍伍德算法24.（D）是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)。A、重疊子問(wèn)題 B 、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、最優(yōu)子結(jié)構(gòu)性質(zhì)25.矩陣連乘問(wèn)題的算法可由（B）設(shè)計(jì)實(shí)現(xiàn)。.A、分支界限算法B 、動(dòng)態(tài)規(guī)劃算法C 、貪心算法D、回溯算法26. 分 支 限 界 法 解 旅 行 售 貨 員 問(wèn) 題 時(shí) ， 活 結(jié) 點(diǎn) 表 的 組 織 形 式 是（A）。A、最小堆B、最大堆C、棧D、數(shù)組27、Strassen 矩陣乘法是利用（A）實(shí)現(xiàn)的算法。A、分治策略B 、動(dòng)態(tài)規(guī)劃法C、貪心法D 、回溯法29、使用分治法求解不需要滿足的

6、條件是（A ）。A 子問(wèn)題必須是一樣的B 子問(wèn)題不能夠重復(fù)C 子問(wèn)題的解可以合并D 原問(wèn)題和子問(wèn)題使用相同的方法解30、下面問(wèn)題（ B ）不能使用貪心法解決。A 單源最短路徑問(wèn)題B N 皇后問(wèn)題C 最小花費(fèi)生成樹(shù)問(wèn)題D 背包問(wèn)題31、下列算法中不能解決0/1 背包問(wèn)題的是（ A ）A 貪心法 B 動(dòng)態(tài)規(guī)劃 C 回溯法 D 分支限界法32、回溯法搜索狀態(tài)空間樹(shù)是按照（C ）的順序。A 中序遍歷 B 廣度優(yōu)先遍歷 C 深度優(yōu)先遍歷 D 層次優(yōu)先遍歷33、下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是（C ）A 數(shù)值概率算法 B 舍伍德算法 C 拉斯維加斯算法 D蒙特卡羅算法34實(shí)現(xiàn)合并排序利用的算法

7、是（A）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法35下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（D）。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子問(wèn)題重疊性質(zhì)36下列算法中通常以自底向下的方式求解最優(yōu)解的是（B）。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法37采用廣度優(yōu)先策略搜索的算法是（A）。.A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法38、合并排序算法是利用（A）實(shí)現(xiàn)的算法。A、分治策略B 、動(dòng)態(tài)規(guī)劃法C、貪心法D 、回溯法39、在下列算法中得到的解未必正確的是（B）。A、蒙特卡羅算法B 、拉斯維加斯算法C、舍伍德算法概率算法40、背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（B）A、O（n

8、2n）B 、O（nlogn ）C、O（2n）41實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（C）。A、貪心法B、動(dòng)態(tài)規(guī)劃法C、分治策略420-1 背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為（AA、O（n2n）B、O（nlogn ）C、O（ 2n）43采用最大效益優(yōu)先搜索方式的算法是（AA、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法44貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（BA、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解優(yōu)解D 、數(shù)值D、 O（ n）D、回溯法）D、O（n）。D、回溯法）。D、定義最45.實(shí)現(xiàn)最大子段和利用的算法是（B）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法46. 優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則

9、是（C）。A、先進(jìn)先出B、后進(jìn)先出C、結(jié)點(diǎn)的優(yōu)先級(jí)D、隨機(jī)47. 背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（B）。A、O（n2n）B、O（nlogn ）C、O（2n）D、O（n）48、廣度優(yōu)先是（A）的一搜索方式。A、分支界限法B 、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法49、舍伍德算法是（B）的一種。A、分支界限算法B 、概率算法C、貪心算法D 、回溯算法50、在下列算法中有時(shí)找不到問(wèn)題解的是（B）。.A、蒙特卡羅算法B 、拉斯維加斯算法C、舍伍德算法D 、數(shù)值概率算法51 下列哪一種算法是隨機(jī)化算法（D）A. 貪心算法 B. 回溯法 C.動(dòng)態(tài)規(guī)劃算法 D.舍伍德算法52. 一 個(gè)問(wèn) 題可 用動(dòng) 態(tài)規(guī) 劃

10、算 法或 貪心 算法 求解的 關(guān)鍵 特征 是問(wèn) 題的（B）。A、重疊子問(wèn)題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解53采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為( B)。A、O（n2n）B、O（nlogn ）C、O（2n）D、O（n）54. 以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱為( D )。A、分支界限算法B 、概率算法C、貪心算法D 、回溯算法55. 實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是（B）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法56、算法是由若干條指令組成的有窮序列，而且滿足以下性質(zhì)（D）（ 1） 輸入：有 0 個(gè)或多個(gè)輸入（

11、2） 輸出：至少有一個(gè)輸出（ 3） 確定性：指令清晰，無(wú)歧義（ 4） 有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行時(shí)間有限A (1)(2)(3)B(1)(2)(4)C(1)(3)(4)D (1) (2)(3)(4)、函數(shù)nn 的漸進(jìn)表達(dá)式是 ( B ).5732 +10nlogA. 2nB. 32nC. nlognD. 10nlogn58、大整數(shù)乘法算法是 (A).算法A. 分治 B.貪心 C.動(dòng)態(tài)規(guī)劃D.窮舉59、用動(dòng)態(tài)規(guī)劃算法解決最大字段和問(wèn)題，其時(shí)間復(fù)雜性為( B).A.lognB.nC.n2D.nlogn60、解決活動(dòng)安排問(wèn)題，最好用（B）算法A. 分治 B.貪心 C.動(dòng)態(tài)規(guī)劃D.窮舉.61、設(shè)

12、 f(N),g(N) 是定義在正數(shù)集上的正函數(shù),如果存在正的常數(shù)C 和自然數(shù) N0,使得當(dāng) NN0 時(shí)有f(N)則稱函數(shù)f(N)當(dāng)N充分大時(shí)有下界g(N),記作Cg(N),f(N) (g(N), 即 f(N) 的階 ( A)g(N) 的階 .A. 不高于 B.不低于 C.等價(jià)于 D.逼近62、回溯法在解空間樹(shù) T 上的搜索方式是 ( A).A. 深度優(yōu)先B.廣度優(yōu)先C.最小耗費(fèi)優(yōu)先D. 活結(jié)點(diǎn)優(yōu)先63、回溯算法和分支限界法的問(wèn)題的解空間樹(shù)不會(huì)是(D).A. 有序樹(shù) B.子集樹(shù) C.排列樹(shù) D.無(wú)序樹(shù)64、在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中,一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是 ( B).A.

13、 回溯法 B.分支限界法 C.回溯法和分支限界法D.回溯法求解子集樹(shù)問(wèn)題65、從活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的不同方式將導(dǎo)致不同的分支限界法 ,以下除 ( C )之外都是最常見(jiàn)的方式 .A. 隊(duì)列式分支限界法B.優(yōu)先隊(duì)列式分支限界法C.棧式分支限界法D.FIFO 分支限界法二、 填空題1. 算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。2、程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。3、算法的“確定性”指的是組成算法的每條指令是清晰的，無(wú)歧義的。4. 矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃設(shè)計(jì)實(shí)現(xiàn)。5、拉斯維加斯算法找到的解一定是正確解。6、算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。7、從分治法的一般設(shè)計(jì)模式可以

14、看出，用它設(shè)計(jì)出的程序一般是遞歸算法。8、問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。.9、以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱為回溯法。10、數(shù)值概率算法常用于數(shù)值問(wèn)題的求解。11、計(jì)算一個(gè)算法時(shí)間復(fù)雜度通?？梢杂?jì)算循環(huán)次數(shù)、基本操作的頻率或計(jì)算步。12、利用概率的性質(zhì)計(jì)算近似值的隨機(jī)算法是 _數(shù)值概率算法，運(yùn)行時(shí)以一定的概率得到正確解的隨機(jī)算法是 _蒙特卡羅算法 _。14、解決 0/1 背包問(wèn)題可以使用動(dòng)態(tài)規(guī)劃、回溯法和分支限界法， 其中不需要排序的是動(dòng)態(tài)規(guī)劃，需要排序的是回溯法，分支限界法。15、使用回溯法進(jìn)行狀態(tài)空間樹(shù)裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函

15、數(shù)的界， N 皇后問(wèn)題和 0/1 背包問(wèn)題正好是兩種不同的類(lèi)型，其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是0/1背包問(wèn)題，只使用約束條件進(jìn)行裁剪的是 N 皇后問(wèn)題。16、 貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素， 也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。17、矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃設(shè)計(jì)實(shí)現(xiàn)。18、拉斯維加斯算法找到的解一定是正確解。19. 貪心 算法 的 基 本要 素 是貪心 選 擇質(zhì) 和最 優(yōu)子 結(jié) 構(gòu)性質(zhì) 。21. 動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干子問(wèn)題，先求解 子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。22. 算法是由若干條指令組成的有窮序列，且要滿足輸入、

16、輸出、確定性和有限性四條性質(zhì)。23、大整數(shù)乘積算法是用分治法來(lái)設(shè)計(jì)的。24、以廣度優(yōu)先或以最小耗費(fèi)方式搜索問(wèn)題解的算法稱為分支限界法。25、舍伍德算法總能求得問(wèn)題的一個(gè)解。26、貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。27. 快速排序算法是基于分治策略的一種排序算法。.28.動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是 .最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問(wèn)題性質(zhì) 。30. 回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。31.分支限界法主要有隊(duì)列式（ FIFO）分支限界法和優(yōu)先隊(duì)列式分支限界法。32分支限界法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。33回溯法搜索解空間樹(shù)時(shí)，

17、常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。34.任何可用計(jì)算機(jī)求解的問(wèn)題所需的時(shí)間都與其規(guī)模有關(guān)。35.快速排序算法的性能取決于劃分的對(duì)稱性 。36.Prim 算法利用貪心策略求解最小生成樹(shù)問(wèn)題，其時(shí)間復(fù)雜度是O(n2)。37. 圖的 m 著色問(wèn)題可用 回溯法求解，其解空間樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)是mn，解空間樹(shù)中每個(gè)內(nèi)結(jié)點(diǎn)的孩子數(shù)是m。三、算法填空1. 背包問(wèn)題的貪心算法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;ic) br

18、eak;xi=1;c - =wi;.if (i=n) xi=c/wi;2. 最大子段和 : 動(dòng)態(tài)規(guī)劃算法int MaxSum(int n, int a)int sum=0, b=0；/sum存儲(chǔ)當(dāng)前最大的bj, b存儲(chǔ) bjfor(int j=1； j0) b+= aj；else b=ai;；/一旦某個(gè)區(qū)段和為負(fù)， 則從下一個(gè)位置累和if(bsum) sum=b;return sum；3. 快速排序templatevoidQuickSort (Type a, int p, int r)if (pr) int q=Partition(a,p,r);QuickSort (a,p,q-1); /對(duì)左

19、半段排序QuickSort (a,q+1,r); /對(duì)右半段排序4. 排列問(wèn)題Template void perm(Type list, int k, int m ). /產(chǎn)生 listk:m的所有排列if(k=m) /只剩下一個(gè)元素for (int i=0;i=m;i+) coutlisti;coutendl;else /還有多個(gè)元素待排列，遞歸產(chǎn)生排列for (int i=k; i=m; i+)sk，listi);perm(list,k+1;m);sk,listi);5. 給定已按升序排好序的 n 個(gè)元素 a0:n-1，現(xiàn)要在這 n 個(gè)元素中找出一特定元素 x。據(jù)此容易設(shè)計(jì)出二分搜索算法：

20、templateint 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.void Mergesort(Type a , int left, int right)if ( left0)y=y*x;(return y) ;四、問(wèn)答題1.用計(jì)算機(jī)求解問(wèn)題的步驟：1、問(wèn)題分析 2、數(shù)學(xué)模型建立 3、算法設(shè)計(jì)與選擇4、算法指標(biāo) 5、

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

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

23、問(wèn)題中， 至少存在一個(gè)直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。2) 、建立迭代關(guān)系式。 所謂迭代關(guān)系式， 指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問(wèn)題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來(lái)完成。.3) 、對(duì)迭代過(guò)程進(jìn)行控制。 在什么時(shí)候結(jié)束迭代過(guò)程？這是編寫(xiě)迭代程序必須考慮的問(wèn)題。 不能讓迭代過(guò)程無(wú)休止地重復(fù)執(zhí)行下去。 迭代過(guò)程的控制通?？煞譃閮煞N情況： 一種是所需的迭代次數(shù)是個(gè)確定的值， 可以計(jì)算出來(lái)； 另一種是所需的迭代次數(shù)無(wú)法確定。 對(duì)于前一種情況， 可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來(lái)實(shí)現(xiàn)對(duì)迭代過(guò)程的控制； 對(duì)于后一種情況， 需要進(jìn)

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

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

26、優(yōu)解（即滿足最優(yōu)子化原理） ，則可以考慮用動(dòng)態(tài)規(guī)劃解決。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是 分治思想 和解決冗余 ，因此，動(dòng)態(tài)規(guī)劃 是一種將問(wèn)題實(shí)例分解為更小的、 相似的子問(wèn)題， 并存儲(chǔ)子問(wèn)題的解而避免計(jì)算重復(fù)的子問(wèn)題， 以解決最優(yōu)化問(wèn)題的算法策略。由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類(lèi)似，它們都是將問(wèn)題實(shí)例歸納為更小的、相似的子問(wèn)題，并通過(guò)求解子問(wèn)題產(chǎn)生一個(gè)全局最優(yōu)解。貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇， 但不依賴于有待于做出的選擇和子問(wèn)題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個(gè)子問(wèn)題是獨(dú)立的（即不包含公共的子問(wèn)題） ，因此一旦遞歸地求出各子問(wèn)題的解后，便可自下而上地將子問(wèn)題的

27、解合并成問(wèn)題的解。不足之處：如果當(dāng)前選擇可能要依賴子問(wèn)題的解時(shí)，則難以通過(guò)局部的貪心策略達(dá)到全局最優(yōu)解； 如果各子問(wèn)題是不獨(dú)立的， 則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題。解決上述問(wèn)題的辦法是利用動(dòng)態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問(wèn)題，這類(lèi)問(wèn)題會(huì)有多種可能的解， 每個(gè)解都有一個(gè)值， 而動(dòng)態(tài)規(guī)劃找出其中最優(yōu) （最大或最?。┲档慕?。若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過(guò)程中，該方法也是通過(guò)求解局部子問(wèn)題的解達(dá)到全局最優(yōu)解， 但與分治法和貪心法不同的是，動(dòng)態(tài)規(guī)劃允許這些子問(wèn)題不獨(dú)立， （亦即各子問(wèn)題可包含公共的子問(wèn)題）也允許其通過(guò)自身子問(wèn)題的解作出選擇， 該方法對(duì)每一個(gè)子

28、問(wèn)題只解一次，并將結(jié)果保存起來(lái)，避免每次碰到時(shí)都要重復(fù)計(jì)算。因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問(wèn)題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問(wèn)題樹(shù)中的子問(wèn)題呈現(xiàn)大量的重復(fù)。 動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于， 對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到時(shí)加以求解， 并把答案保存起來(lái)， 讓以后再遇到時(shí)直接引用， 不必重新求解。.12、動(dòng)態(tài)規(guī)劃算法的基本步驟設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法，通?？砂匆韵聨讉€(gè)步驟進(jìn)行：（ 1）劃分階段：按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題分為若干個(gè)階段。注意這若干個(gè)階段一定要是有序的或者是可排序的（即無(wú)后向性） ，否則問(wèn)題就無(wú)法用動(dòng)態(tài)規(guī)劃求解。（ 2）選擇狀態(tài)：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的

29、狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿足無(wú)后效性。（ 3）確定決策并寫(xiě)出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系， 狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策， 狀態(tài)轉(zhuǎn)移方程也就寫(xiě)出來(lái)了。 但事實(shí)上，我們常常是反過(guò)來(lái)做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來(lái)確定決策。（ 4）寫(xiě)出規(guī)劃方程 （包括邊界條件）：動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。一般說(shuō)來(lái)，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡(jiǎn)單的。動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)， 一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。根據(jù)動(dòng)態(tài)規(guī)劃的基本方程可以直接遞歸計(jì)算最

30、優(yōu)值，但是一般將其改為遞推計(jì)算。實(shí)際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計(jì)動(dòng)態(tài)規(guī)劃， 而是按以下幾個(gè)步驟進(jìn)行：（ 1）分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。（ 2）遞歸地定義最優(yōu)值。（ 3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計(jì)算出最優(yōu)值。（ 4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。步驟（ 1）（ 3）是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省略，若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟（ 4）。此時(shí)，在步驟（ 3）中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟（ 4）中，根據(jù)所記錄的信息，快速地構(gòu)造出一個(gè)最優(yōu)解?？偨Y(jié)：動(dòng)態(tài)規(guī)劃實(shí)際上就是最優(yōu)化的

31、問(wèn)題，是指將原問(wèn)題的大實(shí)例等價(jià)于同一最優(yōu)化問(wèn)題的較小實(shí)例， 自底向上的求解最小實(shí)例， 并將所求解存放起來(lái)， 存放的結(jié)果就是為了準(zhǔn)備數(shù)據(jù)。 與遞歸相比， 遞歸是不斷的調(diào)用子程序求解， 是自.頂向下的調(diào)用和求解。13. 分治法與動(dòng)態(tài)規(guī)劃法的相同點(diǎn)是：將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。兩者的不同點(diǎn)是 ：適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。 而用分治法求解的問(wèn)題， 經(jīng)分解得到的子問(wèn)題往往是互相獨(dú)立的。14. 回溯法回溯法也稱為試探法，該方法首先暫時(shí)放棄關(guān)于問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候選解按某種順序逐一枚舉和檢驗(yàn)。 當(dāng)

32、發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí)， 就選擇下一個(gè)候選解； 倘若當(dāng)前候選解除了還不滿足問(wèn)題規(guī)模要求外， 滿足所有其他要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模， 并繼續(xù)試探。 如果當(dāng)前候選解滿足包括問(wèn)題規(guī)模在內(nèi)的所有要求時(shí)， 該候選解就是問(wèn)題的一個(gè)解。 在回溯法中， 放棄當(dāng)前候選解，尋找下一個(gè)候選解的過(guò)程稱為回溯。 擴(kuò)大當(dāng)前候選解的規(guī)模， 以繼續(xù)試探的過(guò)程稱為向前試探。15. 分支限界法：這是一種用于求解組合優(yōu)化問(wèn)題的排除非解的搜索算法。類(lèi)似于回溯法，分枝定界法在搜索解空間時(shí)， 也經(jīng)常使用樹(shù)形結(jié)構(gòu)來(lái)組織解空間。 然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹(shù)結(jié)構(gòu)， 而分枝定界一般用寬度優(yōu)先或最小耗費(fèi)方法來(lái)

33、搜索這些樹(shù)。 因此，可以很容易比較回溯法與分枝定界法的異同。相對(duì)而言，分枝定界算法的解空間比回溯法大得多， 因此當(dāng)內(nèi)存容量有限時(shí)， 回溯法成功的可能性更大。算法思想：分枝限界（branch and bound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對(duì) E-節(jié)點(diǎn)的擴(kuò)充方式。每個(gè)活節(jié)點(diǎn)有且僅有一次機(jī)會(huì)變成 E-節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)變?yōu)?E-節(jié)點(diǎn)時(shí)，則生成從該節(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所有新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表，然后從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè) E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充， 直到找到解或活動(dòng)表為空， 擴(kuò)充過(guò)

34、程才結(jié).束。有兩種常用的方法可用來(lái)選擇下一個(gè)E-節(jié)點(diǎn)（雖然也可能存在其他的方法） ：1) 先進(jìn)先出（F I F O） 即從活節(jié)點(diǎn)表中取出節(jié)點(diǎn)的順序與加入節(jié)點(diǎn)的順序相同，因此活節(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。2) （優(yōu)先隊(duì)列）最小耗費(fèi)或最大收益法在這種模式中，每個(gè)節(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的耗費(fèi)或收益。如果查找 一個(gè)具有最小耗費(fèi)的解，則活節(jié)點(diǎn)表可用最小堆來(lái)建立，下一個(gè) E-節(jié)點(diǎn)就是具有最小耗費(fèi) 的活節(jié)點(diǎn)；如果希望搜索一個(gè)具有最大收益的解，則可用最大堆來(lái)構(gòu)造活節(jié)點(diǎn)表，下一個(gè)E-節(jié)點(diǎn)是具有最大收益的活節(jié)點(diǎn)16. 分支限界法與回溯法的相同點(diǎn)是： 都是一種在問(wèn)題的解空間樹(shù) T 中搜索問(wèn)題解的算法。不同點(diǎn)：（1）求解目標(biāo)不

35、同；（2）搜索方式不同；（3）對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同；（4）存儲(chǔ)空間的要求不同。17. 分治法所能解決的問(wèn)題一般具有的幾個(gè)特征是：（1）該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決；（2）該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì) ;（3）利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；（ 4）原問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。18. 用分支限界法設(shè)計(jì)算法的步驟是：(1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間（對(duì)解進(jìn)行編碼）；(2)確定易于搜索的解空間結(jié)構(gòu)（按樹(shù)或圖組織解）；(3)以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間

36、，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。.19. 常見(jiàn)的兩種分支限界法的算法框架：（ 1）隊(duì)列式 (FIFO) 分支限界法：按照隊(duì)列先進(jìn)先出（ FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。（ 2）優(yōu)先隊(duì)列式分支限界法： 按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。20. 回溯法中常見(jiàn)的兩類(lèi)典型的解空間樹(shù)是子集樹(shù)和排列樹(shù)。當(dāng)所給的問(wèn)題是從 n 個(gè)元素的集合 S 中找出滿足某種性質(zhì)的子集時(shí)， 相應(yīng)的解空間樹(shù)稱為子集樹(shù)。這類(lèi)子集樹(shù)通常有2n 個(gè)葉結(jié)點(diǎn)，遍歷子集樹(shù)需O(2n)計(jì)算時(shí)間。當(dāng)所給的問(wèn)題是確定 n 個(gè)元素滿足某種性質(zhì)的排列時(shí)， 相應(yīng)的解空間樹(shù)稱為排列樹(shù)。這類(lèi)排列樹(shù)通常有 n!

37、個(gè)葉結(jié)點(diǎn)。遍歷排列樹(shù)需要 O(n!)計(jì)算時(shí)間。21. 分支限界法的搜索策略是：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)（分支） ，然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)。 為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)， 加速搜索的進(jìn)程， 在每一個(gè)活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值（限界） ，并根據(jù)函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。22. 請(qǐng)敘述動(dòng)態(tài)規(guī)劃算法與貪心算法的異同。共同點(diǎn)：都需要最優(yōu)子結(jié)構(gòu)性質(zhì)，都用來(lái)求有優(yōu)化問(wèn)題。不同點(diǎn)：動(dòng)態(tài)規(guī)劃：每一步作一個(gè)選擇依賴于子問(wèn)題的解。貪心方法：每一步作一個(gè)選擇不依賴于子問(wèn)題的解 。動(dòng)態(tài)規(guī)劃方法的

38、條件：子問(wèn)題的重疊性質(zhì)?？捎秘澬姆椒ǖ臈l件：最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)。動(dòng)態(tài)規(guī)劃：自底向上求解；貪心方法： 自頂向下求解。.可用貪心法時(shí)，動(dòng)態(tài)規(guī)劃方法可能不適用；可用動(dòng)態(tài)規(guī)劃方法時(shí)，貪心法可能不適用。23. 請(qǐng)說(shuō)明動(dòng)態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。答：最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問(wèn)題的最優(yōu)解包含子問(wèn)題的最優(yōu)解。動(dòng)態(tài)規(guī)劃方法是自底向上計(jì)算各個(gè)子問(wèn)題的最優(yōu)解，即先計(jì)算子問(wèn)題的最優(yōu)解，然后再利用子問(wèn)題的最優(yōu)解構(gòu)造大問(wèn)題的最優(yōu)解， 因此需要最優(yōu)子結(jié)構(gòu) .24. 請(qǐng)說(shuō)明：(1) 優(yōu)先隊(duì)列可用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)？(2) 優(yōu)先隊(duì)列插入算法基本思想？(3) 優(yōu)先隊(duì)列插入算法時(shí)間復(fù)雜度？答：（1）堆。（2）在小根堆

39、中，將元素 x 插入到堆的末尾，然后將元素 x 的關(guān)鍵字與其雙親的關(guān)鍵字比較，若元素 x 的關(guān)鍵字小于其雙親的關(guān)鍵字，則將元素 x 與其雙親交換，然后再將元素 x 與其新雙親的關(guān)鍵字相比，直到元素 x 的關(guān)鍵字大于雙親的關(guān)鍵字，或元素 x 到根為止。（3）O( log n)25. 衡量算法時(shí)間效率的方法有哪兩種？請(qǐng)敘述。答：有事前分析法和事后分析法兩種。事后分析法：先將算法用程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)，然后度量程序的運(yùn)行時(shí)間。事前分析法：算法的時(shí)間效率是問(wèn)題規(guī)模的函數(shù)， 假如，隨著問(wèn)題規(guī)模 n 的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和函數(shù) f(n) 的增長(zhǎng)率相同，則可記作：T(n)= (f(n)稱 T(n)為算法

40、的漸進(jìn)時(shí)間復(fù)雜度。簡(jiǎn)稱時(shí)間復(fù)雜度。26. 在算法復(fù)雜性分析中， O、這三個(gè)記號(hào)的意義是什么？在忽略常數(shù)因子的情況下， O、分別提供了算法運(yùn)行時(shí)間的什么界？.答：如果存在兩個(gè)正常數(shù)c 和 N0,對(duì)于所有的 NN0，有 |f(N)|C|g(N)|，則記作：f(N)=O(g(N)。這時(shí)我們說(shuō)f(N)的階不高于 g(N)的階。若存在兩個(gè)正常數(shù)C 和自然數(shù) N0，使得當(dāng) N N0 時(shí)有 |f(N)|C|g(N)|，記為f(N)=?( g(N)。這時(shí)我們說(shuō)f(N)的階不低于 g(N)的階。如果存在正常數(shù)c1，c2 和 n0，對(duì)于所有的 nn0，有 c1|g(N)| |f(N)| c2|g(N)|則記作f(

41、N)=(g,(N)O、分別提供了算法運(yùn)行時(shí)間的上界、下界、平均27. 概率算法很多算法的每一個(gè)計(jì)算步驟都是固定的，而概率算法允許算法在執(zhí)行的過(guò)程中隨機(jī)選擇下一個(gè)計(jì)算步驟。許多情況下，當(dāng)算法在執(zhí)行過(guò)程中面臨一個(gè)選擇時(shí)，隨機(jī)性選擇常比最優(yōu)選擇省時(shí)。因此概率算法可在很大程度上降低算法的復(fù)雜度。28. 概率算法的一個(gè)基本特征是對(duì)所求解問(wèn)題的同一實(shí)例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問(wèn)題所需的時(shí)間甚至所得到的結(jié)果可能會(huì)有相當(dāng)大的差別。29概率算法大致分為四類(lèi):數(shù)值概率算法， 蒙特卡羅 （ Monte Carlo ）算法，拉斯維加斯 （ Las Vegas）算法和舍伍德（ Sherw

42、ood ）算法。30. 數(shù)值概率算法常用于數(shù)值問(wèn)題的求解。這類(lèi)算法所得到的往往是近似解。而且近似解的精度隨計(jì)算時(shí)間的增加不斷提高。在許多情況下，要計(jì)算出問(wèn)題的精確解是不可能或沒(méi)有必要的，因此用數(shù)值概率算法可得到相當(dāng)滿意的解。31. 蒙特卡羅算法用于求問(wèn)題的準(zhǔn)確解。對(duì)于許多問(wèn)題來(lái)說(shuō)，近似解毫無(wú)意義。例如，一個(gè)判定問(wèn)題其解為“是”或“否”，二者必居其一，不存在任何近似解答。又如，我們要求一個(gè)整數(shù)的因子時(shí)所給出的解答必須是準(zhǔn)確的，一個(gè)整數(shù)的近似因子沒(méi)有任何意義。用蒙特卡羅算法能求得問(wèn)題的一個(gè)解，但這個(gè)解未必是正確的。求得正確解的概率依賴于算法所用的時(shí)間。算法所用的.時(shí)間越多，得到正確解的概率就越高。

43、蒙特卡羅算法的主要缺點(diǎn)就在于此。一般情況下，無(wú)法有效判斷得到的解是否肯定正確。32. 拉斯維加斯算法不會(huì)得到不正確的解，一旦用拉斯維加斯算法找到一個(gè)解，那么這個(gè)解肯定是正確的。但是有時(shí)候用拉斯維加斯算法可能找不到解。與蒙特卡羅算法類(lèi)似。拉斯維加斯算法得到正確解的概率隨著它用的計(jì)算時(shí)間的增加而提高。對(duì)于所求解問(wèn)題的任一實(shí)例，用同一拉斯維加斯算法反復(fù)對(duì)該實(shí)例求解足夠多次，可使求解失效的概率任意小。33. 舍伍德算法總能求得問(wèn)題的一個(gè)解，且所求得的解總是正確的。當(dāng)一個(gè)確定性算法在最壞情況下的計(jì)算復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有較大差別時(shí)，可以在這個(gè)確定算法中引入隨機(jī)性將它改造成一個(gè)舍伍德算法，消

44、除或減少問(wèn)題的好壞實(shí)例間的這種差別。舍伍德算法精髓不是避免算法的最壞情況行為，而是設(shè)法消除這種最壞行為與特定實(shí)例之間的關(guān)聯(lián)性。舍伍德算法sherwood algorithm舍伍德算法一類(lèi)概率算法的代稱。 此類(lèi)算法總能給出所求問(wèn)題的正確的解。.當(dāng)解決某一問(wèn)題的確定性算法的平均情形復(fù)雜性比最壞情形復(fù)雜性低得多時(shí)，通過(guò)引入隨機(jī)性來(lái)試圖減少甚至消除“好”、“壞”實(shí)體之間這種時(shí)間上的差別，以期望較小的運(yùn)行時(shí)間。例 .五、算法設(shè)計(jì)與分析題1用動(dòng)態(tài)規(guī)劃策略求解最長(zhǎng)公共子序列問(wèn)題：（ 1）給出計(jì)算最優(yōu)值的遞歸方程。（ 2）給定兩個(gè)序列 X=B,C,D,A ，Y=A,B,C,B ，請(qǐng)采用動(dòng)態(tài)規(guī)劃策略求出其最長(zhǎng)公共子序列，要求給出過(guò)程。答：(1).0當(dāng)i 0或j 0時(shí)ci, jci1,