最新算法分析與設(shè)計(jì)期末考試復(fù)習(xí)題綱

1、精品文檔精品文檔選擇題算法分析與設(shè)計(jì)期末復(fù)習(xí)題等 4 個(gè)特性。確定性和易讀性 有窮性和確定性 ，記號(hào)Q表示（A ）漸進(jìn)上界緊漸進(jìn)界算法必須具備輸入、輸出和（A.可行性和安全性丨C.有窮性和安全性丨算法分析中，記號(hào) O 表示（ BA.漸進(jìn)下界C. 非緊上界 假設(shè)某算法在輸入規(guī)模為 完成概算法的時(shí)間為 t 秒。現(xiàn)有另一臺(tái)計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)的 么在這臺(tái)新機(jī)器上用同一算法在題方法：3*2A門*64=3*2儀A. n+8C. n+7 設(shè)問題規(guī)模為T（N）=2T（N/2）+N/2，用0表示的時(shí)間復(fù)雜度為（A. O（logN）C. 0（NlogN） 直接或間接調(diào)用自身的算法稱為（A.貪心算法C.迭代

2、算法Fibonacci 數(shù)列中，第A. 5， 89C. 5， 144在有 8 個(gè)頂點(diǎn)的凸多邊形的三角剖分中，恰有A. 6 條弦和 7 個(gè)三角形BC. 6 條弦和 6個(gè)三角形D一個(gè)問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（A重疊子問題BC.貪心選擇性質(zhì)D下列哪個(gè)問題不用貪心法求解（CA.哈夫曼編碼問題BC.最大團(tuán)問題D下列算法中通常以自底向上的方式求解最優(yōu)解的是（A.備忘錄法C.貪心法 下列算法中不能解決A.貪心法C.回溯法 下列哪個(gè)問題可以用貪心算法求解（B.D.n時(shí)的計(jì)算時(shí)間為T（n）=3*2M。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并64 倍，那 B ）解t 秒內(nèi)能解輸入規(guī)模為多大的問題？n+6n

3、+5N 時(shí)，某遞歸算法的時(shí)間復(fù)雜度記為CO（N） O（N2logN） ）。 遞歸算法 回溯法4 個(gè)和第 11 個(gè)數(shù)分別是 B D3，3，89144B5 條弦和5 條弦和）。T(N) ，）。）。6 個(gè)三角形5 個(gè)三角形最優(yōu)子結(jié)構(gòu)性質(zhì)定義最優(yōu)解）。單源最短路徑問題 最小生成樹問題B）。已知T(1)=1 ，）。D0/1 背包問題的是（B動(dòng)態(tài)規(guī)劃法回溯法A ）。動(dòng)態(tài)規(guī)劃分支限界法D ）。1.2.3.4.5.6.7.8.9.10.11.12.A. LCS問題B.批處理作業(yè)問題C0-1 背包問題D哈夫曼編碼問題用回溯法求解最優(yōu)裝載問題時(shí)，若待選物品為m 種，則該問題的解空間樹的結(jié)點(diǎn)個(gè)數(shù)為（A. m!C.

4、2m+1-1 二分搜索算法是利用（A.分治策略C.貪心法）。B2m+1D2mA ）實(shí)現(xiàn)的算法。BD動(dòng)態(tài)規(guī)劃法 回溯法B）。 P44構(gòu)造最優(yōu)解D 定義最優(yōu)解下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（A. 找出最優(yōu)解的性質(zhì)BC. 算出最優(yōu)解（應(yīng)該是最優(yōu)值） 下面問題（ B ）不能使用貪心法解決。A.單源最短路徑問題B . N皇后問題C.最小花費(fèi)生成樹問題D 背包問題使用二分搜索算法在 n 個(gè)有序元素表中搜索一個(gè)特定元素， 在最好情況和最壞情況 下搜索的時(shí)間復(fù)雜性分別為（ AAO（1），O（logn）BCO（1），O（nlogn）D優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是A先進(jìn)先出C.結(jié)點(diǎn)的優(yōu)先級(jí)D下面不是

5、分支界限法搜索方式的是（A 廣度優(yōu)先BC 最大效益優(yōu)先）。 P17O（logn）O（nlogn） C 后進(jìn)先出 隨機(jī) ）。 P161 最小耗費(fèi)優(yōu)先 深度優(yōu)先 BO(n) ，O(n) ，）。P162分支限界法解最大團(tuán)問題時(shí)，活結(jié)點(diǎn)表的組織形式是（A 最小堆BC 棧D下列關(guān)于計(jì)算機(jī)算法的描述不正確的是（A 算法是指解決問題的一種方法或一個(gè)過程B 算法 是若 干指令的有窮序列C. 算法必須要有輸入和輸出D 算法是編程的思想 下列關(guān)于凸多邊形最優(yōu)三角剖分問題描述不正確的是（最大堆數(shù)組C ）。P1）。）。A n+1 個(gè)矩陣連乘的完全加括號(hào)和 n 個(gè)點(diǎn)的凸多邊形的三角剖分對(duì)應(yīng)B. 在有n個(gè)頂點(diǎn)的凸多邊形的

6、三角剖分中，恰有C 該問題可以用動(dòng)態(tài)規(guī)劃法來求解D. 在有n個(gè)頂點(diǎn)的凸多邊形的三角剖分中，恰有 動(dòng)態(tài)規(guī)劃法求解問題的 基本步驟 不包括（ C遞歸地定義最優(yōu)值 分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解以自底向上的方式計(jì)算出最優(yōu)值n-3 條弦n-2 個(gè)三角形）。 P44ABCD（ 可以省去的 ）分治法所能解決的問題應(yīng)具有的關(guān)鍵特征是（）。 P1613.14.15.16.17.18.19.20.21.22.23.24.A. 該問題的規(guī)?？s小到一定的程度就可以容易地解決B. 該問題可以分解為若干個(gè)規(guī)模較小的相同問題C. 禾U用該問題分解出的子問題的解可以合并為該問題的

7、解D. 該問題所分解出的各個(gè)子問題是相互獨(dú)立的25. 下列關(guān)于回溯法的描述不正確的是( D )。P114A. 回溯法也稱為試探法B. 回溯法有“通用解題法”之稱C. 回溯法是一種能避免不必要搜索的窮舉式搜索法D. 用回溯法對(duì)解空間作深度優(yōu)先搜索時(shí)只能用遞歸方法實(shí)現(xiàn)26. 常見的兩種分支限界法為( D )。P161A. 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B. 隊(duì)列式(FIFO)分支限界法與堆棧式分支限界法；C. 排列樹法與子集樹法；D. 隊(duì)列式(FIFO)分支限界法與優(yōu)先隊(duì)列式分支限界法；二、填空題2 21. f(n)=3n +10 的漸近性態(tài) f(n)= 0(n2 ),g(n)=10lo

8、g3 n 的漸近性態(tài) g(n)= 0( n)。2. 一個(gè)“好”的算法應(yīng)具有正確性、可讀性、 健壯性和高效率和低存儲(chǔ)量需求等特性。3. 算法的時(shí)間復(fù)雜性函數(shù)表示為C=F(N,I,A)，分析算法復(fù)雜性的目的在于比較 _求解同意問題的兩個(gè)不同算法的效率的效率。4. 構(gòu)成遞歸式的兩個(gè)基本要素是遞歸的邊界條件和 遞歸的定義 。5. 單源最短路徑問題可用分支限界法和貪心算法求解。6. 用分治法實(shí)現(xiàn)快速排序算法時(shí)，最好情況下的時(shí)間復(fù)雜性為O( nlogn)，最壞情況下的時(shí)間復(fù)雜性為 0(n2)，該算法所需的時(shí)間與運(yùn)行時(shí)間和戈U分兩方面因素有關(guān)。P267. 0-1背包問題的解空間樹為完全二叉樹;n后問題的解空

9、間樹為排列樹;8. 常見的分支限界法有隊(duì)列式(FIFO)分支限界法和優(yōu)先隊(duì)列式分支限界法。9. 回溯法搜索解空間樹時(shí)常用的兩種剪枝函數(shù)為約束函數(shù)和剪枝函數(shù)。10. 分支限界法解最大團(tuán)問題時(shí)，活結(jié)點(diǎn)表的組織形式是最大堆;分支限界法解單源最短路徑問題時(shí)，活結(jié)點(diǎn)表的組織形式是最小堆。三、算法填空題1. 遞歸求解Hanoi塔問題/階乘問題。例1 :階乘函數(shù)n! P12階乘的非遞歸方式定義：nFn (n-1) (n -2) 2 1試寫出階乖的遞歸式及算法。遞歸式為："1 n=0 邊界條件n!= *n(n T)! n aO遞歸方程遞歸算法：int factorial (int n) if (n=

10、0) return 1; 遞歸出口 return n * factorial (n-1); 遞歸調(diào)用例2:用遞歸技術(shù)求解 Hanoi塔問題,Hanoi塔的遞歸算法。P15其中Hanoi (int n, int a, int c, int b)表示將塔座 A上的n個(gè)盤子移至塔座 C,以塔座B為輔助。Move(a,c)表示將塔座a上編號(hào)為n的圓盤移至塔座 c上。1 1 41rnIIi *n1Oil.krLn13 1叢11嚼1q 1void hano i (i nt n, int a, int c, int b)if (n > 0)hanoi(n-1, a, b, c);move(a,c);h

11、anoi(n-1, b, c, a);2. 用分治法求解快速排序問題?？焖倥判蛩惴≒25 、作業(yè)、課件第 2章(2)42頁-50頁 template<class Typevoid Quicksort (Type a, int p, int r) if (p<r) int q=Partiti on( a,p,r);Quicksort (a,p,q-1);Quicksort (a,q+1,r)；Partition 函數(shù)的具體實(shí)現(xiàn)template<class Type>int Partition (Type a, int p, int r)int i = p, j = r +

12、 1;Type x=ap;/將< x 的元素交換到左邊區(qū)域/將> x 的元素交換到右邊區(qū)域while (true) while (a+i <x && i<r);while (a- -j >x);if (i >= j) break;Swap(ai, aj);ap = aj;aj = x;return j;3. 用貪心算法求解最優(yōu)裝載問題。最優(yōu)裝載問題 P95 課件第 4章(2)第3-8 頁 template<class Type>void Loading(int x, Type w, Type c, int n) int *t =

13、new int n+1;Sort(w, t, n);for (int i = 1; i <= n; i+) xi = 0;for (int j = 1; j <= n && wtj <= c; j+)xti = 1; c -= wtj;4. 用回溯法求解 0-1 背包/批處理作業(yè)調(diào)度 / 最大團(tuán)問題，要會(huì)畫解空間樹。 例 1：用回溯法求解 0-1 背包 P133 課件第 5 章 (2) 第 24-38 頁 template<typename Typew,typename Typep>class Knapprivate:Typep Bound(int

14、 i); / 計(jì)算上界背包容量物品數(shù) 物品重量數(shù)組 物品價(jià)值數(shù)組 當(dāng)前重量 當(dāng)前價(jià)值 當(dāng)前最優(yōu)價(jià)值void Backtrack(int i); Typew c; / 背 int n; /物品Typew *w; /Typep *p; /Typew cw; /Typep cp; /Typep bestp; / ;void Knap<Typew,Typep>:Backtrack(int i) if(i>n) bestp=cp; return; if(cw+wi<=c) / 進(jìn)入左子樹 cw+=wi;cp+=pi;Backtrack(i+1);cw-=wi;cp-=pi; if

15、(Bound(i+1)>bestp) / 進(jìn)入右子樹 Backtrack(i+1);Typep Knap<Typew,Typep>:Bound(int i)Typew cleft=c-cw; /剩余的背包容量Typep b=cp; /b 為當(dāng)前價(jià)值/ 依次裝入單位重量?jī)r(jià)值高的整個(gè)物品while(i<=n&&wi<=cleft) cleft-=wi; b+=pi; i+; if(i<=n) / 裝入物品的一部分 b+=pi*cleft/wi;return b; / 返回上界class Object / 物品類friend int Knapsac

16、k(int *,int *,int,int);public:int operator <(Object a) constreturn (d>=a.d);int ID; / 物品編號(hào)float d; / 單位重量?jī)r(jià)值;Typep Knapsack( Typep p,Typew w,Typew c,int n) / 為 Typep Knapsack 初始化Typew W=0; / 總重量Typep P=0; /總價(jià)值0 開始Object* Q=new Objectn; /創(chuàng)建物品數(shù)組，下標(biāo)從for(int i=1;i<=n;i+) / 初始物品數(shù)組數(shù)據(jù) Qi-1.ID=i;Qi-

17、1.d=1.0*pi/wi;P+=pi; W+=wi;if(W<=c) /能裝入所有物品return P;if(W<=c) /能裝入所有物品return P;QuickSort(Q,0,n-1); / 依物品單位重量?jī)r(jià)值非增排序Knap<Typew,Typep> K;K.p=new Typepn+1;K.w=new Typewn+1;for(int i=1;i<=n;i+) K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; K.cw=0; K.c=c;K.n=n; K.bestp=0; K.Backtrack(1); delete Q;

18、delete K.w;delete K.p; return K.bestp;課件第 5 章 (2)P2-5 問題描述 ,課本 P125-127例 2：批處理作業(yè)調(diào)度 解空間：排列樹 算法描述：class Flowshopstatic int m, x, bestx, / f2,f1, f, bestf, n;/ 各作業(yè)所需的處理時(shí)間/ 當(dāng)前作業(yè)調(diào)度 當(dāng)前最優(yōu)作業(yè)調(diào)度 / 機(jī)器 2 完成處理時(shí)間/ 機(jī)器 1 完成處理時(shí)間/ 完成時(shí)間和/ 當(dāng)前最優(yōu)的完成時(shí)間和/ 作業(yè)數(shù)static void Backtrack(int i)if (i > n) for (int j = 1; j <=

19、 n; j+) elsebestxj = xj; bestf = f; for (int j = i; j <= n; j+) f1+=mxj1; /第 j 個(gè)作業(yè)在第一臺(tái)機(jī)器上所需時(shí)間 f2i=(f2i-1>f1)?f2i-1:f1)+mxj2; f+=f2i;if (f < bestf) / 約束函數(shù) Swap(xi, xj); Backtrack(i+1); Swap(xi, xj); f1 - =mxj1;f - =f2i;所有作業(yè)在機(jī)器2上完成處理的時(shí)間和稱為該作業(yè)調(diào) 度的完成時(shí)間和=工£宀曲機(jī)器！機(jī)器2作業(yè)121作業(yè)231作業(yè)323調(diào)度方案不同，f也不同

20、廠批處理件業(yè)調(diào)度問題要求調(diào)度方案f調(diào)度方案f1,2,3192A1211,3.21S3,1,21912,1,32032119對(duì)于給定的n個(gè)作業(yè)，制定 最隹作業(yè)調(diào)度方寮，使具完 成時(shí)間和達(dá)到最小口18例3:最大團(tuán)問題，要會(huì)畫解空間樹。class Cliquefriend int MaxClique(int *,int ,int);public:void Prin t(); /輸出最優(yōu)解private:void Backtrack(i nt i);int *a; /圖G的鄰接矩陣，下標(biāo)從1開始int n; /圖G的頂點(diǎn)數(shù)int *x; /當(dāng)前解int *bestx; /當(dāng)前最優(yōu)解int cn; /當(dāng)

21、前團(tuán)的頂點(diǎn)數(shù)int best n; /當(dāng)前最大團(tuán)的頂點(diǎn)數(shù);void Clique:Backtrack(i nt i) if(i> n) for(i nt j=1;j<=n ;j+) bestxj=xj; best n=cn; return;/判斷第i個(gè)頂點(diǎn)是否與已選頂點(diǎn)都有邊相連int OK=1;，已入選的頂點(diǎn)集與當(dāng)前團(tuán)中的頂點(diǎn)無邊相連只要與當(dāng)前團(tuán)中一個(gè)頂點(diǎn)無邊相連，則中止for(i nt j=1;j<i;j+) /x1:i-1if(xj&&aij=0) /i進(jìn)入左子樹 OK=0; break; / if(OK) / xi=1;cn+;Backtrack(i+

22、1); xi=O; cn-; if(cn+n-i>best n) /如有可能在右子樹中找到更大的團(tuán)，則進(jìn)入右子樹 xi=0; Backtrack(i+1); 計(jì)算時(shí)間：0(n 2n)int 0K=1： fQrpntJ>1 1啊4時(shí)=0) OK=0； break； xi=1： cn+;Bdcktrack(i4l|；Xi=0： cn-； ir(cn+n-i>bestn)(xi=0；Backtrack(i+1|;11t 0 1 00 10 010 0 0四、 簡(jiǎn)答題1. 請(qǐng)簡(jiǎn)述使用動(dòng)態(tài)規(guī)劃算法解題的基本步驟。P44動(dòng)態(tài)規(guī)劃的設(shè)計(jì)分為以下 4個(gè)步驟：(1) 找出最優(yōu)解的性質(zhì)，并刻劃其

23、結(jié)構(gòu)特征。(2) 遞歸地定義最優(yōu)值。(3) 以自底向上的方式計(jì)算出最優(yōu)值。(4) 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。2. 簡(jiǎn)述動(dòng)態(tài)規(guī)劃方法與分治法的異同。P44相同點(diǎn)：動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題 然后從這些子問題的解得到原問題的解。不同點(diǎn)：分治法的子問題互相獨(dú)立且與原問題相同。與分治法不同的是，適合于動(dòng)態(tài)規(guī)劃 求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。也就是各個(gè)子問題包含公共的子 子問題。3. 試比較Prim算法與Kruskal算法的異同。105-P107相同點(diǎn)：Prim(普里姆)算法和Kruskal(克魯斯卡爾)算法都可以看作是應(yīng)用貪

24、心算法構(gòu)造最 小生成樹的例子。利用了最小生成樹性質(zhì)。不同點(diǎn)：Prim(普里姆)算法：在這個(gè)過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹 T, T中包含G的n-1條邊，且不形成回路。Kruskal(克魯斯卡爾)算法：是構(gòu)造最小生成樹的另一個(gè)常用算法。該算法不是通過擴(kuò)充連 通子集來進(jìn)行貪心選擇。而是通過選擇具有最小權(quán)的邊的集合來進(jìn)行貪心選擇。在選擇的 同時(shí)可以進(jìn)行連通操作以便形成生成樹。4. 請(qǐng)簡(jiǎn)述分支限界法的搜索策略。P161課件第6章(1)第6頁(1) 分支限界法以廣度優(yōu)先或以最小耗費(fèi)(最大效益)優(yōu)先的方式搜索問題的解空間樹。(2) 每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。(3) 活結(jié)點(diǎn)一旦成

25、為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。(4) 兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活 結(jié)點(diǎn)表中。(5) 從活結(jié)點(diǎn)表中取 下一結(jié)點(diǎn) 成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一 直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。5. 試比較分支限界法與回溯法的異同。P161課件第6章(1)第5頁不同點(diǎn)：(1) 求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法 的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義 下的最優(yōu)解。(2) 搜索方式：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或

26、以最 小耗費(fèi)優(yōu)先的方式搜索解空間樹。五、算法應(yīng)用題1. 用動(dòng)態(tài)規(guī)劃求解凸多邊形最優(yōu)三角剖分問題。三角剖分的結(jié)構(gòu)及其相關(guān)問題 P61(1)語法樹與完全加括號(hào)方式一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹，稱為表達(dá)式的語法樹。例如，完全加括號(hào)的矩陣連乘積(A1(A2A3)(A4(A5A6) 所相應(yīng)的語法樹如圖所示。(2)語法樹與凸多邊形三角剖分v0v 6是三角形v0v3v凸多邊形P=vO,v1,vn-1的三角剖分也可以用語法樹表示。 如圖：根結(jié)點(diǎn)是邊v0v 6(可以任選)。其他邊則是語法樹的葉子節(jié)點(diǎn)。6的一條邊。2、三角剖分與矩陣連乘P61(1) 一般來說，凸多邊形的三角剖分和有n-1個(gè)葉節(jié)點(diǎn)

27、的語法樹存在對(duì)應(yīng)關(guān)系。(2) N個(gè)矩陣連乘的完全加括號(hào)和有n個(gè)葉節(jié)點(diǎn)的語法樹也存在一一對(duì)應(yīng)關(guān)系。所以，n個(gè)矩陣連乘的完全加括號(hào)和有n+1個(gè)節(jié)點(diǎn)的凸多邊形的三角剖分也存在對(duì)應(yīng)關(guān)系。矩陣連乘積中 A1 A2An中的每個(gè)矩陣 Ai對(duì)應(yīng)于凸(n+1)邊形中的一條邊 vi-1vi。三角 剖分中的一條弦 vivj , i<j，對(duì)應(yīng)于矩陣連乘積Ai+1:j。(5) 矩陣連乘積的最優(yōu)計(jì)算次序問題是凸多邊形最優(yōu)三角剖分問題的特殊情況。課后習(xí)題(第3章小結(jié)* )對(duì)于如下矩陣鏈P=10,100,5,50,30,20,60,45,50,請(qǐng)按照構(gòu)造其最優(yōu)完全加括號(hào)方式，并列出相應(yīng)的語法樹和最優(yōu)三角剖分圖。2.用貪

28、心算法求解活動(dòng)安排冋題/最小生成樹冋題/哈夫曼編碼冋題。貪心算法求解活動(dòng)安排問題例：設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下:*例如，對(duì)于下圖中的帶權(quán) 圖，按法選取邊的 過程如下頁圖所示口例如，對(duì)于下圖中的帶權(quán) 圖，按Kruskal算法選取 邊的過程如下頁圖所示。哈夫曼編碼問題，前綴碼二叉樹表示法例子:圖a:與固定長(zhǎng)度編碼對(duì)應(yīng)的樹（葉子高度一致） 圖b:與可變長(zhǎng)度編碼對(duì)應(yīng)的樹（葉子高度不一致）3. 用回溯法求解0-1背包問題/最優(yōu)裝載問題。 用回溯法求0-1背包問題。P133,實(shí)例：n=5,M=50N12345W155252730P3012444650P/W22.41

29、.761.701.67(1).令bestp=0,將物體的序號(hào)按價(jià)值體積比排序結(jié)果是(2,1,3,4,5)N21345W515252730P1230444650P/W2.421.761.701.67(2) .根據(jù)排序得到部分解(1,1,1,0)，估計(jì)當(dāng)前部分解的價(jià)值b,86+(50-45)*1.67=94.3, b >bestp.(3) .繼續(xù)向下搜索生成結(jié)點(diǎn)F，得到可行解(1,1,1,0,0)，得到價(jià)值為86,更新bestp=86(如圖第3步)第3步第5步第8步(4).回溯：沿E回溯到左孩子 D，生成相應(yīng)右孩子 G,得到部分解(1,1,0,1 )，此時(shí)b=93.1 b>bestp,

30、可以生成右子樹(第4步在第5步的基礎(chǔ)上沒有 H和I的圖形)(5) .繼續(xù)生成結(jié)點(diǎn) H,I，得到可行解(1,1,0,1,0 ),價(jià)值為88，更新bestp=88(如圖第5步)(6) .回溯H生成J，得到部分解(1,1,0,0 ), 估計(jì)部分解b=92>88 (第6步在第8步的基 礎(chǔ)上沒有K和L的圖形)(7) .繼續(xù)生成結(jié)點(diǎn) K,得到可行解(1,1,0,0, 1 ), 價(jià)值為92,更新bestp=92 (第7步在 第8步的基礎(chǔ)上沒有L的圖形)(8) . K 是左孩子，生成其對(duì)應(yīng)的右孩子L，得到可行解(1,1,0,0,0)(如圖第8步)(9) .回溯，沿結(jié)點(diǎn)L向上回溯到結(jié)點(diǎn) B,生成結(jié)點(diǎn)M,得

31、到部分解(1,0),估計(jì)部分解b=90<92,回溯(第9步在第10步的基礎(chǔ)上沒有 N的圖形)(10).向上繼續(xù)回溯生成結(jié)點(diǎn)N,得到部分解(0),此時(shí)得到的b=74+10*(46/27)=91.03<92,回溯，此時(shí)已回到根結(jié)點(diǎn)，結(jié)束。最優(yōu)解(1,1,0,0, 1 ), 價(jià)值為92.(如圖第10步)練習(xí)n=8, M=110，W=( 1, 11,21,23,33,43,45,55 )P=(11,21,31,33,43,53,55,65 )用回溯法求此0-1背包問題的最優(yōu)解。最優(yōu)裝載問題 P119 課件第 P37- P54 頁假定 n= 4，w= 8 , 6 , 2 , 3 ，c1 = c 2 =12.試根據(jù)改進(jìn)后的最優(yōu)裝載算法找出最優(yōu)裝載量及相應(yīng)的最優(yōu)裝載方案。 要求：a) 列出問題的解空間。b) 構(gòu)造解空間樹。c) 根據(jù)遞歸回溯算法求出最優(yōu)解和最優(yōu)值。六、