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

1、文檔編碼 : CU4V1W8F9T8 HP1C8K8N9V9 ZQ2U6W1W4B8一；選擇題1、二分搜尋 算法是利用（ A ）實現(xiàn)的算法；A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法2、以下 不是動態(tài)規(guī)劃算法 基本步驟的是（ B ）；A、找出最優(yōu)解的性質(zhì)B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、定義最優(yōu)解3、最大效益優(yōu)先 是（ A ）的一搜尋方式；A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法4、在以下算法中有時找不到問題解的是（B ）；A、蒙特卡羅算法 B、拉斯維加斯算法 C、舍伍德算法 D、數(shù)值概率算法5. 回溯法解旅行售貨員問題時的 解空間樹 是（B ）；A、子集樹 B、排列樹 C、深

2、度優(yōu)先生成樹 D、廣度優(yōu)先生成樹6以下算法中通常以 自底向上 的方式求解最優(yōu)解的是（ B ）；A、備忘錄法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法7、衡量一個算法好壞的標(biāo)準(zhǔn)是（C ）；A 運行速度快 B 占用空間少 C 時間復(fù)雜度低 D 代碼短8、以下 不行以 使用分治法 求解的是（ D ）；A 棋盤掩蓋問題B 選擇問題C 歸并排序D 0/1 背包問題9. 實現(xiàn) 循環(huán)賽日程表 利用的算法是（ A ）；A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法10、以下隨機算法中運行時有時候成功有時候失敗的是（C ）A 數(shù)值概率算法 B 舍伍德算法 C 拉斯維加斯算法 D 蒙特卡羅算法11下面不是分支

3、界限法搜尋方式的是（D ）；A、廣度優(yōu)先 B、最小耗費優(yōu)先 C、最大效益優(yōu)先 D、深度優(yōu)先12以下算法中通常以深度優(yōu)先方式系統(tǒng)搜尋問題解的是（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 ）；D 、 數(shù)A、最小堆B、最大堆C、棧組16最長公共子序列算法利用的算法是（B ）；D、回溯法A、分支界限法B、動態(tài)規(guī)劃法C、貪

4、心法17實現(xiàn)棋盤掩蓋算法利用的算法是（A ）；D、回溯法A、分治法B、動態(tài)規(guī)劃法C、貪心法18.下面是 貪心算法 的基本要素的是（ C ）；A、重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、定義最優(yōu)解19.回溯法的效率不依靠于以下哪些因素（D ）A.中意顯約束的值的個數(shù) C. 運算限界函數(shù)的時間B. 運算約束函數(shù)的時間 D. 確定解空間的時間20.下面哪種函數(shù)是回溯法中為防止無效搜尋實行的策略（B ）D.搜尋函數(shù)A遞歸函數(shù)B.剪枝函數(shù)C；隨機數(shù)函數(shù)21、下面關(guān)于 NP 問題說法正確選項（ B ）A NP問題都是不行能解決的問題 B P類問題包含在 NP類問題中 C NP完全問題是 P 類問題的子

5、集 D NP類問題包含在 P 類問題中 22、蒙特卡羅算法 是（B ）的一種；A、分支界限算法B、概率算法C、貪心算法D、回溯算法23.以下哪一種算法不是 隨機化算法 （C ）A. 蒙特卡羅算法 B. 拉斯維加斯算法C.動態(tài)規(guī)劃算法 D.舍伍德算法24. （D ）是貪心算法與動態(tài)規(guī)劃算法的共同點；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、棧 D、數(shù)組27、Stras

6、sen矩陣乘法 是利用（ 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 背包問題 的是（ A ）A 貪心法 B 動態(tài)規(guī)劃 C 回溯法 D 分支限界法32、回溯法搜尋狀態(tài)空間樹是依據(jù)（C ）的次序；A 中序遍歷 B 廣度優(yōu)先遍歷 C 深度優(yōu)先遍歷 D 層次優(yōu)先遍歷33、以下隨機算法

7、中運行時有時候成功有時候失敗的是（C ）A 數(shù)值概率算法 B 舍伍德算法 C 拉斯維加斯算法 D 蒙特卡羅算法34實現(xiàn) 合并排序利用 的算法是（ A ）；A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法35以下 不是動態(tài)規(guī)劃算法基本要素的是（D ）；D、子問題A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解重疊性質(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 ）實現(xiàn)的算法；A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法

8、D、回溯法39、在以下算法中得到的解未必正確選項（B ）；A、蒙特卡羅算法 B、拉斯維加斯算法 C、舍伍德算法 D、數(shù)值概率算法40、背包問題 的貪心算法所需的運算時間為（B ）A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）41實現(xiàn)大整數(shù)的乘法是利用的算法（C ）；C、分治策略D、回溯法A、貪心法B、動態(tài)規(guī)劃法420-1 背包問題的 回溯算法 所需的運算時間為（ A ）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）43接受最大效益優(yōu)先搜尋方式的算法是（A ）；D、回溯法A、分支界限法B、動態(tài)規(guī)劃法C、貪心法44貪心算法與動態(tài)規(guī)劃算法的主要區(qū)分是（B ）；D

9、、定義最A(yù)、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解優(yōu)解45. 實現(xiàn)最 大子段和利用 的算法是（ B ）；A、分治策略B、動態(tài)規(guī)劃法C、貪心法D、回溯法46.優(yōu)先隊列式分支限界法 選取 擴展結(jié)點 的原就是（ C ）；A、先進先出B、后進先出C、結(jié)點的優(yōu)先級D、隨機47.背包問題的貪心算法所需的運算時間為（B ）；D、O（n）A、O（n2n）B、O（nlogn）C、O（2n）48、廣度優(yōu)先是（ A ）的一搜尋方式；A、分支界限法B、動態(tài)規(guī)劃法C、貪心法 D、回溯法49、舍伍德算法是（ B ）的一種；A、分支界限算法 B、概率算法 C、貪心算法 D、回溯算法50、在以下算法中有時找不到問題解的是（

10、B ）；A、蒙特卡羅算法 B、拉斯維加斯算法 C、舍伍德算法 D、數(shù)值概率算法51 以下哪一種算法是隨機化算法（D ）A. 貪心算法 B. 回溯法 C.動態(tài)規(guī)劃算法 D.舍伍德算法52. 一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特點是問題的（B ）；A、重疊子問題 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

11、. 實現(xiàn)最長公共子序列 利用的算法是（ B ）；A、分治策略B、動態(tài)規(guī)劃法C、貪心法D D、回溯法56、算法是由如干條指令組成的有窮序列,而且中意以下性質(zhì)（）（1） 輸入：有 0 個或多個輸入（2） 輸出：至少有一個輸出（3） 確定性：指令清晰,無歧義（4） 有限性：指令執(zhí)行次數(shù)有限,而且執(zhí)行時間有限A 123 B124 C134 D 1 234 B . 57、函數(shù) 32n+10nlogn的漸進表達式是 B . A. 2nB. 32nC. nlognD. 10nlogn58、大整數(shù)乘法算法是 A .算法A.分治 B.貪心 C.動態(tài)規(guī)劃D.窮舉59、用動態(tài)規(guī)劃 算法解決最大字段和問題,其時間復(fù)雜

12、性為60、解決 活動支配 問題,最好用（ B ）算法A.分治 B.貪心 C.動態(tài)規(guī)劃 D.窮舉61、設(shè) fN,gN是定義在正數(shù)集上的正函數(shù) ,假如存在正的常數(shù) C和自然數(shù) N0,使得當(dāng) NN0 時有 fN CgN, 就稱函數(shù) fN當(dāng) N 充分大時有下界 gN,記作fN gN,即 fN的階 A gN的階 . A.不高于 B.不低于 C.等價于 D.靠近62、回溯法在解空間樹 T 上的搜尋方式是 A . A.深度優(yōu)先 B.廣度優(yōu)先 C.最小耗費優(yōu)先 D.活結(jié)點優(yōu)先63、回溯算法和分支限界法的問題的解空間樹不會是 D . A.有序樹 B.子集樹 C.排列樹 D.無序樹64、在對問題的解空間樹進行搜尋

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

14、指解決問題的 一種方法 或 一個過程；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ù)值概率算法, 運行時以確定的概率得到正確解的隨機算法是_蒙特卡羅算法 _；14、解決 0/1 背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法,其中不需要排序的是 動態(tài)規(guī)劃,需要排序的是 回溯法,分支

15、限界法；15、使用回溯法進行狀態(tài)空間樹裁剪分支時一般有兩個標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界, N 皇后問題和 0/1 背包問題正好是兩種不同的類型,其中 同時使用約束條件和目標(biāo)函數(shù) 的界進行裁剪的是 0/1 背包問題,只使用約束條件 進行裁剪的是 N 皇后問題；16、貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素,也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)分；17、矩陣連乘問題的算法可由 動態(tài)規(guī)劃 設(shè)計實現(xiàn)；18、拉斯維加斯算法找到的解確定是 正確解；19. 貪 心 算 法 的 基 本 要 素 是 貪 心 選 擇 質(zhì) 和 最 優(yōu) 子 結(jié) 構(gòu)性質(zhì) ；21. 動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成如干 子問

16、題,先求解 子問題,然后從這些 子問題 的解得到原問題的解；22.算法是由如干條指令組成的有窮序列,且要中意輸入、輸出、確定性 和 有限性 四條性質(zhì)；23、大整數(shù)乘積算法是用 分治法 來設(shè)計的；24、以廣度優(yōu)先或以最小耗費方式搜尋問題解的算法稱為 分支限界法；25、舍伍德算法 總能求得問題的 一個解；26、貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素,也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)分；27.快速排序算法是基于分治策略的一種排序算法；性質(zhì)和28.動態(tài)規(guī)劃算法的兩個基本要素是. 最優(yōu)子結(jié)構(gòu)重疊子問題性質(zhì) ；又帶有跳動性30.回溯法是一種既帶有系統(tǒng)性的搜尋算法；31.分支限界法主要有隊列式（ F

17、IFO）又帶有分支限界法和優(yōu)先隊列式分支限界法；跳動性的32分支限界法是一種既帶有系統(tǒng)性搜尋算法；33回溯法搜尋解空間樹時,常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)；規(guī)模有關(guān)；34.任何可用運算機求解的問題所需的時間都與其35.快速排序算法的性能取決于 劃分的對稱性；36. Prim 算法利用 貪心 策略求解 最小生成樹 問題,其時間復(fù)雜度 是 On2 ；37. 圖的 m 著色問題可用 回溯 法求解,其解空間樹中葉子結(jié)點個數(shù)是,解空間樹中每個內(nèi)結(jié)點的孩子數(shù)是 m ；mn 三、算法填空 1.背包問題的貪心算法 void Knapsackint n,float M,float v,float w,f

18、loat x So rtn,v,w; int i; for i=1;i=n;i+ xi=0; float c=M; for i=1;ic break; xi=1; c - =wi; if i=n xi=c/wi ; 2.最大子段和 : 動態(tài)規(guī)劃算法 int MaxSumint n, int a int sum=0, b=0；速排序 template void QuickSort Type a, int p, int r if pr int q=Partitiona,p,r;QuickSort a,p,q-1; 列問題 Template void permType list, int k, in

19、t m 定已按升序排好序的 n 個元素 a0:n-1,現(xiàn)要在這 n 個元素中找出一特定元素 x；據(jù)此簡潔設(shè)計出二分搜尋算法：template int BinarySearchType 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 r = m+1; return -1; 6、合并排序描述如下：template void MergesortType a , int left, int right if leftright int i= left+ri

20、ght/2; Mergesorta, left, i ; Mergesorta, i+1, right; Mergea,b, left,i,right;運算機求解問題的步驟：1、問題分析 2、數(shù)學(xué)模型建立 3、算法設(shè)計與選擇 4、算法指標(biāo) 5、算法分析 6、算法實現(xiàn) 7、程序調(diào)試 8、結(jié)果整理文檔編制 2. 算法定義：算法是指在解決問題時,依據(jù)某種機械步驟確定可以得到問題結(jié)果的處理過 程3.算法的三要素 1、操作 2、把握結(jié)構(gòu) 3、數(shù)據(jù)結(jié)構(gòu) 4. 算法具有以下 5 個屬性 ：有窮性：一個算法必需總是在執(zhí)行有窮步之后終止,內(nèi)完成；且每一步都在有窮時間確定性：算法中每一條指令必需有精確的含義；不存

21、在二義性； 只有一個入 口和一個出口 可行性：一個算法是可行的就是算法描述的操作是可以通過已經(jīng)實現(xiàn)的基本 運算執(zhí)行有限次來實現(xiàn)的；輸入：一個算法有零個或多個輸入,這些輸入取自于某個特定對象的集合；輸出：一個算法有一個或多個輸出, 這些輸出同輸入有著某些特定關(guān)系的量；5. 算法設(shè)計的質(zhì)量指標(biāo)：正確性：算法應(yīng)中意具體問題的需求；可讀性：算法應(yīng)當(dāng)好讀,以有利于讀者對程序的懂得；健壯性：算法應(yīng)具有容錯處理, 當(dāng)輸入為非法數(shù)據(jù)時, 算法應(yīng)對其作出反應(yīng),而不是產(chǎn)生莫名其妙的輸出結(jié)果；效率與儲備量需求： 效率指的是算法執(zhí)行的時間； 儲備量需求指算法執(zhí)行過 程中所需要的最大儲備空間；一般這兩者與問題的規(guī)模有關(guān)

22、；經(jīng)常接受的算法主要有迭代法、分治法、貪婪法、動態(tài)規(guī)劃法、回溯法、分支 限界法6. 迭代法 : 也稱“ 輾轉(zhuǎn)法” ,是一種不斷用變量的舊值遞推出新值的解決問題的方法；7.利用迭代算法解決問題,需要做好以下三個方面的工作：1、確定迭代模型；在可以用迭代算法解決的問題中,至少存在一個直接或 間接地不斷由舊值遞推出新值的變量,這個變量就是迭代變量；2、建立迭代關(guān)系式；所謂迭代關(guān)系式,指如何從變量的前一個值推出其下 一個值的公式（或關(guān)系）；迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵,通?？梢允褂眠f推或倒推的方法來完成；3、對迭代過程進行把握；在什么時候終止迭代過程這是編寫迭代程序必需考慮的問題； 不能讓迭代

23、過程無休止地重復(fù)執(zhí)行下去；為兩種情形： 一種是所需的迭代次數(shù)是個確定的值,迭代過程的把握通?？煞?可以運算出來； 另一種是所需的迭代次數(shù)無法確定； 對于前一種情形, 可以構(gòu)建一個固定次數(shù)的循環(huán)來實現(xiàn) 對迭代過程的把握； 對于后一種情形, 需要進一步分析出用來終止迭代過程的條 件；8.分治法的基本思想是：將一個規(guī)模為 n 的問題分解為 k 個規(guī)模較小的子問題,這些子問題相互獨立 且與原問題相同； 遞歸地解這些子問題, 然后將各個子問題的解合并得到原問題 的解；9.分治法所能解決的問題一般具有以下幾個特點：（1）該問題的規(guī)?？s小到確定的程度就可以簡潔地解決；（2）該問題可以分解為如干個規(guī)模較小的相

24、同問題,即該問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì)；（3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）該問題所分解出的各個子問題是相互獨立的,即子問題之間不 包含公共的子子問題；10、分治法的基本步驟 分治法在每一層遞歸上都有三個步驟：（1）分解：將原問題分解為如干個規(guī)模較小,相互獨立,與原問題 形式相同的子問題；（2）解決：如子問題規(guī)模較小而簡潔被解決就直接解,否就遞歸地 解各個子問題；（3）合并：將各個子問題的解合并為原問題的解；11. 動態(tài)規(guī)劃的基本思想前文主要介紹了動態(tài)規(guī)劃的一些理論依據(jù),我們將前文所說的具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的動態(tài)規(guī)劃稱為 標(biāo)準(zhǔn)動態(tài)規(guī)劃 ,這種標(biāo)準(zhǔn)動態(tài)規(guī)劃是在

25、研 究多階段決策問題時推導(dǎo)出來的, 具有嚴(yán)格的數(shù)學(xué)形式, 適合用于理論上的分析；在實際應(yīng)用中, 許多問題的階段劃分并不明顯, 這時假如刻意地劃分階段法反而 麻煩；一般來說, 只要該問題可以劃分成規(guī)模更小的子問題,并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即中意最優(yōu)子化原理）決；,就可以考慮用動態(tài)規(guī)劃解動態(tài)規(guī)劃的實質(zhì)是 分治思想 和解決冗余 ,因此,動態(tài)規(guī)劃 是一種將問題實例 分解為更小的、 相像的子問題, 并儲備子問題的解而防止運算重復(fù)的子問題,以 解決最優(yōu)化問題的算法策略；由此可知,動態(tài)規(guī)劃法與分治法和貪心法類似,它們都是將問題實例歸納為 更小的、相像的子問題,并通過求解子問題產(chǎn)生一個全局最

26、優(yōu)解；貪心法的當(dāng)前選擇可能要依靠已經(jīng)作出的全部選擇,但不依靠于有待于做出的選擇和子問題；因此貪心法自頂向下,一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的（即不包含公共的子問題）,因此一旦遞歸地 求出各子問題的解后,便可自下而上地將子問題的解合并成問題的解；不足之處：假如當(dāng)前選擇可能要依靠子問題的解時,就難以通過局部的貪心 策略達到全局最優(yōu)解； 假如各子問題是不獨立的, 就分治法要做許多不必要的工 作,重復(fù)地解公共的子問題；解決上述問題的方法是利用動態(tài)規(guī)劃；該方法主要應(yīng)用于最優(yōu)化問題,這類 問題會有多種可能的解, 每個解都有一個值, 而動態(tài)規(guī)劃找出其中最優(yōu) （最大或 最?。┲档慕猓蝗绱?/p>

27、在如干個取最優(yōu)值的解的話,它只取其中的一個；在求解過程中,該方法也是通過求解局部子問題的解達到全局最優(yōu)解,但與分治法和貪心法不同的是,動態(tài)規(guī)劃答應(yīng)這些子問題不獨立,問題）也答應(yīng)其通過自身子問題的解作出選擇,（亦即各子問題可包含公共的子 該方法對每一個子問題只解一次,并將結(jié)果儲存起來,防止每次遇到時都要重復(fù)運算；因此,動態(tài)規(guī)劃法所針對的問題有一個顯著的特點,即它所對應(yīng)的子問題樹 中的子問題顯現(xiàn)大量的重復(fù)； 動態(tài)規(guī)劃法的關(guān)鍵就在于, 對于重復(fù)顯現(xiàn)的子問題,只在第一次遇到時加以求解, 并把答案儲存起來, 讓以后再遇到時直接引用, 不 必重新求解；12、動態(tài)規(guī)劃算法的基本步驟 設(shè)計一個標(biāo)準(zhǔn)的動態(tài)規(guī)劃算

28、法,通?？砂匆韵聨讉€步驟進行：（1）劃分階段：依據(jù)問題的時間或空間特點,把問題分為如干個階段；留意這 如干個階段確定要是有序的或者是可排序的（即無后向性）,否就問題就無法用 動態(tài)規(guī)劃求解；（2）選擇狀態(tài)：將問題進展到各個階段時所處于的各種客觀情形用不同的狀態(tài) 表示出來；當(dāng)然,狀態(tài)的選擇要中意無后效性；（3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起,是由于決策和 狀態(tài)轉(zhuǎn)移有著自然的聯(lián)系, 狀態(tài)轉(zhuǎn)移就是依據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階 段的狀態(tài)； 所以,假如我們確定了決策, 狀態(tài)轉(zhuǎn)移方程也就寫出來了； 但事實上,我們經(jīng)常是反過來做,依據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決策；（4）寫出規(guī)

29、劃方程 （包括邊界條件）：動態(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)用當(dāng)中經(jīng)常不顯式地依據(jù)上面步驟設(shè)計動態(tài)規(guī)劃,而是按以下幾個步 驟進行：（1）分析最優(yōu)解的性質(zhì),并刻劃其結(jié)構(gòu)特點；（2）遞歸地定義最優(yōu)值；（3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）運算出最優(yōu)值；（4）依據(jù)運算最優(yōu)值時得到的信息,構(gòu)造一個最優(yōu)解；步驟（1）（3）是動態(tài)規(guī)劃算法的基本步驟；在

30、只需要求出最優(yōu)值的情形,步 驟（4）可以省略,如需要求出問題的一個最優(yōu)解,就必需執(zhí)行步驟（4）；此時,在步驟（ 3）中運算最優(yōu)值時,通常需記錄更多的信息,以便在步驟（4）中,根 據(jù)所記錄的信息,快速地構(gòu)造出一個最優(yōu)解；總結(jié)：動態(tài)規(guī)劃實際上就是最優(yōu)化的問題,是指將原問題的大實例等價于同 一最優(yōu)化問題的較小實例, 自底向上的求解最小實例, 并將所求解存放起來, 存 放的結(jié)果就是為了預(yù)備數(shù)據(jù)； 與遞歸相比, 遞歸是不斷的調(diào)用子程序求解,是自 頂向下的調(diào)用和求解；13. 分治法與動態(tài)規(guī)劃法的相同點是：將待求解的問題分解成如干個子問題,先求解子問題,然后從這些子問題的 解得到原問題的解；兩者的不同點是

31、：適合于用動態(tài)規(guī)劃法求解的問題,經(jīng)分解得到的子問題往 往不是相互獨立的； 而用分治法求解的問題, 經(jīng)分解得到的子問題往往是相互獨 立的；14. 回溯法 回溯法也稱為摸索法,該方法第一暫時舍棄關(guān)于問題規(guī)模大小的限制,并將問 題的候選解按某種次序逐一枚舉和檢驗；當(dāng)發(fā)覺當(dāng)前候選解不行能是解時,就選 擇下一個候選解； 假如當(dāng)前候選解除了仍不中意問題規(guī)模要求外,中意全部其他要求時,連續(xù)擴大當(dāng)前候選解的規(guī)模,并連續(xù)摸索； 假如當(dāng)前候選解中意包括問題規(guī)模在內(nèi)的全部要求時, 該候選解就是問題的一個解；在回溯法中, 舍棄當(dāng)前候選解,查找下一個候選解的過程稱為回溯；探的過程稱為向前摸索；15. 分支限界法：擴大當(dāng)

32、前候選解的規(guī)模, 以連續(xù)試這是一種用于求解組合優(yōu)化問題的排除非解的搜尋算法；類似于回溯法,分 枝定界法在搜尋解空間時, 也經(jīng)常使用樹形結(jié)構(gòu)來組織解空間；然而與回溯法不同的是,回溯算法使用深度優(yōu)先方法搜尋樹結(jié)構(gòu),而分枝定界一般用寬度優(yōu)先或最小耗費方法來搜尋這些樹； 因此,可以很簡潔比較回溯法與分枝定界法的異同；相對而言, 分枝定界算法的解空間比回溯法大得多,溯法成功的可能性更大；因此當(dāng)內(nèi)存容量有限時, 回算法思想： 分枝限界（ branch and bound）是另一種系統(tǒng)地搜尋解空間的方法,它與回溯法的主要區(qū)分在于對E-節(jié)點的擴充方式； 每個活節(jié)點有且僅有一次機會變成 E-節(jié)點；當(dāng)一個節(jié)點變?yōu)?/p>

33、 E-節(jié)點時,就生成從該節(jié)點移動一步即可到達的全部新節(jié)點；在生成的節(jié)點中,拋棄那些不行能導(dǎo)出（最優(yōu)）可行解的節(jié)點,其余節(jié)點加入活節(jié)點表, 然后從表中選擇一個節(jié)點作為下一個 E-節(jié)點；從活節(jié)點 表中取出所選擇的節(jié)點并進行擴充, 直到找到解或活動表為空, 擴充過程才終止；有兩種常用的方法可用來選擇下一個E-節(jié)點（雖然也可能存在其他的方法） ：1 先進先出 （F I F O） 即從活節(jié)點表中取出節(jié)點的次序與加入節(jié)點的次序相同,因此活 節(jié)點表的性質(zhì)與隊列相同；2 （優(yōu)先隊列）最小耗費或最大收益法在這種模式中,每個節(jié)點都有一個對應(yīng)的耗費或收益；假如查找一個具有最小耗費的解,就活節(jié)點表可用最小堆來建立,下

34、一個 E-節(jié)點就是具有最小耗費 的活節(jié)點；假如期望搜尋一個具有最大收益的解,就可用最大堆來構(gòu)造活節(jié)點表,下一個 點E-節(jié)點是具有最大收益的活節(jié)16. 分支限界法與回溯法的相同點是：都是一種在問題的解空間樹T 中搜尋問題解的算法；不同點：（1）求解目標(biāo)不同；（2）搜尋方式不同；（3）對擴展結(jié)點的擴展方式不同；（4）儲備空間的要求不同；17. 分治法所能解決的問題一般具有的幾個特點是：（1）該問題的規(guī)模縮小到確定的程度就可以簡潔地解決；（2）該問題可以分解為如干個規(guī)模較小的相同問題,即該問題具有最優(yōu)子 結(jié)構(gòu)性質(zhì) ; （3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）原問題所分解出的各個

35、子問題是相互獨立的,的子問題；18. 用分支限界法設(shè)運算法的步驟是：即子問題之間不包含公共1針對所給問題,定義問題的解空間（對解進行編碼）；2確定易于搜尋的解空間結(jié)構(gòu)（按樹或圖組織解）；3以廣度優(yōu)先或以最小耗費（最大收益）優(yōu)先的方式搜尋解空間,并在搜尋 過程中用剪枝函數(shù)防止無效搜尋；19. 常見的兩種分支限界法的算法框架：（1）隊列式 FIFO分支限界法：依據(jù)隊列先進先出（節(jié)點為擴展節(jié)點；FIFO）原就選取下一個（2）優(yōu)先隊列式分支限界法： 依據(jù)優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高 的節(jié)點成為當(dāng)前擴展節(jié)點；20. 回溯法中常見的兩類典型的解空間樹是子集樹和排列樹；當(dāng)所給的問題是從n 個元素的集

36、合 S中找出中意某種性質(zhì)的子集時, 相應(yīng)的解空間樹稱為子集樹；這類子集樹通常有2n 個葉結(jié)點,遍歷子集樹需O2n運算時間；當(dāng)所給的問題是確定n 個元素中意某種性質(zhì)的排列時, 相應(yīng)的解空間樹稱為排列樹；這類排列樹通常有n.個葉結(jié)點；遍歷排列樹需要On.運算時間；21. 分支限界法的搜尋策略是：在擴展結(jié)點處,先生成其全部的兒子結(jié)點（分支）,然后再從當(dāng)前的活結(jié)點表中選擇下一個擴展結(jié)點； 為了有效地選擇下一擴展結(jié)點,加速搜尋的進程, 在每一個活結(jié)點處,運算一個函數(shù)值（限界）,并依據(jù)函數(shù)值,從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點,使搜尋朝著解空間上有最優(yōu)解的分支推 進,以便盡快地找出一個最優(yōu)解

37、；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. 請說明動態(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) 解,然后再利用

38、子問題的最優(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 到根為止；（3）O log n25. 衡量算法時間效率的方法有哪兩種請表達；答：有事前分析法和事后分析法兩種；事后分析法：先將算法用程序設(shè)計語言實現(xiàn),然后度量程序的運行時間

39、；事前分析法：算法的時間效率是問題規(guī)模的函數(shù), 假如,隨著問題規(guī)模 n 的增長,算法執(zhí)行時間的增長率和函數(shù)fn的增長率相同,就可記作：Tn= fn稱 Tn為算法的漸進時間復(fù)雜度；簡稱時間復(fù)雜度；26. 在算法復(fù)雜性分析中,O、 、 這三個記號的意義是什么在忽視常數(shù)因子的情形下, O、 、 分別供應(yīng)了算法運行時間的什么界答：假如存在兩個正常數(shù) c 和 N0,對于全部的 NN0,有| fN| C| gN| ,就記作：fN= OgN；這時我們說 fN的階不高于 gN的階；如存在兩個正常數(shù) C 和自然數(shù) N0,使得當(dāng) N N0 時有 | fN| C| gN| ,記為fN=gN；這時我們說 fN的階不低

40、于 gN的階；假如存在正常數(shù)c1,c2 和 n0,對于全部的nn0,有 c1|gN| |fN| c2|gN|就記作fN= g,NO、 、 分別供應(yīng)了算法運行時間的上界、下界、平均27. 概率算法許多算法的每一個運算步驟都是固定的,而概率算法答應(yīng)算法 在執(zhí)行的過程中隨機選擇下一個運算步驟；許多情形下,當(dāng)算法在執(zhí)行過 程中面臨一個選擇時,隨機性選擇常比最優(yōu)選擇省時；因此概率算法可在 很大程度上降低算法的復(fù)雜度；28.概率算法的一個基本特點 是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不 同的成效；這兩次求解問題所需的時間甚至所得到的結(jié)果可能會有相當(dāng)大 的差別；29概率算法大致分為四類

41、 : 數(shù)值概率算法,蒙特卡羅（Monte Carlo ）算法,拉斯維加斯（Las Vegas）算法和舍伍德（Sherwood ）算法；30.數(shù)值概率算法 常用于數(shù)值問題的求解；這類算法所得到的往往是近似解；而且近似 解的精度隨運算時間的增加不斷提高；在許多情形下,要運算出問題的精 確解是不行能或沒有必要的,因此用數(shù)值概率算法可得到相當(dāng)中意的解；31.蒙特卡羅算法用于求問題的精確解；對于許多問題來說,近似解毫無意義；例如,一個判定問題其解為“是” 或“否”,二者必居其一, 不存在任何近似解答；又如,我們要求一個整數(shù)的因子時所給出的解答必需是精確的,一個整數(shù)的近似 因子沒有任何意義；用蒙特卡羅算法

42、能求得問題的一個解,但這個解未必 是正確的；求得正確解的概率依靠于算法所用的時間；算法所用的時間越 多,得到正確解的概率就越高；蒙特卡羅算法的主要缺點就在于此；一般 情形下,無法有效判定得到的解是否確定正確；32.拉斯維加斯算法 不會得到不正確的解,一旦用拉斯維加斯算法找到一個解,那么這個解 確定是正確的；但是有時候用拉斯維加斯算法可能找不到解；與蒙特卡羅 算法類似；拉斯維加斯算法得到正確解的概率隨著它用的運算時間的增加 而提高；對于所求解問題的任一實例,用同一拉斯維加斯算法反復(fù)對該實 例求解足夠多次,可使求解失效的概率任意?。?3.舍伍德算法 總能求得問題的一個解,且所求得的解總是正確的；當(dāng)

43、一個確定性算法 在最壞情形下的運算復(fù)雜性與其在平均情形下的運算復(fù)雜性有較大差別 時,可以在這個確定算法中引入隨機性將它改造成一個舍伍德算法,排除 或削減問題的好壞實例間的這種差別；舍伍德算法精髓不是防止算法的最 壞情形行為,而是設(shè)法排除這種最壞行為與特定實例之間的關(guān)聯(lián)性；舍伍德算法 sherwood algorithm 舍伍德算法 一類概率算法的代稱；此類算法總能給出所求問題的正確的解；. 當(dāng)解決某一問題的確定性算法的平均情形復(fù)雜性比最壞情形復(fù)雜性低得多時,通 過引入隨機性來試圖削減甚至排除“ 好” 、“ 壞” 實體之間這種時間上的差別,以期望較小的運行時間；例 . 五、算法設(shè)計與分析題1用動

44、態(tài)規(guī)劃策略求解最長公共子序列問題：（1）給出運算最優(yōu)值的遞歸方程；（2）給定兩個序列 X=B,C,D,A,Y=A,B,C,B,請接受動態(tài)規(guī)劃策略求出其最長公共子序列,要求給出過程；答：1 ci,j0jj11ci1,j當(dāng)i0或j0時iyi時i時ci1,當(dāng)i,j0且ximaxci,1,y當(dāng)i,j0且x2 0 0 0 0 0 0 1 1 1 0 0 1 2 2 0 0 1 2 2 0 1 1 2 2 最長公共子序列：2對以下各組函數(shù) f n 和 g n,確定 f n = O g n 或 f n = g n或 fn =gn,并簡要說明理由；1 fn=2n；gn=n. 2 fn= n ；g n=log n23 fn=100；gn=log100 4 fn=n3；gn= 3n5 fn=3 n；gn=2n答：1 fn = Ogn 2 fn = gn 3 fn = gn 4 fn = Ogn 5 fn = gn 由于 gn的階比 fn的階高；由于 gn的階比 fn的階低；由于 gn與 fn同階；由于 gn的階比 fn的階高；由于 gn的階比 fn的階低；3對下圖所示的連通