太原理工大學(xué)軟件學(xué)院算法設(shè)計(jì)與分析復(fù)習(xí)題目及答案

1、太原理工大學(xué)軟件學(xué)院算法設(shè) 計(jì)與分析復(fù)習(xí)題目及答案、選擇題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. 回溯法解旅行售貨員問(wèn)題時(shí)的解空間樹(shù)是（B ） 。A、子集樹(shù)B、排列機(jī)tC、深度優(yōu)先生成樹(shù)D廣度優(yōu)先生成樹(shù)5下列算法中通常以自底向上的方式求解最優(yōu)解的是（B ） 。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法 D回溯法6、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C ）

2、 。A 運(yùn)行速度快B 占用空間少C 時(shí)間復(fù)雜度低D 代碼短7、以下不可以使用分治法求解的是（D ） 。A 棋盤(pán)覆蓋問(wèn)題B 選擇問(wèn)題C 歸并排序D 0/1 背包問(wèn)題8. 實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（A ） 。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法9下面不是分支界限法搜索方式的是（D ） 。A、廣度優(yōu)先 R最小耗費(fèi)優(yōu)先C、最大效益優(yōu)先D深度優(yōu)先10下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的是（D ） 。A、備忘錄法R動(dòng)態(tài)規(guī)劃法C、貪心法 D回溯法11. 備忘錄方法是那種算法的變形。（ B ）B ）。C、貪心法D回溯法A ）。C、貪心法D回溯法C ）。A、分治法 R動(dòng)態(tài)規(guī)劃法C、貪心法 D

3、回溯法 12最長(zhǎng)公共子序列算法利用的算法是（A、分支界BM法R動(dòng)態(tài)規(guī)劃法13實(shí)現(xiàn)棋盤(pán)覆蓋算法利用的算法是（A、分治法R動(dòng)態(tài)規(guī)劃法14. 下面是貪心算法的基本要素的是（A、重疊子問(wèn)題 R構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D定義最優(yōu)解15. 回溯法的效率不依賴(lài)于下列哪些因素（D ）A. 滿(mǎn)足顯約束的值的個(gè)數(shù)B. 計(jì)算約束函數(shù)的時(shí)間C. 計(jì)算限界函數(shù)的時(shí)間D. 確定解空間的時(shí)間16. 下面哪種函數(shù)是回溯法中為避免無(wú)效搜索采取的策略（B ）A.遞歸函數(shù)B.剪枝函數(shù)C.隨機(jī)數(shù)函數(shù)D.搜索函數(shù)17. （ 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ì)18. 矩

4、陣連乘問(wèn)題的算法可由（B）設(shè)計(jì)實(shí)現(xiàn)。A分支界BM算法B、動(dòng)態(tài)規(guī)劃算法G貪心算法D、回溯算法19. 分支限界法解旅行售貨員問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是（A ） 。A、最小堆 R最大堆 C棧 D數(shù)組20. Strassen 矩陣乘法是利用（A ）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法21、使用分治法求解不需要滿(mǎn)足的條件是（A ） 。A 子問(wèn)題必須是一樣的B 子問(wèn)題不能夠重復(fù)C 子問(wèn)題的解可以合并D 原問(wèn)題和子問(wèn)題使用相同的方法解22、下面問(wèn)題（B ）不能使用貪心法解決。A 單源最短路徑問(wèn)題B N 皇后問(wèn)題C 最小花費(fèi)生成樹(shù)問(wèn)題D 背包問(wèn)題23、下列算法中不能解決0/1 背包

5、問(wèn)題的是（A ）A 貪心法 B 動(dòng)態(tài)規(guī)劃C 回溯法 D 分支限界法24、回溯法搜索狀態(tài)空間樹(shù)是按照（C ）的順序。A 中序遍歷B 廣度優(yōu)先遍歷C 深度優(yōu)先遍歷D 層次優(yōu)先遍歷25實(shí)現(xiàn)合并排序利用的算法是（A ） 。A、分治策略 R動(dòng)態(tài)規(guī)劃法C、貪心法 D回溯法26下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（D ） 。A、定義最優(yōu)解 R構(gòu)造最優(yōu)解C、算出最優(yōu)解D子問(wèn)題重疊性質(zhì)27下列算法中通常以自底向下的方式求解最優(yōu)解的是（B ）。A、分1B法B、動(dòng)態(tài)規(guī)劃法C、貪心法 D回溯法28采用廣度優(yōu)先策略搜索的算法是（A ） 。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法 D回溯法29、合并排序算法是利用（A ）實(shí)現(xiàn)的算

6、法。A、分治策略B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法30、背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（B ）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）31實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（C ） 。A、貪心法 R動(dòng)態(tài)規(guī)劃法C、分治策H&D回溯法32 0-1 背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為（A ）A、O（n2n）B、O（nlogn ）C、O（2n）D、O（n）33采用最大效益優(yōu)先搜索方式的算法是（A ） 。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法 D回溯法34貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（B ） 。A、最優(yōu)子2構(gòu) R貪心選擇Tt質(zhì)G構(gòu)造最優(yōu)解D定義最優(yōu)解35. 優(yōu)先隊(duì)列式分支限

7、界法選取擴(kuò)展結(jié)點(diǎn)的原則是（C ） 。A、先進(jìn)先出 R后進(jìn)先出 C結(jié)點(diǎn)的優(yōu)先級(jí)D隨機(jī)36. 背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為（B ） 。A、O（n2n）B、O（nlogn ）C、O（2n）D、O（n）37、廣度優(yōu)先是（A ）的搜索方式。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法 D、回溯法38. 一個(gè)問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問(wèn)題的（B ） 。A、重疊子問(wèn)題R最優(yōu)子結(jié)構(gòu)性質(zhì)G貪心選擇性質(zhì)D定義最優(yōu)解39采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為（B ） 。A、O（n2n）B、O（nlogn ）C、O（2n）D、O（n）40. 以

8、深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為（ D ）。A、分支界限算法R概率算法C、貪心算法D、回溯算法41. 實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是(A、分治策略B、動(dòng)態(tài)規(guī)劃法C貪心法 D回溯法42、算法是由若干條指令組成的有窮序列，而且滿(mǎn)足以下性質(zhì)(D)(1) 輸入：有0 個(gè)或多個(gè)輸入(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)43、函數(shù)32n+10nlogn的漸進(jìn)表達(dá)式是(B ).A. 2n B. 32nC. nlogn D. 10nlogn4

9、4、大整數(shù)乘法算法是( A ).算法A.分治B.貪心C.動(dòng)態(tài)規(guī)劃D.窮舉45、解決活動(dòng)安排問(wèn)題，最好用(B )算法A.分治B.貪心C.動(dòng)態(tài)規(guī)劃D.窮舉46、設(shè)f(N),g(N)是定義在正數(shù)集上的正函數(shù)，如果存在正的常數(shù)C和自然數(shù)N0, 使得當(dāng)NN0時(shí)有f(N) &Cg(N則稱(chēng)函數(shù)f(N)當(dāng)N充分大時(shí)有下界g(N),記作 f(N) CO(g(N),即 f(N)的階(A )g(N)的階.A.不高于B.不低于C.等價(jià)于D.逼近47、回溯法在解空間樹(shù)T 上的搜索方式是( A ).A.深度優(yōu)先B.廣度優(yōu)先C.最小耗費(fèi)優(yōu)先D.活結(jié)點(diǎn)優(yōu)先48、回溯算法和分支限界法的問(wèn)題的解空間樹(shù)不會(huì)是(D).A.有序樹(shù)B.

10、子集樹(shù)C.排列樹(shù)D.無(wú)序樹(shù)49、在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中,一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是( B ).A.回溯法B.分支限界法C.回溯法和分支限界法 D.回溯法求解子集樹(shù)問(wèn)題50、從活結(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ì)

11、實(shí)現(xiàn)。5、算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程 。6、從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是 遞歸算法 。7、問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。8、以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為回溯法 。9、計(jì)算一個(gè)算法時(shí)間復(fù)雜度通?？梢杂?jì)算循環(huán)次數(shù)、基本操作的頻率或計(jì)算步。10、解決0/1背包問(wèn)題可以使用動(dòng)態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是動(dòng)態(tài)規(guī)劃，需要排序的是回溯法 ,分支限界法 。11、使用回溯法進(jìn)行狀態(tài)空間樹(shù)裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問(wèn)題和0/1背包問(wèn)題正好是兩種不同的類(lèi)型， 其中同時(shí)使用約 束條件和

12、目標(biāo)函數(shù)的界進(jìn)行裁剪的是 0/1 背包問(wèn)題,只使用約束條件進(jìn) 行裁剪的是 N 皇后問(wèn)題。12、貪心選擇性質(zhì) 是貪心算法可行的第一個(gè)基本要素,也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。13、矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃設(shè)計(jì)實(shí)現(xiàn)。14 .貪心算法的基本要素是貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。15 .動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干子問(wèn)雪幺求解子問(wèn)題、然后從這些 子問(wèn)題的解得到原問(wèn)題的解。16 .算法是由若干條指令組成的有窮序列，且要滿(mǎn)足輸入、輸出 、確定性和 有限性四條性質(zhì)。17、大整數(shù)乘積算法是用分治法來(lái)設(shè)計(jì)的。18、以廣度優(yōu)先或以最小耗費(fèi)方式搜索問(wèn)題解的算法稱(chēng)為分支限界法。19 、貪心

13、選擇性質(zhì) 是貪心算法可行的第一個(gè)某本要素、也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。20 .快速排序算法是基于分治策略的一種排序算法。21 .動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問(wèn)題 性質(zhì)。22 .回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。23 .分支限界法主要有隊(duì)列式(FIF。分支限界法和 優(yōu)先隊(duì)列式分支限界法。24 .分支限界法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。25 .回溯法搜索解空間樹(shù)時(shí)，常用的兩種剪枝函數(shù)為約束函數(shù)和限界函數(shù)。26 .任何可用計(jì)算機(jī)求解的問(wèn)題所需的時(shí)間都與其規(guī)模 有關(guān)。27 .快速排序算法的性能取決于劃分的對(duì)稱(chēng)性。28 . Prim算法利用貪心策

14、略求解最小生成樹(shù)問(wèn)題,其時(shí)間復(fù)雜度是O(n2)。29 .圖的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) break;xi=1;c - =wi;if (i=n) xi=c/wi; 2 .最大子段和：動(dòng)態(tài)規(guī)劃算法int MaxSum(int n, int a口) int su

15、m=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 .快速排序templatevoid QuickSort (Type a口，int p, int r)if (pr) int q=Partition(a,p,r);QuickSort (a,p,q-1); 對(duì)左半段排序QuickSort (a,q+1,r); 對(duì)右半段排序4 . IF歹I問(wèn)題Template void perm(Type list口，int k,

16、 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+)swap(listk, listi);perm(list,k+1;m);swap(listk,listi);5.給定已按升序排好序的n個(gè)元素a0:n-1,現(xiàn)要在這n個(gè)元素中找出一特定元素X 0據(jù)此容易設(shè)計(jì)出二分搜索算法：templateint BinarySearch(Type a口，const Type& x, int l, int r)while

17、 (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、合并排序描述如下：templatevoid Mergesort(Type a , int left, int right)if (leftvright )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ù)制到

18、數(shù)組 a 7、分治法求最大、最小元 template void SortableList二MaxMin(int i, int j, T& max, T& min) const /前置條件：i和j, 0&i&j表長(zhǎng)，是表的下標(biāo)范圍的界T min1, max1;if (i=j) max=min=li;表中只有一個(gè)元素時(shí)else if (i=j-1)/表中有兩個(gè)元素時(shí)if (叨血max=lj; min=li; else max=li; min=lj;else /表中多于兩個(gè)元素時(shí)int m=(i+j)/對(duì)半分割MaxMin(i, m, max, min);/求前半部子表中的最大、最小元MaxMin(

19、m+1, j, max1, min1)/求后半部子表中的最大、最小元if (maxmin1) min=min1;兩子表最小元的小者為原表最小元 四、問(wèn)答題1 .用計(jì)算機(jī)求解問(wèn)題的步驟：1、問(wèn)題分析2、數(shù)學(xué)模型建立3、算法設(shè)計(jì)與選擇4、算法指標(biāo)5、算法分析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)完成。確定性：算法中每一條指令必須有確切的含義。不存在二義性。只

20、有一個(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)系的量。5. 算法設(shè)計(jì)的質(zhì)量指標(biāo)：正確性：算法應(yīng)滿(mǎn)足具體問(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)常采用的算法主要有迭代法、分

21、治法、貪婪法、動(dòng)態(tài)規(guī)劃法、回溯法、分支限界法6. 迭代法 :也稱(chēng)“輾轉(zhuǎn)法”，是一種不斷用變量的舊值遞推出新值的解決問(wèn)題的方法。7. 利用迭代算法解決問(wèn)題，需要做好以下三個(gè)方面的工作：1） 、確定迭代模型。在可以用迭代算法解決的問(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í)行下去。迭代

22、過(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)一步分析出用來(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）利用

23、該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；（ 4）該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。10、分治法的基本步驟分治法在每一層遞歸上都有三個(gè)步驟：（ 1 ）分解：將原問(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ī)劃稱(chēng)為標(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é)形式

24、，適合用于理論上的 分析。在實(shí)際應(yīng)用中，許多問(wèn)題的階段劃分并不明顯，這時(shí)如果刻意地劃分階 段法反而麻煩。一般來(lái)說(shuō)，只要該問(wèn)題可以劃分成規(guī)模更小的子問(wèn)題，并且原 問(wèn)題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解（即滿(mǎn)足最優(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)前選擇可能要依賴(lài)已經(jīng)作出的所有選擇，但不依賴(lài)于有待于

25、做出 的選擇和子問(wèn)題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個(gè)子問(wèn)題是獨(dú)立的（即不包含公共的子問(wèn)題），因此一旦遞歸地求出各子問(wèn)題的解后，便可自下而上地將子問(wèn)題的解合并成問(wèn)題的解。不足之處：如果當(dāng)前選擇可能要依賴(lài)子問(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)值的解的話(huà)，它只取其中的一個(gè)。在求 解過(guò)程中，該方法也是通過(guò)求解

26、局部子問(wèn)題的解達(dá)到全局最優(yōu)解，但與分治法 和貪心法不同的是，動(dòng)態(tài)規(guī)劃允許這些子問(wèn)題不獨(dú)立，（亦即各子問(wèn)題可包含公共的子問(wèn)題）也允許其通過(guò)自身子問(wèn)題的解作出選擇，該方法對(duì)每一個(gè)子問(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)題分為若

27、干個(gè)階段。注意這若干個(gè)階段一定要是有序的或者是可排序的（即無(wú)后向性），否則問(wèn)題就無(wú)法用動(dòng)態(tài)規(guī)劃求解。（ 2）選擇狀態(tài)：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿(mǎn)足無(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)

28、、決策和狀態(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ì)算最優(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） 。此

29、時(shí)，在步驟（3）中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速地構(gòu)造出一個(gè)最優(yōu)解?？偨Y(jié)： 動(dòng)態(tài)規(guī)劃實(shí)際上就是最優(yōu)化的問(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)題往往是互相

30、獨(dú)立的。14. 回溯法回溯法也稱(chēng)為試探法，該方法首先暫時(shí)放棄關(guān)于問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí)，就選擇下一個(gè)候選解；倘若當(dāng)前候選解除了還不滿(mǎn)足問(wèn)題規(guī)模要求外，滿(mǎn)足所有其他要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿(mǎn)足包括問(wèn)題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問(wèn)題的一個(gè)解。在回溯法中，放棄當(dāng)前候選解，尋找下一個(gè)候選解的過(guò)程稱(chēng)為回溯。擴(kuò)大當(dāng)前候選解的規(guī)模，以繼續(xù)試探的過(guò)程稱(chēng)為向前試探。15. 分支限界法：這是一種用于求解組合優(yōu)化問(wèn)題的排除非解的搜索算法。類(lèi)似于回溯法，分枝定界法在搜索解空間時(shí)，也經(jīng)常使用樹(shù)形結(jié)構(gòu)來(lái)組織解空

31、間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹(shù)結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小耗費(fèi)方法來(lái)搜索這些樹(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)镋-節(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é)

32、點(diǎn)作為下一個(gè)E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充過(guò)程才結(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. 分支限界法與

33、回溯法的相同點(diǎn)是：都是一種在問(wèn)題的解空間樹(shù)T中搜索問(wèn)題解的算法。不同點(diǎn)： （ 1）求解目標(biāo)不同；（ 2）搜索方式不同；（ 3）對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同；（ 4）存儲(chǔ)空間的要求不同。17. 分治法所能解決的問(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)題。18. 用分支限界法設(shè)計(jì)算法的步驟是：（1）針對(duì)所給問(wèn)題，定義問(wèn)題的解空間（對(duì)解進(jìn)行編碼）；（2）確

34、定易于搜索的解空間結(jié)構(gòu)（按樹(shù)或圖組織解）；（3）以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。19. 常見(jiàn)的兩種分支限界法的算法框架：(1)隊(duì)列式(FIFO)分支限界法：按照隊(duì)列先進(jìn)先出(FIFO)原則選取下一 個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。1 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中找出滿(mǎn)足某種性質(zhì)的子集時(shí)，相 應(yīng)的解空間樹(shù)稱(chēng)為子集樹(shù)。這類(lèi)子集樹(shù)通常有2n個(gè)葉結(jié)點(diǎn)，遍歷子集樹(shù)需O(2n) 計(jì)算時(shí)間。當(dāng)所給的問(wèn)題是確定n個(gè)元素滿(mǎn)足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹(shù) 稱(chēng)為排列樹(shù)。這類(lèi)排列樹(shù)通常有 n!個(gè)葉結(jié)點(diǎn)。遍歷排列樹(shù)需要 O(n!)計(jì)算時(shí)間。21 .分支限界法的搜索策略是：在擴(kuò)展結(jié)點(diǎn)處，先生成其所有