計(jì)算機(jī)算法分析與設(shè)計(jì)

1、袀算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。 莀算法是若干指令的有窮序列，滿足性質(zhì)： 莆(1)輸入：有外部提供的量作為算法的輸入。(2)輸出：算法產(chǎn)生至少一個(gè)量作為輸出。 襖(3)確定性：組成算法的每條指令是清晰，無(wú)歧義的。 節(jié)(4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。 蝿程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)(4)。 膆分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破, 分而治之。 蟻直接或間接地調(diào)用自身的算法稱(chēng)為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱(chēng)為遞歸函數(shù)。 莁1.階乘函數(shù)階乘函數(shù)可遞歸地

2、定義為: 膈f 1 n = 0 邊界條件 n!=丿 n(n -1)! n0 祎遞歸方程 螃邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素 葿 2.Fibonacci 數(shù)列 蚈無(wú)窮數(shù)列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ，稱(chēng)為Fibonacci數(shù)列。它可以遞歸地定義為 薇 1 n =0 F( n) =* 1 n = 1 螄F (n 1) + F (n 2) n 1 莇當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱(chēng)這個(gè)函數(shù)是雙遞歸函數(shù)。 薁Ackerman函數(shù) A(n , m)定義如下: A(1,0) =2 IA(0,m)=1m0 |A(n ,0) = n+2n2 A(n,

3、 m)=A(A(n -1, m),m1) n, m 亠1 蚃 節(jié) 膀Ackerman函數(shù) 薄A(n , m)的自變量 m的每一個(gè)值都定義了一個(gè)單變量函數(shù)： 螄 M=0 時(shí)，A(n ,0)=n+2 蒁 M=1 時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和 A(1,1)=2 故 A(n,1)=2*n 蕿 M=2 時(shí)，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和 A(1,2)=A(A(0,2),1)=A(1,1)=2 ，故 A(n,2)= 25 。 莄M=3時(shí)，類(lèi)似的可以推出 蒁M=4時(shí)，A(n,4)的增長(zhǎng)速度非常快，以至于沒(méi)有適當(dāng)?shù)臄?shù)學(xué)式子來(lái)表示這一函

4、數(shù)。 蕿定義單變量的 Ackerman函數(shù) A(n)為，A(n)=A(n ， n)。 聿定義其擬逆函數(shù)a (n)為：a (n)=mink | A(k) n。即a (n)是使nW A(k)成立的最小的k值。 肅a (n)在復(fù)雜度分析中常遇到。對(duì)于通常所見(jiàn)到的正整數(shù)n,有a (n) w4。但在理論上a (n)沒(méi)有上界，隨著 n的增加，它以難以想象的慢速度趨向正無(wú)窮大。 薃6排列問(wèn)題 袁設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素r1,r2,rn的全排列。 蒈設(shè)R=r1,r2,rn是要進(jìn)行排列的n個(gè)元素，Ri=R-ri。集合X中元素的全排列記為perm(X)。 螅(ri)perm(X)表示在全排列perm(X)的每

5、一個(gè)排列前加上前綴得到的排列。R的全排列可歸納定義如下：當(dāng) n=1時(shí)，perm(R)=(r)，其中r是集合 R中唯一的元素； 蚄當(dāng) n1 時(shí)，perm(R)由(r1)perm(R1) , (r2)perm(R2),，(rn)perm(Rn)構(gòu)成。 薀7整數(shù)劃分問(wèn)題 莇在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加 數(shù)n1不大于m的劃分個(gè)數(shù)記作 q(n,m)。可以建立q(n,m)的如下遞歸關(guān)系。 肅(3) q(n,n )=1+q( n,n-1); 羂正整數(shù)n的劃分由n仁n的劃分和n1 m1; 螇正整數(shù)n的最大加數(shù)n1不大于m的劃分由n仁m的劃分和

6、 n = 1, m = 1 n ： m 螆n1 0) 袃hano i(n-1, a, c, b); 薀move(a,b); 螈hanoi( n-1, c, b, a); 螇遞歸小結(jié)：優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、 調(diào)試程序帶來(lái)很大方便。 羅缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。 羂分治法的適用條件 膈分治法所能解決的問(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)題分解

7、出的子問(wèn)題的解可以合并為該問(wèn)題的解； 蚇4.該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。 羄這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地 解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。 平衡 袃?nèi)藗儚拇罅繉?shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。即將一個(gè)問(wèn)題分成大 小相等的k個(gè)子問(wèn)題的處理方法是行之有效的。這種使子問(wèn)題規(guī)模大致相等的做法是出自一種 (balancing)子問(wèn)題的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。 腿9二分搜索技術(shù) 肆給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在

8、這n個(gè)元素中找出一特定元素X。 螄二分搜索算法： 裊 public static int bin arySearch(i nt a, int x, int n) 薁 / 在 a0 = a1 = . = an-1中搜索 x 螀 /找到x時(shí)返回其在數(shù)組中的位置，否則返回-1 蒅in t left = 0; int right = n - 1; 螞 while (left amiddle) left = middle + 1; else right = middle - 1; 肂 return -1; / 未找到 x 蕿算法復(fù)雜度分析： 羆每執(zhí)行一次算法的 while循環(huán)，待搜索數(shù)組的大小減少一半。

9、因此，在最壞情況下，while循環(huán)被執(zhí)行了 O(logn)次。循環(huán)體內(nèi)運(yùn)算需要 0(1)時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn)。 螅合并排序： 膀基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的 子集合合并成為所要求的排好序的集合。 肇最壞時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：O(nl og n)輔助空間：O(n) 蚆快速排序：最壞時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)或O(logn) 薂動(dòng)態(tài)規(guī)劃算法的基本要素 薃(1)最優(yōu)子結(jié)構(gòu)性質(zhì)(2 )重疊子問(wèn)題性質(zhì) 蕆1 利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)

10、，以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu) 解。最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。 蒆2.遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱(chēng)為 子問(wèn)題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次 需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。 蚃通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得 較高的解題效率。 蟻備忘錄方法 袇備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過(guò)的子問(wèn)題建立 了備忘錄以備需要時(shí)查

11、看，避免了相同子問(wèn)題的重復(fù)求解。 腿動(dòng)態(tài)規(guī)劃基本步驟：1.找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 蚅2.遞歸地定義最優(yōu)值。3以自底向上的方式計(jì)算出最優(yōu)值。 蝿4.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。 薀動(dòng)態(tài)規(guī)劃基本思想 羇是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目 常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。如果能夠保存已解決的子問(wèn) 題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。 蒂0/1背包問(wèn)題0/1背包問(wèn)題的求解過(guò)程 膂一、動(dòng)態(tài)規(guī)劃函數(shù) nn 罿Xi :物體i被裝入背包的情

12、況，Xi =0,1。約束方程和目標(biāo)函數(shù)：7 WiXi _Moptp = max piXi 解向量X =(X1，X2，Xn)。背包的載重量：0mVy 蚇optpj):前i個(gè)物體中，能裝入載重量為j的背包中的物體的最大價(jià)值，j=1,2,m。 薄動(dòng)態(tài)規(guī)劃函數(shù)：optpi(0) =optp0(j) =0( 6.6.1) 芀 optp i (j) optpi .1( j ) maxoptpi(j),optpi 4(j -Wi) - Pi j：Wi( 6.6.2) jWi 莂若 optpi (j ) optPi 4(j) 貝yXi =1, j = j _Wi (664) 葿二、求解過(guò)程 膄1、決策階段：第

13、一階段，只裝入一個(gè)物體，確定在各種不同載重量的背包下，能夠得到的最大價(jià)值；第 二階段，裝入前兩個(gè)物體，確定在各種不同載重量的背包下，能夠得到的最大價(jià)值；依此類(lèi)推，直到第n個(gè) 階段。 蚅最后，optp n ( m)便是在載重量為 m的背包下，裝入n個(gè)物體時(shí)，能夠取得的最大價(jià)值。 螞2、解向量的確定 袈從optp n ( m)的值向前倒推。 (663) 襖遞推關(guān)系式：若optp, j)込optpi 4( j)貝Vxi =0 螁例6.6有5個(gè)物體，其重量分別為2,2, 6, 5, 4,價(jià)值分別為6, 3, 5,4, 6，背包的載重量為10,求裝入背 包的物體及其總價(jià)值 羋計(jì)算結(jié)果，如圖6.7所示。

14、0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 6 6 6 I 6 6 6 6 6 6 2 0 0 6 6 9 9 9 9 9 9 9 3 0 0 6 6 9 9 9 9 11 11 14 4 0 0 6 6 9 9 9 10 11 13 14 5 0 0 6 6 9 9 12 12 15 15 15 蒄圖6.75個(gè)物體的0/1背包問(wèn)題的例子 衿裝入背包的物體為x = 1,1,0,0,1。 蚇0-1背包問(wèn)題 蒞給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi,背包的容量為 C。問(wèn)應(yīng)如何選擇裝入背包的物 品，使得裝入背包中物品的總價(jià)

15、值最大？ 薅0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。 n WjXj _ C i 4 n Vi xi i -1 max 膆 Xi 莂設(shè)所給 0-1背包問(wèn)題的子問(wèn)題 n WkXk 豈 j k -i 0,1, i 乞 k 乞 n 袀 祎 max n VkXk k =i xk (0,1,1 乞 i 乞 n 螂 m(i, j) j - Wi 0 乞 j :wi 莄的最優(yōu)值為m(i, j)，即m(i, j)是背包容量為j，可選擇物品為i, i+1，n時(shí)0-1背包問(wèn)題的最優(yōu)值。 由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i, j)的遞歸式如下。 賺 m(n, j) Vn .0 j - wn 0 -

16、j : wn maxm(i 1, j), m(i 1, j - wi) vi m(i +1, j) 蚈算法復(fù)雜度分析： 莆從m(i , j)的遞歸式容易看出，算法需要0(nc)計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算時(shí)間較多。 例如，當(dāng)c2n時(shí)，算法需要Q (n2n)計(jì)算時(shí)間。 芃二叉搜索樹(shù) 罿(1)若它的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值; 肇(2)若它的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值; 肇(3它的左、右子樹(shù)也分別為二叉排序樹(shù) 芄最優(yōu)二叉搜索樹(shù) 莁最優(yōu)二叉搜索樹(shù) Tij的平均路長(zhǎng)為pij，則所求的最優(yōu)值為p1,n。由最優(yōu)二叉搜索樹(shù)問(wèn)題的最優(yōu)子結(jié)

17、構(gòu)性質(zhì) 可建立計(jì)算pij的遞歸式如下 薇 Wi,j Pi,j 二 Wi,jmkiqWi,kPi,kWki,jPk i,j 袇 肁記wi,jpi,j為m(i,j)，則m(1,n)=w1,np1,n=p1,n為所求的最優(yōu)值。計(jì)算m(i,j)的遞歸式為 蒀m(i, j) =Wi,j.mkinjm(i,k -1) m(k 1, j), i 乞 j m(i,i 1) =0,1 勻蘭 n FP9. I羇 薈 呵鳥(niǎo)紅* 1)+m(k +1, j) =限叫卡.“(* -1)+m(k +1, j” i jsusij/Mhsi 1 j 膃注意至U 螂可以得到0(n2)的算法 蝕多段圖的最短路徑問(wèn)題 肄定義6.1有

18、向連通賦權(quán)圖G=(V,E,W)，頂點(diǎn)集合V劃分成k個(gè)不相交的子集 Vi ,1_i_k , k _2，使得 E中的任一邊(u,v)，必有u Vi , v Vi -m , m -1。稱(chēng)為多段圖。 芄令|V1 |=|Vk |=1，稱(chēng)s V1為源點(diǎn),t Vk為收點(diǎn)。 羈多段圖的最短路徑問(wèn)題，是求從源點(diǎn)s到達(dá)收點(diǎn)t的最小花費(fèi)的通路 聿一、頂點(diǎn)編號(hào)： 襖根據(jù)多段圖的k個(gè)不相交的子集Vi，把多段圖劃分為k段，每一段包含頂點(diǎn)的一個(gè)子集。 羈把頂點(diǎn)集合V中的所有頂點(diǎn)，按照段的順序進(jìn)行編號(hào)。 聿子集中的頂點(diǎn)互不鄰接，它們之間的相互順序無(wú)關(guān)緊要。 蕿頂點(diǎn)個(gè)數(shù)為n，頂點(diǎn)s的編號(hào)為0，則收點(diǎn)t的編號(hào)為n _1， 薅對(duì)E

19、中的任何一條邊（u,v），頂點(diǎn)u的編號(hào)小于頂點(diǎn)v的編號(hào)。 肅二、決策過(guò)程 莁 數(shù)組元素costi:存放頂點(diǎn)i到達(dá)收點(diǎn)t的最小花費(fèi) 羈數(shù)組元素path i :存放頂點(diǎn)i到達(dá)收點(diǎn)t的最小花費(fèi)通路上的前方頂點(diǎn)編號(hào) 芅數(shù)組route n:存放從源點(diǎn)s出發(fā)，到達(dá)收點(diǎn)t的最短通路上的頂點(diǎn)編號(hào) 膄第一階段，確定第k -1段的所有頂點(diǎn)到達(dá)收點(diǎn)t的花費(fèi)最小的通路。 薀第二階段，用第一階段的信息，確定第k_2段的所有頂點(diǎn)到達(dá)收點(diǎn)t的花費(fèi)最小的通路。 莇如此依次進(jìn)行，直到最后確定源點(diǎn)s到達(dá)收點(diǎn)t的花費(fèi)最小的通路。 肅最后，從源點(diǎn)s的path信息中，確定它的前方頂點(diǎn)編號(hào)p1 ， 羂從5的path信息中，確定P1的前方

20、頂點(diǎn)編號(hào)P2， 袂如此遞推，直到收點(diǎn)t 螇動(dòng)態(tài)規(guī)劃函數(shù)：costi=mi nCjj cost j （6.2.1） 螆 pathi二使 Cj cost j 最小的 j i ： j n （6.2.2） 羃三、步驟： 羀1.對(duì)所有的i,0_i ： n，把cost i 初始化為最大值，path i 初始化為-1; cost n-1初始化為0; 2.令 i =n -2 ; 3.根據(jù)（6.2.1）式和（6.2.2）式計(jì)算 costi和 path i ； 蒀4. i =i -1，若 i _0 ,轉(zhuǎn) 3;否則，轉(zhuǎn) 5; 5.令 i =0 , route i = 0;薆6.如果route i =n -.1，算法

21、結(jié)束；否則，轉(zhuǎn) 7; 肄 7. i =i 亠 1, route i = path route i _1;轉(zhuǎn) 6; 腿例6.2求解圖6.3所示的最短路徑問(wèn)題。 芇圖6.3動(dòng)態(tài)規(guī)劃方法求解多段圖的例子 袂 i =8： cos t 8 =c89 cost 9 =3 0 =3pat8 =9 蒁i =7 : cost 7 = C79 :cost 9 =7 ：0 =7p a t7 =9 荿 i =6 :cost 6=min c67- cos t 7 , c68- cos t 8 =min 67,53=8pat6=8 肇 i =5 :cost 5 =min c57亠 cost 7 ,c58亠 cost 8=

22、mi 門(mén)8亠7,6亠3=9pat5=8 袃 i =4 :cost 4 =min c47 cos t 7 , c48- cost 8 =mi n 5 7,6 3=9pa t4=8 薀 i =3: cos t 3 =min c35 亠 cost 5 , c36 亠 cost 6 = min 4 亠 9,7 亠 8 =13 pat3=5 螈i =2 : cost 2 =min c23 cost 3, c24 cost 4 ,c25 cost 5 ,c26 cost 6 =mi n113,6 9,7 9,8 8 =14 p a t!2 =3 羅 i=1 :cost 1 =min c14cos t 4

23、, c15cost 5 = min 99,69 =15 pat1=5 羂 i=0 :cost 0 =min c01cost 1 ,c02- cost 2 ,c03 cost 3 膈=min 4 15,1 14,3 13 =15path)=2 蒈 route 0 =0 螂 route 1 = path route 0 = path 0 = 2 肀 route 2 = path route 1 = path 2 =3 蚇 route 3 = path route 2 = path 3 =5 羄 route 4 = path route 3 = path 5 =8 袃 route 5 = path

24、route 4 = path 8 =9 腿最后，得到最短的路徑為0, 2, 3, 5, 8, 9,費(fèi)用是15。 肆 螄貪心算法的基本要素 裊貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 薁所謂貪心選擇性質(zhì) 是指所求問(wèn)題的 整體最優(yōu)解 可以通過(guò)一系列 局部最優(yōu) 的選擇，即貪心選擇來(lái)達(dá)到。 這是 貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。 螀動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的 方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。 蒅最優(yōu)子結(jié)構(gòu)性質(zhì) 當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)此問(wèn)題具有最優(yōu)子

25、結(jié)構(gòu)性質(zhì)。問(wèn)題的 最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。 螞0-1背包問(wèn)題： 蠆給定n種物品和一個(gè)背包。物品 i的重量是 Wi，其價(jià)值為Vi，背包的容量為 C。應(yīng)如何選擇裝入背 包的物品，使得裝入背包中物品的總價(jià)值最大？ 腿在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背 包多次，也不能只裝入部分的物品io 芅背包問(wèn)題：與0-1背包問(wèn)題類(lèi)似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不 一定要全部裝入背包，1 w i n) output(x); else for (int i=t;iv=n;i+) swap

26、(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); 遍歷子集樹(shù)需0(2n)計(jì)算時(shí)間 void backtrack (int t) if (tn) output(x); else for (int i=0;i=1;i+) xt=i; if (legal(t) backtrack(t+1); 裝載問(wèn)題 i的重量為wi，且 有一批共n個(gè)集裝箱要裝上2艘載重量分別為cl和c2的輪船，其中集裝箱 n 裝載問(wèn)題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。 容易證明，如果一個(gè)給定裝載問(wèn)題有解，則采用下面的策略可

27、得到最優(yōu)裝載方案。 (1) 首先將第一艘輪船盡可能裝滿； n max 必 i d n S.t. wi Xj _ c1 i d Xj0,1, 1 乞 i 空 n (2) 將剩余的集裝箱裝上第二艘輪船。 將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱的 一個(gè)子集，使該子集中集裝箱重量之和最接近。由 此可知，裝載問(wèn)題等價(jià)于以下特殊的0-1背包問(wèn)題。 用回溯法設(shè)計(jì)解裝載問(wèn)題的0(2 n)計(jì)算時(shí)間算法。 在某些情況下該算法優(yōu)于動(dòng)態(tài)規(guī)劃算法。 n后問(wèn)題 解向量：(x1, x2,，xn)顯約束：xi=1,2,，n 隱約束：1)不同列：x-xj2)不處于同一正、反對(duì)角線：|i-j|討xi-xj| 0-1背包問(wèn)題n

28、 解空間：子集樹(shù)可行性約束函數(shù)：送wx c, 圖的m著色問(wèn)題 - 給定無(wú)向連通圖 G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一 種著色法使 G中每條邊的2個(gè)頂點(diǎn)著不同顏色。這個(gè)問(wèn)題是圖的m可著色判定問(wèn)題。若一個(gè)圖最少需要m 種顏色才能使圖中每條邊連接的 2個(gè)頂點(diǎn)著不同顏色，則稱(chēng)這個(gè)數(shù)m為該圖的色數(shù)。求一個(gè)圖的色數(shù) m的問(wèn) 題稱(chēng)為圖的m可著色優(yōu)化問(wèn)題。 解向量：(x1, x2,，xn)表示頂點(diǎn)i所著顏色xi 可行性約束函數(shù)：頂點(diǎn)i與已著色的相鄰頂點(diǎn)顏色不重復(fù)。 復(fù)雜度分析 圖m可著色問(wèn)題的解空間樹(shù)中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是 對(duì)于每一個(gè)內(nèi)結(jié)點(diǎn)，在最壞情況下，用ok檢查當(dāng)前擴(kuò)展

29、結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色可用性需耗時(shí)0(mn)。 因此，回溯法總的時(shí)間耗費(fèi)是 連續(xù)郵資問(wèn)題 假設(shè)國(guó)家發(fā)行了 n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問(wèn)題要求對(duì)于 給定的n和m的值，給出郵票面值的最佳設(shè)計(jì)，在1張信封上可貼出從郵資1開(kāi)始，增量為1的最大連續(xù)郵 資區(qū)間。 例如，當(dāng)n=5和m=4時(shí)，面值為(1,3,11,15,32)的5種郵票可以貼出郵資的最大連續(xù)郵資區(qū)間是1到70。 解 向量：用n元組x1:n表示n種不同的郵票面值，并約定它們從小到大排列。x1=1是唯一的選擇。可行 性約束函數(shù)：已選定 x1:i-1，最大連續(xù)郵資區(qū)間是1:r，接下來(lái)xi的可取值范圍是

30、xi-1+1:r+1。 回溯法效率分析 通過(guò)前面具體實(shí)例的討論容易看出，回溯算法的效率在很大程度上依賴于以下因素： (1) 產(chǎn)生xk的時(shí)間； (2) 滿足顯約束的xk值的個(gè)數(shù)； 計(jì)算約束函數(shù)constraint的時(shí)間； 計(jì)算上界函數(shù)bound的時(shí)間； (5)滿足約束函數(shù)和上界函數(shù)約束的所有xk的個(gè)數(shù)。 好的約束函數(shù)能顯著地減少所生成的結(jié)點(diǎn)數(shù)。但這樣的約束函數(shù)往往計(jì)算量較大。因此，在選擇約束函數(shù)時(shí) 通常存在生成結(jié)點(diǎn)數(shù)與約束函數(shù)計(jì)算量之間的折衷。 分支限界法 分支限界法與回溯法 (1) 求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹(shù)中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是 找出滿足約束條件的一

31、個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。 (2) 搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹(shù)，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu) 先的方式搜索解空間樹(shù)。 分支限界法常以廣度優(yōu)先或以最小耗費(fèi)(最大效益)優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。 在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生 其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加 入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一 直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。 常見(jiàn)的兩種分

32、支限界法：(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)。 0/1背包問(wèn)題分支限界法解0/1背包問(wèn)題的思想方法和求解過(guò)程 n個(gè)物體重量分別為 WoW!，Wn二，價(jià)值分別為Po，PmPn，背包載重量為 M 物體按價(jià)值重量比遞減的順序，排序后物體序號(hào)的集合為S = 0,1,，n 1。 S1 :選擇裝入背包的物體集合，S2 :不選擇裝入背包的物體集合，S3:尚待選擇的物體集合。S1（k）、S2（k）、 S3（k）:搜索深度為k時(shí)的三個(gè)集合中的物體。開(kāi)始時(shí)，0（0