算法設(shè)計(jì)與分析基礎(chǔ)第2版算法分析第8章課件

1、 動(dòng)態(tài)規(guī)劃(dynamic programming)是一種算法設(shè)計(jì)技術(shù)，它有著相當(dāng)有趣的歷史。作為一種使多階段決策過程最優(yōu)的通用方法，它是在20世紀(jì)50年代由一位卓越的美國(guó)數(shù)學(xué)家Richard Bellman所發(fā)明的。因此，這個(gè)技術(shù)名字中的“Programming”是計(jì)劃和規(guī)劃的意思，不是代表計(jì)算機(jī)中的編程。它作為一種重要的工具在應(yīng)用數(shù)學(xué)中的價(jià)值被大家認(rèn)同以后，起碼在計(jì)算機(jī)科學(xué)的圈子里，人們不僅用它來解決特定類型的最憂問題，而且最終把它作為一種通用的算法設(shè)計(jì)技術(shù)來使用。在這里，我們正是從這個(gè)角度來考慮這種技術(shù)的。 如果問題是由交疊的子問題所構(gòu)成的，我們就可以用動(dòng)態(tài)規(guī)劃技術(shù)來解決它。一般來說，這

2、樣的于問題出現(xiàn)在對(duì)給定問題求解的遞推關(guān)系中，這個(gè)遞推關(guān)系中包含了相同類型的更小子問題的解。動(dòng)態(tài)規(guī)劃法建議，與其對(duì)交疊的子問題一次又一次地求解，還不如對(duì)每個(gè)較小的子問題只求解一次并把結(jié)果記錄在表中，這樣就可以從表中得出原始問題的解 8.1 計(jì)算二項(xiàng)式系數(shù) 計(jì)算二項(xiàng)式系數(shù)是把動(dòng)態(tài)規(guī)劃應(yīng)用于非最優(yōu)化問題的一個(gè)標(biāo)準(zhǔn)例子 在二項(xiàng)式系數(shù)的多種特性之中，只關(guān)心兩種： 當(dāng)nk0時(shí)，C(n,k)C(n-1,k-1)+C(n-1,k)以及 C(n,0)=C(n,n)=1 為了計(jì)算c(n,k)，一行接一行地填充下表，從行0開始，到行n結(jié)束 算法 Binomial(n,k) /用動(dòng)態(tài)規(guī)劃算法計(jì)算C(n,k) /輸入：

3、對(duì)非負(fù)整數(shù)n=k=0 /輸出：C(n,k)的值 for i 0 to n do for j 0 to min(i,k) do if j=0 or j=k Ci,j 1 else Ci,j Ci-1,j-1+Ci-1,j return Cn,k該算法的時(shí)間效率如何呢?顯然，該算法的基本操作是加法 8.2 Warshall算法和FLoyd算法822 Warshall算法 一個(gè)有向圖的鄰接矩陣A=aij是一個(gè)布爾矩陣，當(dāng)且僅當(dāng)從第i個(gè)頂點(diǎn)到第j個(gè)頂點(diǎn)之間有一條有向邊時(shí)，矩陣第i行第j列的元素為1。 定義 一個(gè)n頂點(diǎn)有向圖的傳遞閉包可以定義為一個(gè)n階布爾矩陣T=tij ，如果從第i個(gè)到頂點(diǎn)到第j個(gè)頂點(diǎn)

4、之間存在一條有效的有向路徑，矩陣第i行(1i n)第j列(1j n)的元素為1；否則，tij為0。我們可以在深度優(yōu)先查找和廣度優(yōu)先查找的幫助下生成有向圖的傳遞閉包。從第i個(gè)頂點(diǎn)開始，無論采用哪種遍歷方法，都能夠得到通過第i個(gè)頂點(diǎn)訪問到的所有頂點(diǎn)的信息，因此，傳遞閉包的第i行的相應(yīng)列置為了1。以每個(gè)頂點(diǎn)為起始點(diǎn)做一次這樣的遍歷就生成了整個(gè)圖的傳遞閉包。Warshall算法通過一系列n階布爾矩陣來構(gòu)造一個(gè)給定的n個(gè)頂點(diǎn)有向圖的傳遞閉包，算法的中心思想是，任何中的所有元素都可以通過它在序列（8.5）中的直接前趨計(jì)算得到。 ： 式(87)是Warshall算法的核心 算法 Warshall（A1.n,

5、1.n） /實(shí)現(xiàn)計(jì)算傳遞閉包的Warshall算法 /輸入：包括n個(gè)頂點(diǎn)有向圖的鄰接矩陣A /輸出：該有向圖的傳遞閉包8.2.2計(jì)算完全最短路徑的Floyd算法 紿定一個(gè)加權(quán)連通圖（無向的或有向的），完全最短路徑問題要求找到從每個(gè)頂點(diǎn)到其他所有頂點(diǎn)之間的距離(最短路徑的長(zhǎng)度) Floyd算法通過一系列n階矩陣來計(jì)算一個(gè)n頂點(diǎn)加權(quán)圖的距離矩陣：每一個(gè)這種矩陣都包含了所討論的矩陣在特定路徑約束下的最短路徑的長(zhǎng)度 每條這種路徑都由兩條路徑構(gòu)成：一條從vi到vk的路徑，路徑中每個(gè)中間頂點(diǎn)的編號(hào)都大于K一1；一條從vi到vj的路徑，路徑中每個(gè)中間頂點(diǎn)的編號(hào)也都不大于k-1.算法 Floyd(W1.n,1

6、.n) / 實(shí)現(xiàn)計(jì)算完全最短路徑的Floyd算法 / 輸入：圖的權(quán)重矩陣W / 輸出：包含最短路徑長(zhǎng)度的距離矩陣8.3 最優(yōu)二叉樹考慮分別以概率0.1，0.2，0.4，0.3來查找4個(gè)鍵A,B,C,D。包含這些鍵的二叉查找樹有14種不同的可能ABCDABCD在成功查找時(shí)，第一棵樹的平均鍵值比較次數(shù)為0.1*1+0.2*2+0.4*3+0.3*42.9，而第二棵樹是0.1*2+0.2*1+0.4*2+0.3*32.1。 作為一個(gè)通用的算法，這種窮舉查找方法是不現(xiàn)實(shí)的：包含n個(gè)鍵的二叉查找樹的總數(shù)量等于第n個(gè)卡塔蘭數(shù) 當(dāng)n0時(shí)，設(shè)a1,an是從小到大排列的互不相等的鍵，p1,pn是它們的查找概率。

7、是由鍵a1,an構(gòu)成的二叉樹，Ci,j是在這棵樹中成功查找的最小的平均查找次數(shù)。要求出該問題的所有較小實(shí)例的Ci,j值。為了推導(dǎo)出動(dòng)態(tài)規(guī)劃算法中隱含的遞推關(guān)系，需要考慮從鍵ai,aj中選擇一個(gè)根ak的所有可能的方法。 對(duì)于這樣一棵二叉樹來說，它的根包含了鍵ak，它的左子樹 中的鍵 是最優(yōu)排列的，它的右子樹 中 的鍵也是最優(yōu)排列的。 當(dāng)1in+1時(shí)，Ci,i-10，這可以解釋為空樹的比較次數(shù)。請(qǐng)注意，這個(gè)公式意味著二維表給出了用公式(8.11)來計(jì)算Ci,j時(shí)需要用到的一些值；它們是i行中位于j列左邊的列上的值，以及j列中在i行下邊的行上的值。箭頭指出了需要對(duì)元素求和的一對(duì)對(duì)單元，然后求出這些元

8、素對(duì)的和的最小值，把它作為Ci,j的值記錄下來。這意味著我們要沿著表格的對(duì)角線填寫表格，從全部是0的主對(duì)角線和右上方給定概率Pi(1=i=n)的對(duì)角線開始，并向著右上角移動(dòng)。 0 p1 目標(biāo) p2 Ci,j Pn 001jnn+1例1 讓我們對(duì)本節(jié)開頭使用的4個(gè)鍵的集合應(yīng)用該算法，來給大家一個(gè)感性的認(rèn)識(shí)： 鍵 A B C D 查找概率 0.1 0.2 0.4 0.3算法 OptimalBST(P1.n)/ 用動(dòng)態(tài)規(guī)劃算法求最優(yōu)二叉查找樹/輸入：一個(gè)n個(gè)鍵的有序列表的查找概率數(shù)組P1.n/輸出：在最優(yōu)BST中成功查找的平均比較次數(shù)，以及最優(yōu)BST中子/樹的根表RFor i1 to n do Ci

9、,i-10 Ci,iPi Ri,iiCn+1,niFor d1 to n-1 do /對(duì)角線計(jì)數(shù) For i1 to n-d do ji+d minval for ki to j do if Ci,k-1+Ck+1,j minval minvalCi,k-1+Ck+1,j;kmink Ri,ik sumPi; for si+1 to j do sumsum+Ps Ci,iminval + sumReturn C1,n,R該算法的空間效率顯然是平方級(jí)的；這個(gè)算法的時(shí)間效率是立方級(jí)的。 一個(gè)更詳細(xì)的分析告訴我們，根表中的單元格總是沿著每一行和每一列非降序排列的。這就把Ri，j值限定在范圍Ri,j-

10、1,. Ri+1,j.間，使得我們有可能把該算法的運(yùn)行時(shí)間降低到 。8.4 背包問題和記憶功能8.4.1 背包問題為了設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，需要推導(dǎo)出一個(gè)遞推關(guān)系，用較小于實(shí)例的解的形式來表不背包問題的實(shí)例的解。讓我們來考慮一個(gè)由前i個(gè)物品(1in)定義的實(shí)例，物品的重量分別為w1,wi、價(jià)價(jià)值分別為v1，vi，背包的承重量為j(1jW)。設(shè)Vi,j為該實(shí)例的最優(yōu)解的物品總價(jià)值，也就是說，是能夠放進(jìn)承重量為j的背包中的前i個(gè)物品中最有價(jià)值子集的總價(jià)值?？梢园亚癷個(gè)物品中能夠放進(jìn)承重量為j的背包中的子集分成兩個(gè)類別：那些包括第j個(gè)物品的子集和那些不包括第J個(gè)物品曲子集。 有下面的結(jié)論： 1. 根

11、據(jù)定義，在不包括第i個(gè)物品的子集中，最優(yōu)子集的價(jià)值是Vi-1,j. 2 在包括第i個(gè)物品的子集中(因此，jw0)，員優(yōu)子集是由該物品和前i-1個(gè)物 品中能夠放進(jìn)承重量為卜wj的背包的最優(yōu)子集組成。這種最憂子集的總價(jià)值等于 Vi+Vi-1,j-wi。 因此，在前j個(gè)物品中員優(yōu)解的總價(jià)值等于這兩個(gè)價(jià)值中的較大值。當(dāng)然，如果第i個(gè)物品不能放進(jìn)背包，從前i個(gè)物品中選出的最優(yōu)子集的總價(jià)值等于從前i-1個(gè)物品中選出的最優(yōu)子集的總價(jià)值。這個(gè)觀察結(jié)果導(dǎo)致了下面這個(gè)遞推式： MaxVi-1,j,vi+Vi-1,j-wi 如果j-wi0 Vi，j Vi-1,j 如果j-wi0我們可以很容易地這樣定義初始條件： 當(dāng)

12、j0時(shí)；V0，i=0;當(dāng)i0時(shí),Vi,0=0 我們的目標(biāo)是求Vn，W，即n個(gè)給定物品中能夠放進(jìn)承重量為肛的背包的子集的最大總價(jià)值，以及最優(yōu)子集本身。8.4.2 記憶功能該方法用自頂向下的方式對(duì)給定的問題求解，但還需要維護(hù)一個(gè)類似自底向上動(dòng)態(tài)規(guī)劃算法使用的表格。一開始的時(shí)候，用一種“null”符號(hào)創(chuàng)始化表中所省的單元，用來表明它們還沒有被計(jì)算過(在這里可以便用一種稱為虛擬初始化的技術(shù)參見習(xí)題71的第8題)。然后，一日需要計(jì)算個(gè)新的值該方法先檢查表中相應(yīng)的單元；如果該單元不是“null”，它就簡(jiǎn)單地從表中取值；否則，就使用遞歸調(diào)用進(jìn)行計(jì)算，然后把返回的結(jié)果記錄在表中。 算法 MFKnapsack(

13、I,j)對(duì)背包問題實(shí)現(xiàn)記憶功能方法輸入：一個(gè)非負(fù)整數(shù)f指出先考慮的物品數(shù)量，一個(gè)非負(fù)整數(shù)J指出了背包的承重量輸出：前i個(gè)物品的最伏可行子集的價(jià)值注意：我們把輸入數(shù)組 Weights1n,Values1n和表格V0.n,0.W作為全局變量，除了行0和列0用0初始化以外，V的所有單元都用-1做初始化。if VI,j01 if jWeightsi valueMFKnapsack(i-1,j)else valuemax(MFKnapsack(i-1),j), Valuei+MFKnapsack(i-1,j-Weightsi)VI,jvaluereturn VI,j例2 對(duì)例1中的實(shí)例應(yīng)用記憶功能法*圖814給出了結(jié)果。只計(jì)算了20個(gè)有效值(也就是不在行o和列o上的)