算法設計與分析(霍紅衛(wèi))-第3章-動態(tài)規(guī)劃教學講義課件

算法設計與分析(霍紅衛(wèi))_第3章動態(tài)規(guī)劃3.1用表代替遞歸圖3-1是利用遞歸算法計算斐波那契數(shù)F7時的遞歸結(jié)構(gòu)，由此可見，重復計算的子問題數(shù)導致了指數(shù)級的復雜度。圖3-1表明，為了計算F7，遞歸算法進行了多次重疊子問題的遞歸調(diào)用,而這些重疊子問題導致了指數(shù)級的算法。在這個例子中，在第二次調(diào)用中忽略了前次調(diào)用所做的計算。計算F6=8的遞歸調(diào)用如圖3-2所示。樹中每一個節(jié)點代表所計算的斐波那契數(shù)。由于多重遞歸，導致了大量重復計算。圖3-1計算斐波那契數(shù)算法的遞歸結(jié)構(gòu)（n=7）利用自底向上的動態(tài)規(guī)劃設計策略，我們可以將計算斐波那契數(shù)的遞歸算法(例2-1)變成以下的C語言函數(shù)：intF(intn){intf,f1,f2,k,t;

if(n<2)returnn;

else{f1=f2=1;

for(k=2;k<n;k++){f=f1+f2;f2=f1;f1=f;}}returnf;}自頂向下的動態(tài)規(guī)劃(topdowndynamicprogramming)方法甚至是更簡單的一種技術，它執(zhí)行遞歸函數(shù)的運行時間與自底向上的動態(tài)規(guī)劃的運行時間相同，有時更少。我們跟蹤遞歸程序，存儲它計算的每一個值，并檢查計算的值，以避免重復計算。這種自頂向下的技術也稱為備忘錄(memoization)方法。利用自頂向下的動態(tài)規(guī)劃設計策略，我們可以將計算斐波那契數(shù)的遞歸算法(例2-1)變成以下的C語言函數(shù)：intfibarr［1000］={0};intMEMOIZED-F(intn){intt;

if(fibarr［n］!=0returnfibarr［n］;

if(n==0)t=0;

if(n==1)t=1;

if(n>1)t=MEMOIZED-F(n-1)+MEMOIZED-F(n-2);

returnfibarr［n］=t;}圖3-3計算斐波那契數(shù)的自頂向下的動態(tài)規(guī)劃示例(n=7)算法將數(shù)組fibarr初始化為0，算法執(zhí)行完成后，數(shù)組fibarr中的值如下所示：比較圖3-1與圖3-3可得，自頂向下的動態(tài)規(guī)劃方法大大減少了遞歸調(diào)用的次數(shù)，使得算法的復雜度從指數(shù)級降到線性級。這種方法將已經(jīng)計算過的子問題存儲在數(shù)組fibarr中，可避免重復計算。3.20-1背包問題對于更復雜的例子，考慮0-1背包問題(knapsackproblem)。某商店有n個物品，第i個物品價值為vi，重量(或稱權值)為wi，其中vi和wi為非負數(shù)。背包的容量為W，W為一非負數(shù)。目標是如何選擇裝入背包的物品，使裝入背包的物品總價值最大。可將這個問題形式描述如下：(3.1)約束條件為(3.2)圖3-40-1背包問題示例(1)刻畫0-1背包問題最優(yōu)解的結(jié)構(gòu)。我們可以將背包問題的求解過程看做是進行一系列的決策過程，即決定哪些物品應該放入背包，哪些物品不放入背包。如果問題的一個最優(yōu)解x1,x2,…,xn包含物品n，即xn=1，那么其余決策x1,x2,…,xn-1一定構(gòu)成子問題1,2,…,n-1在容量為W-wn時的最優(yōu)解。我們可以利用“切割—粘貼”方法證明：如果存在子問題1,2,…,n-1在容量為W-wn時的更大價值的解x1′,x2′,…,xn-1′

，我們可以構(gòu)造問題的一個新解x1′,x2′,…,xn-1′，xn。這個解比x1,x2,…,xn的總價值更大，這與x1,x2,…,xn是問題最優(yōu)解相矛盾。如果這個最優(yōu)解不包含物品n，即xn=0，那么這個最優(yōu)解一定包含子問題1,2,…,n-1在容量為W時的最優(yōu)解。證明過程類似上述情形。(2)遞歸定義最優(yōu)解的值。根據(jù)子問題的最優(yōu)解遞歸地定義問題最優(yōu)解的開銷。設c［i,w］表示背包容量為w時，i個物品導致的最優(yōu)解的總價值。顯然，問題的最優(yōu)價值為c［n,W］。由(1)中分析可得，c［i,w］遞歸定義如下：i=0或w=0wi>w

i>0且wi≤w

(3.3)(3)計算背包問題最優(yōu)解的值?；谏鲜鲇嬎鉩［i,w］的遞歸方程，我們很容易寫一個遞歸算法RECURKNAP，計算背包容量為W時n個物品的最優(yōu)價值。然而，這個算法為指數(shù)時間復雜度O(2n)，并不比窮舉法好。RECUR-KNAP(w)1max←02for(i←1to

n)3doif(space←(w-wi)≥0)4thenif((t←RECUR-KNAP(space)+vi)>max

5thenmax←t

6return

max這個遞歸過程初始調(diào)用為RECUR-KNAP(W)。我們不是直接計算遞歸方程的解，而是利用一個表格，以自底向上的方式計算最優(yōu)價值。過程KNAPSACK-DP以物品權值〈w1，w2,…,wn〉，物品價值〈v1,v2，…,vn〉，物品個數(shù)n，背包容量W作為輸入，并將c［i,w］的值存儲在輔助表c［0..n,0..W］中，以行為主序從左到右計算表c中的元素。同時維持輔助表s［1..n,1..W］，以簡化最優(yōu)解的構(gòu)造。為簡單起見，我們只將物品個數(shù)及背包容量在參數(shù)表中列出。KNAPSACK-DP(n,W)1for

w←0to

W

2do

c［0,w］←03fori←1ton4do

c［i,0］←05for

w←1to

W

6doif

w［i］≤w

7thenif

v［i］+c［i-1,w-w［i］］>c［i-1,w］8then

c［i,w］←v［i］+c［i-1,w-w［i］］9else

c［i,w］←c［i-1,w］10else

c［i,w］←c［i-1,w］由算法KNAPSACK-DP的嵌套循環(huán)結(jié)構(gòu)可得，算法的運行時間為O(nW)。對于(w1,w2,w3,w4,w5)=(3,4,7,8,9)，(v1,v2,v3,v4,v5)=(4,5,10,11,13)，W=17。圖3-5給出了由算法KNAPSACK-DP計算表c［i,w］的過程。圖3-5算法KNAPSACK-DP示例(4)根據(jù)計算的結(jié)果，構(gòu)造問題最優(yōu)解。KNAPSACK-DP返回的c可用于快速構(gòu)造背包問題的一個最優(yōu)解。如果c［i,w］=c［i-1,w］，表明xi=0，然后考察c［i-1，w］；否則xi=1，接著考察c［i-1，w-wi］。這個過程初始調(diào)用為OUTPUT-SACK(c,W)。OUTPUTSACK(c,w)1for

i←n

downto22doif

c［i,w］=c［i-1,w］3then

xi←04 else

xi←15 w←w-vi

6x1←c［1,w］?1:07return

x

3.3矩陣鏈乘問題通過上述的兩個實例表明，動態(tài)規(guī)劃算法的研制可由4步組成：(1)刻畫最優(yōu)解的結(jié)構(gòu)。(2)遞歸定義最優(yōu)解的值。(3)以自底向上(或自頂向下)的方式計算最優(yōu)解的值。(4)根據(jù)計算的結(jié)果，構(gòu)造問題最優(yōu)解。我們給矩陣加上括號的方式會對矩陣的計算開銷產(chǎn)生巨大影響。首先考慮兩個矩陣的乘積。標準計算兩個矩陣乘積的算法MATRIX-MULTIPLY描述如下，其中rows和columns分別表示矩陣的行數(shù)和列數(shù)。MATRIXMULTIPLY(A,B)1ifcolumns［A］≠rows［B］2thenerror“incompatibledomensions”3elsefor

i←1torows［A］4doforj←1to-columns［B］5doC［i,j］←06fork←1tocolumns［A］7doC［i,j］←C［i,j］+A［i,k］·B［k,j］8returnC如果矩陣A的列數(shù)等于矩陣B的行數(shù)，則兩個矩陣A和B是可相乘的,即如果矩陣A是p×q的矩陣，B是q×r的矩陣，那么，它們乘積的結(jié)果矩陣C是p×r。我們首先給出一個例子，來說明括號加在矩陣不同位置對計算量所產(chǎn)生的影響?？紤]三個矩陣〈A1，A2，A3〉鏈乘的情況。這三個矩陣的維數(shù)分別為10×100，100×5和5×50。如果我們按照((A1A2)A3)方式計算，則計算A1A2需要10×100×5=5000次乘法,計算其結(jié)果與A3的乘積需要10×5×50=2500次乘法,共需7500次數(shù)乘。如果我們按照(A1(A2A3))方式計算，則計算A2A3需要100×5×50=25000次乘法,計算A1與其結(jié)果的乘積需要10×100×50=50000次乘法，共需75000次數(shù)乘。矩陣鏈乘問題闡述如下：給定n個矩陣〈A1，A2，…，An〉，矩陣Ai的維數(shù)為pi-1×pi，i=1,2,…,n，如何給矩陣鏈乘A1×A2×…×An完全加上括號，使得矩陣鏈乘中數(shù)乘次數(shù)最少。值得注意的是，在矩陣鏈乘問題中，我們實際上并不做矩陣相乘。我們的目標是決定具有最少乘法次數(shù)的矩陣相乘的次序。一般而言，決定這個最優(yōu)次序的開銷可以由以后計算節(jié)省的開銷補償。在用動態(tài)規(guī)劃求解矩陣鏈乘問題之前，我們先討論窮舉法求解該問題的算法。假設P(n)表示n個矩陣序列的加括號的數(shù)目。當n=1時，只有一個矩陣，完全加括號的方式只有一種。當n≥2時，完全加括號矩陣乘積等于兩個完全加括號的子矩陣的乘積。而兩個子矩陣間分割的位置可在第k個矩陣以及第k+1個矩陣之間，其中k=1,2,…,n-1。因此，可得遞歸方程n=1n≥2這個遞歸方程的解為Catalan數(shù)由此可見，矩陣鏈乘完全加上括號的個數(shù)為n的指數(shù)次冪，因此，窮舉法不是一個有效的方法。以下研究如何用動態(tài)規(guī)劃解該問題。研制一個動態(tài)規(guī)劃算法的步驟如下：(1)刻畫矩陣鏈乘問題的最優(yōu)結(jié)構(gòu)。動態(tài)規(guī)劃范型的第一步是刻畫問題的最優(yōu)結(jié)構(gòu)，通過子問題的最優(yōu)解構(gòu)造原問題的最優(yōu)解。為簡便起見，我們用Ai..j表示矩陣乘積AiAi+1…Aj的結(jié)果，其中i≤j。如果問題是非平凡的，即i<j，那么乘積AiAi+1…Aj一定在Ak與Ak+1之間被分裂，i≤k<j，即對于某些k值，首先要計算Aj..k與Ak+1..j，然后計算它們的乘積，得到最終結(jié)果Ai..j。問題AiAi+1…Aj被完全加上括號的開銷等于計算矩陣Ai..k與計算矩陣Ak+1..j的開銷，再加上它們結(jié)果相乘的開銷。問題的最優(yōu)子結(jié)構(gòu)刻畫如下：假定問題AiAi+1…Aj被完全加上括號的最優(yōu)方式是在Ak與Ak+1處分裂，那么分裂之后，最優(yōu)解AiAi+1…Aj中的子鏈AiAi+1…Ak一定是問題AiAi+1…Ak的最優(yōu)加括號方式。我們用反證法證明這一點。如果問題AiAi+1…Ak存在更小開銷的加括號方式，我們可以用這個更小開銷的加括號方式代替問題AiAi+1…Aj中的子問題AiAi+1…Ak的加括號方式,這樣就產(chǎn)生問題AiAi+1…Aj的另一種具有更小開銷的加括號方式,這與問題AiAi+1…Aj具有最優(yōu)解(具有最小開銷)矛盾?？捎妙愃品椒ㄗC明，最優(yōu)解AiAi+1…Aj中的子鏈Ak+1Ak+2…Aj一定也是問題Ak+1Ak+2…Aj的最優(yōu)加括號方式?，F(xiàn)在，我們利用最優(yōu)子結(jié)構(gòu)構(gòu)造問題的最優(yōu)解。正如已經(jīng)表明的那樣，非平凡矩陣鏈乘問題都會對矩陣進行分割，而分割的位置是未定的，需要我們確定，使得問題的最優(yōu)解一定包含子問題的最優(yōu)解，我們稱這個性質(zhì)為問題的最優(yōu)子結(jié)構(gòu)(optimalsubstructure)。由此，我們可以建立矩陣鏈乘問題的遞歸解。(2)遞歸定義矩陣鏈乘問題最優(yōu)解的值。根據(jù)子問題的最優(yōu)解遞歸地定義問題最優(yōu)解的開銷。設m［i,j］表示計算Ai..j所需的最少乘法次數(shù)，對于原問題，計算A1..n的最少開銷則為m［1,n］。m［i,j］遞歸定義如下:如果i=j，則為平凡問題。子問題中只有一個矩陣，即Ai..i=Ai，不需數(shù)乘。因此，對于i=1，2，…，n，m［i,i］=0。如果i<j，可以利用第一步中得出的最優(yōu)解結(jié)構(gòu)，構(gòu)造問題的最優(yōu)解。假設最優(yōu)加括號方式將乘積AiAi+1…Aj分裂為AiAi+1…Ak和Ak+1Ak+2…Aj，其中i≤k<j，則m［i,j］等于計算子乘積Ai..k和Ak+1..j的最小開銷，再加上將這兩個結(jié)果矩陣相乘的開銷。由前定義，矩陣Ai的維數(shù)為pi-1×pi，因此計算矩陣乘積Ai..k×Ak+1..j需要pi-1pkpj次數(shù)乘。所以，m［i,j］=m［i,k］+m［k+1,j］+pi-1pkpj因為k有j-i種選擇，即k=i，i+1，…，j-1。最優(yōu)加括號方式一定利用某個k值，我們只需逐個檢查，找出最優(yōu)的。因此，矩陣乘積AiAi+1…Aj加括號的最小開銷的遞歸定義變?yōu)閕=j

i<j

(3.4)m［i,j］給出了子問題最優(yōu)解的值。為了記錄構(gòu)造最優(yōu)解的過程，設s［i,j］表示將AiAi+1…Aj分裂產(chǎn)生最優(yōu)解時k的位置，即s［i,j］等于值k，滿足m［i,j］=m［i,k］+m［k+1,j］+pi-1pkpj。(3)計算矩陣鏈乘最優(yōu)解的值。為了正確實現(xiàn)自底向上方法，我們必須決定m表中的哪個元素用于計算m［i,j］。式(3.4)表明，計算j-i+1個矩陣乘積的開銷m［i,j］只取決于計算矩陣Ai..k與Ak+1..j的開銷，其中k=i，k+1，…，j-1。因此，我們可以按照矩陣鏈長度增加的方式填充表格。1n←length［p］-12for

i←1to

n

3do

m［i,i］←04for

l←2to

n

5dofor

i←1to

n-l+16do

j←i+l-17m［i,j］←∞8for

k←i

toj-19 do

q←m［i,k］+m［k+1,j］+pi-1pkpj

10 Ifq<m［i,j］11 then

m［i,j］←q

12 s［i,j］←k

13return

mands

首先，對于i=1，2，…，n，算法MATRIX-CHAIN-ORDER計算出m［i,i］=0，即鏈長度為1的最小開銷。然后，在第4~12行循環(huán)的第一次執(zhí)行中，利用遞歸方程(3.3)計算m［i,i+1］，i=1，2，…，n-1，即鏈長度為2的最小開銷。第二次執(zhí)行中，計算m［i,i+2］，i=1，2，…，n-2，即鏈長度為3的最小開銷，依次類推。在每一步計算m［i,j］時，只需要表m［i,k］和m［k+1,j］中已計算出的值。計算m［i,j］的次序如圖3-6所示。圖3-6m［i,j］的計算次序注意,矩陣Ai的維數(shù)為pi-1×pi。給定n=6，p=〈p0,p1,…,pn〉=〈30,35,15,5,10,20,25〉。首先設m［i,i］=0，然后依次計算j-i=1，j-i=2，…，j-i=n-1時m［i,j］的值。我們按照如下步驟計算問題的最優(yōu)解的值：(a)m［i,i］=0，i=1，2，…，6,如圖3-7(a)所示。(b)當j-i=1時，m［1,2］，m［2,3］，m［3,4］，m［4,5］和m［5,6］的計算結(jié)果及其對應的s表如圖3-7(b)所示。(c)當j-i=2時，m［1,3］，m［2,4］，m［3,5］和m［4,6］的計算結(jié)果及其對應的s表如圖3-7(c)所示。(d)當j-i=3時，m［1,4］，m［2,5］和m［3,6］的計算結(jié)果及其對應的s表如圖3-7(d)所示。(e)當j-i=4時，m［1,5］和m［2,6］的計算結(jié)果及其對應的s表如圖3-7(e)所示。(f)當j-i=5時，m［1,6］的計算結(jié)果及其對應的s表如圖3-7(f)所示。在m表中，利用表的主對角線和下三角部分。而在s表中，只利用表的下三角部分。6個矩陣相乘的最少數(shù)乘次數(shù)為m［1,6］=15125。在計算m［2,4］時，要用到已計算出的m［2,2］，m［2,3］，m［3,4］和m［4,4］：且s［2,4］=k=3由算法MATRIX-CHAIN-ORDER的嵌套循環(huán)結(jié)構(gòu)可得，算法的復雜度為O(n3)。算法第2~3行需要O(n)時間單位，第4~12行的三層嵌套循環(huán)需要O(n3)時間單位，因為每個循環(huán)下標l，i和k至多取n-1個值。算法存儲m表和s表需要的空間為Θ(n2)。因此，自底向上的動態(tài)規(guī)劃要比窮舉法的動態(tài)規(guī)劃算法有效得多。圖3-7算法MATRIX-CHAIN-ORDER計算m［i,j］和s［i,j］的值圖3-7算法MATRIX-CHAIN-ORDER計算m［i,j］和s［i,j］的值圖3-7算法MATRIX-CHAIN-ORDER計算m［i,j］和s［i,j］的值(4)構(gòu)造矩陣鏈乘問題的最優(yōu)解。盡管算法給出了計算矩陣乘積的最優(yōu)數(shù)乘次數(shù)(最優(yōu)解的值)，但我們?nèi)匀徊恢肋@些矩陣相乘的次序。從存儲在s表中的信息不難構(gòu)造問題的一個最優(yōu)解。s［i,j］中的每個元素記錄著AiAi+1…Aj最優(yōu)分裂的位置，即k值。由于s［1,n］是A1..n的最優(yōu)分裂位置，通過這個位置s［1,n］，我們考慮這兩個子問題A1..s［1,n］和As［1,n］+1..n，而s［1,s［1,n］］記錄問題A1..s［1,n］最優(yōu)分裂的位置，s［s［1,n］+1,n］記錄問題As［1,n］+1..n最優(yōu)分裂的位置，因此，以下過程OUTPUT-OPTIMAL-PARENS輸出〈Ai，Ai+1，…，Aj〉的最優(yōu)加括號方法，其中s表作為已知條件輸入，并給定下標i和j。初始時，調(diào)用OUTPUT-OPTIMAL-PARENS(s,1,n)。OUTPUT-OPTIMAL-PARENS(s,i,j)1if

i=j

2thenoutput“A”i

3elseoutput“(”4OUTPUT-OPTIMAL-PARENS(s,i,s［i,j］)OUTPUT-OPTIMALPARENS(s,s［i,j］+1,j)OUTPUT“)”

上述例子調(diào)用OUTPUT-OPTIMAL-PARENS-(s,1,6)之后，產(chǎn)生輸出結(jié)果((A1(A2A3))((A4A5)A6))。3.4動態(tài)規(guī)劃的基本元素

1.最優(yōu)子結(jié)構(gòu)

動態(tài)規(guī)劃應用于組合優(yōu)化問題的第一個特征是問題自身具有最優(yōu)子結(jié)構(gòu)。在前面所討論的問題中，如果問題的最優(yōu)解包含子問題的最優(yōu)解，則問題展示了最優(yōu)子結(jié)構(gòu)。只要問題展示最優(yōu)子結(jié)構(gòu)，就為應用動態(tài)規(guī)劃提供了可能性。在動態(tài)規(guī)劃中，我們通過子問題的最優(yōu)解建立問題的最優(yōu)解。因此，我們必須仔細考慮以保證子問題的范圍包括在最優(yōu)解中。我們詳細討論0-1背包問題、矩陣鏈乘問題的最優(yōu)子結(jié)構(gòu)。在3.2節(jié)中，i個物品在背包容量為w時的最優(yōu)解，一定包括前i-1個物品的最優(yōu)解。在3.3節(jié)中，AiAi+1…Aj在Ak與Ak+1處最優(yōu)分裂，所產(chǎn)生的子問題AiAi+1…Ak和Ak+1Ak+2…Aj，一定分別是這兩個子問題的最優(yōu)加括號方式。因此，在尋找問題的最優(yōu)子結(jié)構(gòu)時，問題具有以下公共結(jié)構(gòu)：(1)問題的解由一系列決策組成。在背包問題中，是選擇一個物品是否放在背包中；在矩陣鏈乘問題中，是選擇分裂矩陣的一個下標。(2)對于給定的問題，假定已知一個選擇導致最優(yōu)解。你不需關心如何做出這個選擇,只需假定它是已知的。(3)給定這個決策，你來決定哪些子問題最好地刻畫子問題的其余空間。(4)證明在問題最優(yōu)解中所用到的子問題的解，通過使用“切割—粘貼”技術，一定是最優(yōu)的。這可以通過假定子問題的解不是最優(yōu)的，然后導出與問題最優(yōu)解相矛盾的結(jié)論。在證明過程中，把不是子問題最優(yōu)解的解切割出去，粘貼上子問題的最優(yōu)解，就可以得到比原問題更好的一個解，這與初始時假定原問題具有最優(yōu)解相矛盾。如果有多個子問題，明的過程十分相似，只需做少量修改。為了刻畫子問題的空間，一個好的原則是盡可能保持這個空間簡單，然后在需要的時候擴展它。例如，0-1背包問題的子空間就是空間為w時前i個物品的最優(yōu)裝包方式。相反，假定我們試圖將矩陣鏈乘問題的子空間限制到形如A1A2…Aj的形式，如前所述，最優(yōu)的加括號方式一定將這個乘積在Ak與Ak+1處分裂，1≤k<j。除非我們能夠保證k總是等于j-1，否則我們就會得到形如A1A2…Ak和Ak+1Ak+2…Aj的子問題，而后者不是形如A1A2…Aj的子問題。因此，對于矩陣鏈乘問題，子問題需要在兩端都可變化，即在子問題AiAi+1…Aj的兩端i和j處都可改變。最優(yōu)子結(jié)構(gòu)隨問題域的變化有兩種方式：(1)原問題的最優(yōu)解中，利用了多少個子問題？(2)決定最優(yōu)解中使用哪些子問題需做多少次決策？在0-1背包問題中，子問題為i個物品在背包容量為w時的最優(yōu)解，它一定包括前i-1個物品的最優(yōu)解。最優(yōu)解利用兩個子問題，每個子問題需要做w(1≤w≤W)次決策，以便決定一個最優(yōu)解。為了找到子問題c［i,

w］的最優(yōu)裝包方式，我們或者利用子問題c［i-1,w］的最優(yōu)裝包方式，或者利用子問題c［i-1,w-wi］的最優(yōu)裝包方式。不論使用哪一個子問題，都表示要最優(yōu)解決那個子問題。動態(tài)規(guī)劃算法的運行時間取決于兩個因素的乘積：所有子問題的數(shù)目以及對于每個子問題需要做出多少次決策。在0-1背包問題中，共有Θ(n)個子問題，每個子問題至多需要做出W次決策，即需要檢查W次才能確定子問題的最優(yōu)解，因此，運行時間為O(nW)。對于矩陣鏈乘問題，共有Θ(n2)個子問題，每個子問題至多需要做出n-1次決策，因此運行時間為O(n3)。當我們應用動態(tài)規(guī)劃技術時，需要關注遇見的如下問題。當問題的最優(yōu)子結(jié)構(gòu)不存在時，就不能假設應用最優(yōu)子結(jié)構(gòu)。考慮如下兩個問題，在這兩個問題中，給定有向圖G=(V,E)和頂點u，v∈V。一個問題是最短路徑問題：找一條從u到v包含最少邊的簡單路徑。另一個問題是最長簡單路徑問題：找一條從u到v包含最多邊的簡單路徑。我們要求路徑是簡單的，原因是一旦路徑中包含回路，則可以多次遍歷這個回路，使得這條路徑上具有無限多條邊。下面來分析這兩個問題最優(yōu)子結(jié)構(gòu)的存在性。最短路徑問題展示了最優(yōu)子結(jié)構(gòu)。假定u≠v，問題是非平凡的。從u到v的任何路徑p包含一定包含中間結(jié)點，這個中間結(jié)點稱為w，這里w可能為u或v。因此我們可將這條路徑分為兩條子路徑 。顯然，p中邊數(shù)等于子路徑p1與p2中的邊數(shù)之和。因此，我們可以聲稱，如果p是一條從u到v的最優(yōu)路徑，即最短路徑，那么，p1一定是一條從u到w的最優(yōu)路徑。這是因為，我們可以利用“切割—粘貼”方法證明：如果存在一條從u到w的具有更少邊的路徑p1′，我們可以將路徑p1切除，并將這條更短路徑p1′粘貼進來，則得一條具有更少條邊的路徑 。這與路徑p是最優(yōu)路徑相矛盾。類似地，可證明p2一定是一條從w到v的最優(yōu)路徑。因此，求從u到v的最優(yōu)路徑可以通過考察所有中間結(jié)點w來完成，即求從u到w的最優(yōu)路徑和從w到v的最優(yōu)路徑，并選擇導致最短路徑的中間結(jié)點w。圖3-8給出了一個例子。圖3-8有向圖示例

2.重疊子問題動態(tài)規(guī)劃應用于組合優(yōu)化問題的第二個特征是問題自身具有重疊子問題。這些子問題的空間可以足夠小，以至于問題的遞歸算法可以多次解相同子問題,并且不同子問題的個數(shù)是問題規(guī)模的多項式函數(shù)。當遞歸算法反復重新訪問相同問題時，我們說優(yōu)化問題具有重疊子問題。而用分治方法所解的問題，通常在遞歸的每一步產(chǎn)生新的子問題。動態(tài)規(guī)劃算法只計算一次子問題，并將它們存儲在一張表中，當需要時直接查找這張表。查表時間為常量時間。我們以矩陣鏈乘問題為例，詳細說明重疊子問題的性質(zhì)。參照圖3-9，在解更大一層子問題時，算法MATRIX-CHAIN-ORDER不斷檢查更小一層子問題的解。例如，在計算m［2,4］、m［1,4］、m［3,5］和m［3,6］時，元素m［3,4］共被調(diào)用4次。如果每次m［3,4］都被重新計算，而不是查找，那么運行時間上的增加將會是急劇上升的。為了更清楚地看清這一點，考慮以下效率不太高的計算m［i,j］的遞歸過程RECURSIVE-MATRIX-CHAIN，m［i,j］表示計算矩陣乘積Ai..j=AiAi+1…Aj所需的最少數(shù)乘次數(shù)。圖3-9RECURSIVE-MATRIX-CHAIN(p,1,4)的遞歸樹RECURSIVE-MATRIX-CHAIN(p,i,j)1ifi=j2thenreturn03m［i,j］←∞4for

k←i

to

j-15do

q←RECURSIVE-MATRIX-CHAIN(p,i,k) +RECURSIVE-MATRIX-CHAIN(p,k+1,j)+pi-1pkpj

6ifq<m［i,j］7thenm［i,j］←q8returnm［i,j］圖3-9顯示調(diào)用RECURSIVE-MATRIX-CHAIN(p,1,4)所產(chǎn)生的遞歸樹。樹中的每個結(jié)點標以參數(shù)i和j的值。由圖可見，許多參數(shù)對在圖中出現(xiàn)多次。事實上，我們可以證明，這個遞歸過程計算m［1,n］的時間至少為n的指數(shù)時間。設T(n)表示RECURSIVE-MATRIX-CHAIN計算n個矩陣鏈乘的最優(yōu)加括號方式的時間。如果假設1、2行和6、7行每個至少執(zhí)行一個單位時間,那么，

T(i)(i=1,2,:,n-1)在T(k)和T(n-k)中各出現(xiàn)一次。重寫遞歸方程，可得利用替換方法，可以證明T(n)=Ω(2n)。尤其是證明n≥1時，T(n)≥2n-1?；A為T(1)≥1=20，對于n≥2，可得證畢。由此可得，RECURSIVEMATRIXCHAIN算法的時間復雜度至少為n的指數(shù)函數(shù)。比較這個自頂向下的遞歸算法與自底向上的動態(tài)規(guī)劃算法，可見后者更有效，因為它充分利用了重疊子問題的性質(zhì)，只有Θ(n2)個不同子問題，并且動態(tài)規(guī)劃算法只解這些子問題一次。只要是在遞歸樹中遇見的子問題，遞歸算法都進行求解。當問題的自然遞歸樹中包含相同子問題且不同子問題數(shù)目少時，可以考慮用動態(tài)規(guī)劃方法求解。我們常常將對子問題做出的選擇存儲在一張表中，以便可以利用這個信息得到問題的最優(yōu)解。在矩陣鏈乘問題中，當重構(gòu)最優(yōu)解時，表s［i,j］存儲了重要信息。假定我們沒有維持s［i,j］表，而只填充了包含子問題最優(yōu)開銷的表m［i,j］。在求AiAi+1…Aj的最優(yōu)加括號方式時，我們有j-i種選擇，來決定哪些子問題使AiAi+1…Aj的乘積達到最優(yōu)。(j-i不是常量。)因此，如果我們將AiAi+1…Aj分裂處的下標存儲在表s［i,j］中，那么我們只需O(1)時間就可重構(gòu)每次選擇。3.5備忘錄方法備忘錄遞歸算法將每個子問題的計算結(jié)果存放在表中。表中的每個輸入用一個特殊值進行初始化，這個特殊值表明這個輸入需要被計算并填充。當遞歸算法在執(zhí)行中，首次遇見該位置處的子問題時，就計算該子問題，并將計算結(jié)果存儲在表中該位置處。當在以后遇見這個子問題時，通過查表返回該值。這種方法預示著已知了所有子問題的參量集合，并且表位置和子問題之間的關系已經(jīng)確立。另一種記錄的方法是利用子問題參數(shù)作為哈希函數(shù)關鍵字的方法。以下是矩陣鏈乘問題的備忘錄算法。MEMOIZED-MATRIX-CHAIN(p)1n←length［p］-12for

i←1to

n

3dofor

j←i

to

n

4do

m［i,j］←∞5returnLOOKUP-CHAIN(p,1,n)LOOKUPCHAIN(p,1,n)1if

m［i,j］<∞2thenreturn

m［i,j］3if

i=j

4then

m［i,j］←05elsefor

k←i

to

j-1do

q←LOOKUP-CHAIN(p,i,k)+LOOKUP-CHAIN(p,k+1,j)+pi-1pkpj

7if

q<m［i,j］8then

m［i,j］←q9return

m［i,j］我們?nèi)砸詐=〈p0,p1,…,pn〉=〈30,35,15,5,10,20,25〉為例說明備忘錄算法的計算過程。在初始化m［i,j］后(執(zhí)行算法MEMOIZED-MATRIX-CHAIN后)，m［i,j］中的所有元素初始化為∞。算法返回LOOKUP-CHAIN(p,1,6)。為簡便起見，我們省略過程中參數(shù)p。圖3-10說明了LOOKUP-CHAIN(p,1,6)的計算過程。其中，每張表中淺色陰影部分表示更新，深色陰影表示查表直接返回該處結(jié)果。在圖3-10(a)中，初始化m［i,j］←∞，其中i，j=1，2，…，6。圖3-10LOOKUP-CHAIN(p,1,6)的計算過程圖3-10LOOKUP-CHAIN(p,1,6)的計算過程在圖3-10(c)中，q=LOOKUP-CHAIN(1,2)+LOOKUP-CHAIN(3,6)+p0p2p6

且q<m［1,6］,執(zhí)行更新操作m［1,6］←q。其中需要計算m［1,2］，如淺色陰影所示。而m［3,6］可查表直接返回結(jié)果，如深色陰影所示。在圖3-10(d)中，q=LOOKUP-CHAIN(1,3)+LOOKUP-CHAIN(4,6)+p0p3p6=7875+3500+30×5×25=15125LOOKUP-CHAIN(1,3)=min{LOOKUP-CHAIN(1,1)+LOOKUP- CHAIN(2,3)+p0p1p3,LOOKUP- CHAIN(1,2)+LOOKUP-HAIN(3,3)+p0p2p3} =min{7875,18000}=7875且q<m［1,6］,執(zhí)行更新操作m［1,6］←q。其中需要計算m［1,3］，m［2,3］，如淺色陰影所示。而m［1,2］，m［4,6］可查表直接返回結(jié)果，如深色陰影所示。在圖3-10(e)中，q=LOOKUP-CHAIN(1,4)+LOOKUP-CHAIN(5,6)+p0p4p6=9375+5000+30×10×25=21875LOOKUP-CHAIN(1,4)=min{LOOKUP-CHAIN(1,1)+LOOKUP- CHAIN(2,4)+p0p1p4,=LOOKUP- CHAIN(1,2)+LOOKUP-CHAIN(3,5) +p0p2p4,=LOOKUP-HAIN(1,3)+LOOKUP- CHAIN(4,4)+p0p3p4} =min{14875,21000,9375}=9375且q>m［1,6］,不執(zhí)行更新操作m［1,6］←q。其中需要計算m［1,4］，m［2,4］，m［3,4］，如淺色陰影所示。而m［1,2］，m［1,3］，m［2,3］，m［5,6］可查表直接返回結(jié)果，如深色陰影所示。在圖3-10(f)中，q=LOOKUP-CHAIN(1,5)+LOOKUP-CHAIN-(6,6)+p0p5p6

=11875+30×20×25=26875LOOKUP-CHAIN(1,5)=min{LOOKUP-CHAIN(1,1)+LOOKUP- CHAIN(2,5)+p0p1p5, LOOKUP-CHAIN(1,2)+LOOKUP- CHAIN(3,5)+p0p2p5, LOOKUP-CHAIN(1,3)+LOOKUP- CHAIN(4,5)+p0p3p5}LOOKUP- CHAIN(1,4)+LOOKUP-CHAIN(5,5)+p0p4p5} =min{28125,24750,11875,15375}=11875圖3-11背包算法的遞歸結(jié)構(gòu)圖3-11表示背包容余量為14時的背包算法的遞歸結(jié)構(gòu)。typedefstruct{intweight;intval;}Item;intRECURKNAP(intX){inti,space,max,t;

for(i=0,max=0;i<n;i++)

if((space=X-items［i］.weight)>=0))

if((t=RECURKNAP(space)+items［i］.val)>maxmax=t;returnmax;}圖3-12背包問題的動態(tài)規(guī)劃算法結(jié)構(gòu)intTopDown-KNAP(intW){inti,space,max,maxi,t;

if(maxKnown［W］![KG-*3]=unknown)returnmaxKnown［W］;//可用一個觀察哨表示unknown的值

for(i=0,max=0;i<N;i++)

if((space=W-items［i］.weight)>=0)

if((t=TopDown-KNAP(space)+items［i］.val)>max){max=t;maxi=i;}maxKnown［W］=max;itemKnown［W］=items［maxi］;

returnmax;}改進后的算法TopDown-KNAP將復雜度從指數(shù)級降到線性級(當W不為n的指數(shù)級函數(shù)時)，即運行時間與nW成正比。在程序中，簡單地存儲已計算過的函數(shù)值。當進行遞歸調(diào)用時，查找存儲函數(shù)值的表，若表中存在該值，則返回該值，否則進行遞歸調(diào)用。在表中將所有值初始化為觀察哨，然后存儲物品的下標，當計算完成后，可以重構(gòu)背包內(nèi)的物品。如果物品itemKnown［W］在背包中，其余的物品在背包容量為W-itemKnown［W］.weight的背包中產(chǎn)生最優(yōu)解,那么itemKnown［W-item［W］.weight］在背包中，依次類推。在自頂向下的動態(tài)規(guī)劃技術中，我們存儲已知的值。在自底向上的動態(tài)規(guī)劃技術中，我們預先進行計算。自頂向下的動態(tài)規(guī)劃方法具有如下特點：·它是一種對自然問題求解的機械轉(zhuǎn)換?！し椒ㄗ陨砜梢源_定計算子問題的順序。·可能不需要計算出所有子問題的解。3.6裝配線調(diào)度問題如圖3-13所示，某公司在生產(chǎn)汽車過程中使用兩條裝配線。當汽車底盤進入每條裝配線時，在許多站點裝配零件。在每條線結(jié)束時，自動完成下線工作。每條裝配線有n個站點，標號為j=1，2，…，n。我們用Si,j表示第i條裝配線上第j個站點，其中i=1，2。第1條裝配線上的第j個站點S1,j與第2條裝配線上的第j個站點S2,j的作用相同。由于站點建立的時間及技術不同，因此每個站點所需的時間不同，即使在兩條不同裝配線對應的同一站點，也會不同。用bi,j表示在Si,j處所需的裝配時間，ei表示進入裝配線i的進入時間，oi表示退出裝配線i的退出時間。圖3-13尋找以最快方式通過工廠的制造問題在一般情況下，當一個底盤進入某條裝配線時，它只通過那條裝配線，在同一條裝配線上從一個站點到下一個站點的時間可忽略不計；有時候，當特殊情況訂購出現(xiàn)時，顧客希望汽車盡可能快地制造出來。此時，底盤仍然按照次序通過每一站點，但是工廠主可能將部分完成的汽車從一條裝配線切換到另一條裝配線。假設通過站點Si,

j后，底盤離開裝配線i的轉(zhuǎn)移時間為ti,j，其中i=1，2和j=1，2，…，n-1。問題是要決定通過哪些站點完成一輛汽車的裝配，使得裝配時間達到最小。如果采用窮舉法解決這個問題，那么最小化裝配時間是不可行的。這是因為在每個站點上我們都有兩種選擇，所以有2n種選擇站點的方式。因此，通過枚舉所有可能的路線，計算所需時間為Ω(2n)。當n較大時，這是不可行的。我們?nèi)匀挥脛討B(tài)規(guī)劃解決這個問題。(1)分析裝配線調(diào)度問題最優(yōu)解的結(jié)構(gòu)。動態(tài)規(guī)劃的第一步是分析問題最優(yōu)解的結(jié)構(gòu)。對于裝配線調(diào)度問題，考慮一個底盤從開始點到通過站點S1,j的最快方式，如果j=1，只有惟一一種方式通過S1,j。對于j=2，3，…，n，則有兩種選擇：一種方式是底盤從S1,j-1直接到S1,j，同一條線上從站點j-1到站點j的時間可忽略不計，另一種方式是底盤從S2,j-1經(jīng)轉(zhuǎn)移到S1,j，轉(zhuǎn)移時間為t2,j-1。我們分別考慮這兩種情形。首先，假定通過S1,j-1以最快方式到達S1,j，那么，底盤一定以最快的方式從開始點達到S1,j-1。這是因為，如果存在通過S1,j-1的更快方式，我們可以用這條更快方式得到一條通過S1,j的更快方式，這與S1,j是最快方式相矛盾。同樣，假定通過S2,j-1以最快方式到達S1,j，那么，底盤一定以最快的方式從開始點到達S2,j-1。原因是相同的。這是因為，如果存在通過S2,j-1的更快方式，則可以用這條更快方式得到一條通過S1,j的更快方式，這與S1,j是最快通過方式相矛盾。更一般地說，對于裝配線調(diào)度問題(assemblylineschedulingproblem)，問題的一個最優(yōu)解(找出通過S1,j的最優(yōu)解)包含子問題的最優(yōu)解(找出通過S1,j-1的最優(yōu)解或找出通過S2,j-1的最優(yōu)解)，裝配線調(diào)度問題具有最優(yōu)子結(jié)構(gòu)。問題的最優(yōu)子結(jié)構(gòu)表明，我們可以通過子問題的最優(yōu)解構(gòu)造問題的最優(yōu)解。對于裝配線調(diào)度問題，推理如下：考慮最快通過站點S1,j的方式，它一定通過裝配線1或者裝配線2的站點S1,j-1。因此，最快通過站點S1,j的方式或者通過站點S1,j-1并直接通過站點S1,j，或者通過站點S2,j-1并從裝配線2轉(zhuǎn)移到裝配線1，然后通過站點S1,j。由對稱性可得，通過站點S2,j的方式或者通過站點S2,j-1并直接通過站點S2,j，或者通過站點S1,j-1并從裝配線1轉(zhuǎn)移到裝配線2，然后通過站點S1,j。(2)遞歸定義裝配線調(diào)度問題最優(yōu)解的值。設fi［j］表示從開始點到通過站點Si,j的最快時間，f*表示底盤從開始點經(jīng)過工廠所有最優(yōu)站點到輸出的最快時間，則有f*=min{f1［n］+o1,f2［n］+o2}顯然，f1［1］=e1+b1,1f2［1］=e2+b2,1

(3.6)(3.7)(3.5)以下推導fi［j］的計算過程，其中j=2，3，…，n；i=1，2。先看f1［j］的計算。經(jīng)過上述討論，得知最快通過S1,j的方式或者通過站點S1,j-1并直接通過站點S1,j，或者通過站點S2,j-1并從裝配線2轉(zhuǎn)移到裝配線1，然后通過站點S1,j。在前一種情形下，f1［j］=f1［j-1］+b1,j

在后一種情形下，f1［j］=f2［j-1］+t2,j-1+b1,j

因此，f1［j］=min{f1［j-1］+b1,j，f2［j-1］+t2,j-1+b1,j}，j=2，3，…，n由對稱性，可得f2［j］=min{f2［j-1］+b2,j，f1［j-1］+t1,j-1+b2,j}，j=2，3，…，n因此，j=1j≥2(3.8)j=1j≥2(3.9)圖3-14裝配線調(diào)度問題示例

fi［j］的值給出了子問題最優(yōu)解的值。為了記錄如何構(gòu)造一個最優(yōu)解，我們用li［j］表示裝配線號，其值為1或2，表示最快通過Si,j的站點j-1所在的裝配線。這里，j=2，3，…，n；i=1，2。這里不定義li［1］的原因是，無論是哪一條線，在它之前都沒有站點。用l*表示最快通過站點n所在的裝配線。

f*=38表示最快通過工廠所用時間。f1［3］=min{f1［2］+b1,3，f2［2］+t2,2+b1,3}=min{18+3，16+1+3}=20，對應的l1［3］=2，表示通過裝配線1的第3個站點時，是從裝配線2轉(zhuǎn)移到裝配線1得到的。借助li［j］的值可以求得最快通過工廠的方式，即經(jīng)過哪條裝配線、哪些站點。由l*=1可得，表示從第一條裝配線站點S1,n下線。然后看l1［6］=2，表示通過站點S2,5(裝配線2)轉(zhuǎn)移到站點S1,6(裝配線1)。下一個考察l2［5］，為2，表示通過站點S2,4(裝配線2)直接到站點S2,5。l2［4］=1，表示通過站點S1,3(裝配線1)轉(zhuǎn)移到站點S2,4(裝配線2)。l1［3］=2，表示通過站點S2,2(裝配線2)轉(zhuǎn)移到站點S1,3(裝配線1)。l2［2］=1，表示通過站點S1,1(裝配線1)轉(zhuǎn)移到站點S2,2(裝配線2)。(3)計算裝配線調(diào)度問題的最快時間。根據(jù)式(3.4)、式(3.5)和式(3.6)，很容易寫一個遞歸算法。但是這樣的遞歸算法，它的運行時間為n的指數(shù)級。以下做出分析。設ri(j)表示遞歸算法中調(diào)用fi［j］的數(shù)目，由式(3.4)可得r1(n)=r2(n)=1(3.10)由式(3.7)和式(3.8)可得r1(j)=r2(j)=r1(j+1)+r2(j+1)，j=1,2,…,n-1(3.11)如果我們按照不同于遞歸調(diào)用的次序計算fi［j］，則可以做得更好。觀察可見，對于j≥2，每個fi［j］的值只依賴于f1［j-1］和f2［j-1］。按照站點號j遞增的次序計算fi［j］的值，即按從左到右的次序計算，此時運行時間為Θ(n)。過程以bi,j、ti,j、ei、oi和n作為輸入。FASTEST-WAY(b,t,e,o,n)1f1［1］←e1+b1,1

2f2［1］←e2+b2,1

3for

j←2to

n

4doif

f1［j-1］+b1,j≤f2［j-1］+t2,j-1+b1,j5then

f1［j］←f1［j-1］+b1,j

6l1［j］←17elsef1［j］←f2［j-1］+t2,j-1+b1,j

8l1［j］←29if

f2［j-1］+b2,j≤f1［j-1］+t1,j-1+b2,j

10then

f2［j］←f2［j-1］+b2,j

11l2［j］←212else

f2［j］←f1［j-1］+t1,j-1+b2,j

13l2［j］←114if

f1［n］+o1≤f2［n］+o2

15then

f*=f1［n］+o1

16l*=117else

f*=f2［n］+o2

18l*=2(4)構(gòu)造裝配線調(diào)度的最優(yōu)解。計算出fi［j］、li［j］、f*和l*之后，我們可以構(gòu)造出最快方式通過哪些站點。過程OUTPUT-STATION按照站點號遞增的次序輸出。OUTPUT-STATION(l,i,j)1if

j=0thenreturn

2OUTPUT-STATION(l,li［j］,j-1)3print“l(fā)ine”i“,station”j

如要輸出所有站點，需調(diào)用OUTPUT-STATION(l,l*,n)。在圖3-13的示例中，OUTPUT-STATION將產(chǎn)生如下輸出：line1,station1line2,station2line1,station3line2,station4line2,station5line1,station63.7最長公共子序列(1)刻畫LCS問題的最優(yōu)子結(jié)構(gòu)。如果利用窮舉法解LCS問題，列舉出X的所有子序列，檢查每個子序列是否是Y的一個子序列，記錄所找到的最長子序列，X的每個子序列與X的下標集{1,2,…,n}的一個子集對應，X共有2m個子序列，因而，這種方法具有指數(shù)級的復雜度。因此，對于長序列，這種方法不可行。借助圖3-15，定理3.1證明了LCS問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。給定序列X=〈x1,x2,…,xm〉，定義Xi=〈x1,x2,…,xi〉為X的第i個前綴，其中i=0,1,…,m。例如，如果X=〈B,A,C,A,D,A,B〉，X3=〈B,A,C〉，X0為空序列。圖3-15LCS問題的最優(yōu)子結(jié)構(gòu)

定理3.1LCS的最優(yōu)子結(jié)構(gòu)。設X=〈x1,x2,…,xm〉和Y=〈y1,y2,…,yn〉是兩條序列，Z=〈z1,z2,…,zk〉是X和Y的任一LCS。(i)如果xm=yn，那么zk=xm=yn，且Zk-1是Xm-1和Yn-1的一條最長公共子序列。(ii)如果xm≠yn，那么zk≠xm，蘊含著Z是Xm-1和Y的一條最長公共子序列。(iii)如果xm≠yn，那么zk≠yn，蘊含著Z是X和Yn-1的一條最長公共子序列。證明：(i)如果zk≠xm，那么，我們可以將xm=yn添加到序列Z后，得到X和Y的一條長度為k+1的公共子序列，這與Z是X和Y的最長公共子序列矛盾。因此，一定會有zk=xm=yn。現(xiàn)在，前綴Zk-1是Xm-1和Yn-1的長度為k-1的公共子序列。我們要證明，這條子序列是最長公共子序列。假定存在Xm-1和Yn-1的長度大于k-1的公共子序列W，則將xm=yn添加到序列W后，產(chǎn)生X和Y的長度大于k的公共子序列，這與k是最長公共子序列的長度相矛盾。(ii)如果zk≠xm，則Z是Xm-1和Y的一條公共子序列。如果存在Xm-1和Yn-1的長度大于k的公共子序列W，那么W也會是Xm和Y的公共子序列，這與Z是X和Y的LCS的假設相矛盾。(iii)如果zk≠yn，則Z是X和Yn-1的一條公共子序列。如果存在Xm-1和Yn-1的長度大于k的公共子序列W，那么W也會是X和Yn的公共子序列，這與Z是X和Y的LCS的假設相矛盾。證畢。定理3.1表明，兩條序列的LCS包含兩條序列前綴的LCS。因此，LCS問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，其遞歸解具有重疊子問題性質(zhì)。(2)遞歸定義LCS問題最優(yōu)解的值。定理3.1表明，當求X=〈x1,x2,…,xm〉和Y=〈y1,y2,…,yn〉的一條最長公共子序列時，需要考察一個或兩個子問題。如果xm=yn，我們一定要找Xm-1和Yn-1的LCS。將xm=yn添加到這條LCS之后，就得到X和Y的LCS。如果xm≠yn，則必須解兩個子問題，這就是求Xm-1和Y以及X和Yn-1這兩個子問題的解。這兩個子問題中較長的LCS就是X和Y的LCS。因為這些情形已經(jīng)窮舉了所有可能性，我們知道其中的最優(yōu)子問題一定是X和Y的一條LCS。我們可以容易地表明，LCS問題具有重疊子問題性質(zhì)。要求出X和Y的LCS，必須求出Xm-1和Y以及X和Yn-1這兩個子問題的LCS。但這兩個子問題都以Xm-1和Yn-1的LCS作為子問題。許多其他子問題共享子問題。設l［i,j］表示序列Xi和Yj的LCS的長度，如果i=0或j=0，則其中有一個序列長度為0，因此，LCS長度為0。由LCS問題的最優(yōu)子結(jié)構(gòu)可導出以下遞歸公式：i=0或j=0i,j>0且xi=yj

i,j>0且xi≠yj

(3.12)(3)計算LCS最優(yōu)解的值?；诜匠?3.12)，我們可以容易地寫一個計算兩個序列長度LCS值的指數(shù)級算法。因為只有Θ(mn)個不同的子問題，我們可以利用自底向上的動態(tài)規(guī)劃求解這一問題。過程LCS-LENGTH(X,Y)以X=〈x1,x2,…,xm〉和Y=〈y1,y2,…,yn〉作為輸入，并將l［i,j］的值存儲在表l［0..m,0..n］中，以行為主序從左到右計算表l中的元素，同時維持表b［1..m,1..n］，以簡化最優(yōu)解的構(gòu)造。當計算l［i,j］時，用b［i,j］記錄使得l［i,j］取最優(yōu)值的最優(yōu)子問題。LCSLENGTH(X,Y)1m←length［X］2n←length［Y］3for

i←1tom4dol［i,0］←05for

j←1to

n

6do

l［0,j］←07for

i←1tom8dofor

j←1to

n

9doif

xi=yj

10then

l［i,j］←l［i-1,j-1］+111b［i,j］←“”12elseif

l［i-1,j］←l［i,j-1］13then