計算理論與算法分析設(shè)計：03-dynamic-programming

動態(tài)規(guī)劃法

方法概述:發(fā)展及研究內(nèi)容動態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個分支，20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。動態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、資源分配、設(shè)備更新等問題，用動態(tài)規(guī)劃比用其它方法求解更為方便。2方法概述:基本思想動態(tài)規(guī)劃的思想實質(zhì)是分治思想和解決冗余。與分治法類似的是，將原問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，經(jīng)分解的子問題往往不是互相獨立的。若用分治法來解，有些共同部分（子問題或子子問題）被重復(fù)計算了很多次。如果能夠保存已解決的子問題的答案，在需要時再查找，這樣就可以避免重復(fù)計算、節(jié)省時間。動態(tài)規(guī)劃法用一個表來記錄所有已解的子問題的答案。這就是動態(tài)規(guī)劃法的基本思路。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表方式。3方法概述:求解步驟1、找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2、遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；3、以自底向上的方式計算出最優(yōu)值；4、根據(jù)計算最優(yōu)值時記錄的信息，構(gòu)造最優(yōu)解。注：－步驟1-3是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略；－若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息是構(gòu)造最優(yōu)解的基礎(chǔ)4方法概述:適用條件

動態(tài)規(guī)劃法的有效性依賴于問題本身所具有的兩個重要性質(zhì)最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。5方法概述:最優(yōu)性原理及舉例Bellman給出這個原理作為動態(tài)規(guī)劃的適用條件，后來Morin在1982年證明了這只是一個充分條件而非必要條件。Bellman的原定義如下：

Anoptimalpolicyhasthepropertythatwhatevertheinitialstateandinitialdecisionare,thenremainingdecisionsmustconstituteanoptimalpolicywithregardtothestateresultingfromfirstdecision.

最優(yōu)性原理又稱為最優(yōu)子結(jié)構(gòu)性質(zhì)：

如果有一決策序列包含有非最優(yōu)的決策子序列，則該決策序列一定不是最優(yōu)的。即一個最優(yōu)策略的子策略總是最優(yōu)的。6例1：多段圖的最短路問題多段圖：設(shè)G=<V,E>是一個有向連通圖，

其中|V|=n,|E|=m,V有劃分{V1,V2,···,Vk}，

這里V1={s},s稱為源點，Vk={t},t稱為

終點，其中k≥2。對于每條有向邊

<u,v>∈E都存在Vi

∈V，使得u∈Vi

和v∈Vi+1,其中1≤i<k且每條邊<u,v>均

附有代價C(u,v)，則稱G是一個k段圖。7123456789101112s97324212711118654356425V1V2V3V4V5t8最短路：從源點s到終點t的整條路上的代價之和為最小。每個子集Vi構(gòu)成圖中的一段。由于E的約束，每條從s到t的路徑都是從第一段開始，然后順次經(jīng)過第2段，第3段，···，最后在第k段終止。對于每條從s到t的路徑，可以把它看成在k-2個階段中做出的某個決策序列的相應(yīng)結(jié)果。9假設(shè)s,v2,v3,···,vk-1,t是一條從s到t的最短路徑，還假定從源點s（初始狀態(tài)）開始，已做出了到結(jié)點v2的決策（初始決策），因此v2就是初始決策所產(chǎn)生的狀態(tài)。如果把v2看成是原問題的一個子問題的初始狀態(tài)，解這個子問題就是找出一條由v2到t的最短路徑。這條路徑顯然是v2,v3,···,vk-1,t，否則設(shè)v2,q3,···,qk-1,t是一條由v2到t的更短路徑，則s,v2,q3,···,qk-1,t是一條比路徑s,v2,v3,···,vk-1,t更短的由s到t的路徑，與假設(shè)矛盾，故最優(yōu)化原理成立。10cost(i,j)=min{C(j,r)+cost(i+1,r)}

r∈Vi+1<j,r>∈EjrtViVi+1最短最短正向處理法：設(shè)P(i,j)是從Vi中的點j到t的一條最短路，cost(i,j)是這條路線的耗費。由后向前推算，得到11123456789101112s97324212711118654356425V1V2V3V4V5tcost(4,9)=4cost(i,j)=min{C(j,r)+cost(i+1,r)}

cost(4,10)=2cost(4,11)=5cost(3,6)=min{6+cost(4,9),5+cost(4,10)}=min{6+4,5+2}=7從第3段的頂點6到t的最短路徑是6-10-t5+212123456789101112s97324212711118654356425V1V2V3V4V5tcost(3,7)=min{4+cost(4,9),3+cost(4,10)}=min{4+4,3+2}=5從第3段的頂點7到t的最短路徑是7-10-tcost(3,8)=7從第3段的頂點8到t的最短路徑是8-10-t13123456789101112s97324212711118654356425V1V2V3V4V5tcost(2,2)=7從第2段頂點2到t的最短路是2-7-10-tcost(2,3)=9從第2段頂點3到t的最短路是3-6-10-tcost(2,4)=18從第2段頂點4到t的最短路是4-8-10-tcost(2,5)=15從第2段頂點5到t的最短路是5-8-10-tcost(1,1)=16從第1段頂點1到t的最短路徑有兩條：

1-2-7-10-t和1-3-6-10-t14從s到t的一條最短路徑的代價為16。用D(i,j)表示使C(j,r)+cost(i+1,r)取得最小值

的r，則在上述求解過程中同時得到：D(3,6)=10,D(3,7)=10,D(3,8)=10D(2,2)=7,D(2,3)=6,D(2,4)=8D(2,5)=8,D(1,1)=2設(shè)從s到t的最短路徑為s,w2,w3,···,wk-1,t則有w2=D(1,1)=2w3=D(2,D(1,1))=D(2,2)=7w4=D(3,D(2,D(1,1)))=D(3,D(2,2))=D(3,7)=10所以這條路徑是1-2-7-10-t所以這條路徑是1-2-7-10-t15為了便于描述算法，對一個k段圖的頂點，按段的順序給它的每個頂點編號。設(shè)圖中有n個頂點，則編號為1，2，···，n。首先，給s編為1號；然后給V2中的各個頂點分別編為2，3，···

，|V2|+1號；以此類推，最后t編號為n。這樣編號使Vi+1中的任何頂點的編號大于Vi中所有頂點的編號。于是，可以按n-1,n-2,···,1的順序計算出cost(i,j)和D(i,j)。算法中可以利用順序編號的特點，而不再考慮頂點所在的段。16設(shè)頂點的編號已知，邊已知及邊的代價函

數(shù)C(i,j)已知。用cost[i]表示頂點i到t的最小

代價，1≤i≤n。用D[i]表示從頂點i到t的最短路徑上頂點i的后繼頂點號，用P[i]表示最短路徑經(jīng)過第i級的頂點號，1≤i≤k17求兩點間最短路徑的算法：ProcedureFgraph

1.{fori←1toncost[i]←0；

2.forj=n-1step–1to1do

{

3.找頂點r,使<j,r>∈E,且C(j,r)+cost[r]最小；

4.cost[j]←C(j,r)+cost[r];

5.D[j]←r;

}

6.P[1]←1;P[k]←n;

7.forj=2tok-1doP[j]←D[P[j-1]]

}O(n+|E|)18123456789101112s97324212711118654356425V1V2V3V4V5t逆向處理法：設(shè)BPij是從源點s到Vi中頂點j的最小成本路徑，bcost(i,j)是這條路徑的代價bcost(i,j)=min{bcost(i-1,r)+C(r,j)}r∈Vi-1<r,j>∈E19格路問題：求從起點O(0,0)到終點E(m,n)的最短路。則分別用窮舉法和動態(tài)規(guī)劃法的加法次數(shù)和比較次數(shù)各是多少？E(m,n)O(0,0)xy20E(m,n)O(0,0)xy21E(m,n)O(0,0)xymn個點22例2：貨郎擔(dān)問題即旅行商問題(TravelingSalesmanProblem)有n個城市，城i,j之間的距離為dij，有一個貨郎從城1出發(fā)到其他城市一次且僅一次，最后回到城市1，怎樣選擇行走路線使總路程最短231243105209128913156810∞1015205∞910613∞12889∞v1

v2v3v4v1v2v3v4不失一般性，考慮以結(jié)點1為起點和終點的一條哈密頓回路。每一條這樣的路線都由一條邊<1,k>和一條由結(jié)點k到結(jié)點1的路徑組成，其中k∈V-{1},而這條由結(jié)點k到結(jié)點1的路徑通過V-{1，k}的每個結(jié)點各一次。如果這條周游路線是最優(yōu)的，則這條由結(jié)點k到結(jié)點1的路徑必定是通過V-{1，k}的每個結(jié)點各一次的由k到1的最短路徑。24設(shè)T(i,S)是由結(jié)點i出發(fā)，經(jīng)過結(jié)點集S中每個結(jié)點各一次并回到初始結(jié)點1的一條最

短路徑長度，則T(1,V-{1})就是一條最優(yōu)的周游路線長度。動態(tài)規(guī)劃模型：T(1,V-{1})=min{d1k+T(k,V-{1,k})}2≤k≤nT(i,s)=min{dij+T(j,S-{j})}j∈S,i?S25∞1015205∞910613∞12889∞v1

v2v3v4v1v2v3v4T(1,{2,3,4})=min{d12+T(2,{3,4}),

d13+T(3,{2,4}),d14+T(4,{2,3})}T(2,{3,4})=min{d23+T(3,{4}),d24+T(4,{3})}T(3,{4})=d34+T(4,Φ)T(4,Φ)=d4126T(1,{2,3,4})T(2,{3,4})T(3,{2,4})T(4,{2,3})T(3,{4})T(4,{3})T(2,{4})T(4,{2})T(2,{3})T(3,{2})T(4,Φ)T(3,Φ)T(4,Φ)T(2,Φ)T(3,Φ)T(4,Φ)27O(2n)NP-C矩陣鏈乘法問題描述加括號的方案數(shù)動態(tài)規(guī)劃法28矩陣鏈乘法:問題描述給定n個矩陣A1,A2,…,An,Ai的維數(shù)為

pi-1×pi(1≤i≤n),要求計算鏈乘積A1A2…An由于矩陣乘法滿足結(jié)合率，所以可以有許多不同的計算次序，這種計算次序可以用加括號的方式來確定。比如：A1,A2,A3,A4

(A1(

A2(

A3(A4)))(A1((

A2A3)A4))(A1A2)(

A3A4)((A1(

A2A3))

A4)((A1A2)

A3)A4)29不同的計算次序有不同的計算量注：1.設(shè)Ap×q,Aq×r兩矩陣相乘，普通乘法的次數(shù)為p×q×r2.加括號對乘法次數(shù)的影響如：A10×100×B100×5×C5×50((AB)C):10×100×5+10×5×50=7500次(A(BC)):100×5×50+10×100×50=75000次30窮舉法：將n個矩陣從第k和第k+1處隔開，對二個子序列再分別加括號，則可以得到下面遞歸式：因此，窮舉法不是一個有效算法311.矩陣鏈乘問題滿足最優(yōu)性原理記A[i:j]為AiAi+1…Aj鏈乘的一個最優(yōu)括號方案，設(shè)A[i:j]的最優(yōu)次序中含有二個子鏈A[i:k]和A[k+1:n]，則A[i:k]和A[k+1:n]也是最優(yōu)的。（反證可得）2.矩陣鏈乘的子問題空間：A[i:j],1≤i≤j≤nA[1:1],A[1:2],A[1:3],…,A[1:n]A[2:2],A[2:3],…,A[2:n]………A[n-1:n-1],A[n-1,n]A[n,n]32遞歸求解最優(yōu)解的值記m[i][j]為計算A[i:j]的最少乘法數(shù)，則原問題的最優(yōu)值為

m[1][n](AiAi+1…Ak)pi-1×pk×(Ak+1Ak+2…Aj)pk×pj33依據(jù)遞歸式自底向上計算。在計算過程中，保存已經(jīng)解決的子問題答案。A1,A2,A3,A4,A5,A634A1=(aij)35Х40A2=(aij)40Х20

A3=(aij)20Х10A4=(aij)10Х15m[1][3]=min{m[1][2]=m[2][3]=40Х20Х10＝8000

m[3][4]=20Х10Х15＝300035Х40Х20＝28000m[1][1]+m[2][3]+35Х40Х10,

m[1][2]+m[3][3]+35Х20Х10}m[2][4]m[1][4]m11m12m13m14m22m23m24m33m34m44

j=1234i=1

2

3

435MATRIX-CHAIN-ORDER(p)1n←

length[p]-12fori←1ton3 m[i,i]←04forl←2ton//listhechainlength.5 fori←1ton-l+16 j←

i+l-17 m[i,j]←

∞8 fork←

itoj-1{9 q←

m[i,k]+m[k+1,j]+pi-1pkpj10 ifq<m[i,j]{11 m[i,j]←

q12 s[i,j]←

k

}

}13returnmands(n3)36對角線僅含1個元素，計算量為0將i:j中的序列遍歷分割一遍選擇斜對角線上的元素下標(biāo)i與j矩陣鏈乘法:s中存放m取得最優(yōu)時k的值

行x列A1 30x35A2 35x15A3 15x5A4 5x10A5 10x20A6 20x256555443333i33322333111654321sj6543i21654321mj00000015125500035001000537525007501050071254375262511875937578751575037矩陣鏈乘法:s中存放m取得最優(yōu)時k的值6555443333i33322333111654321sjPRINT-OPTIMAL-PARENS(s,i,j)1ifi=j2 thenprint"A"i3 elseprint"("4 PRINT-OPTIMAL-PARENS(s,i,s[i,j])5 PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j)6 print")"A1,A2,A3,A4,A5,A6

((A1(A2A3))((A4A5)A6))

38重疊子問題對比分治法遞歸的每一步常常產(chǎn)生全新的子問題.39計算m[1][4]過程如下：自頂向下遞歸求解最優(yōu)解的值重疊子問題40備忘錄MEMOIZED-MATRIX-CHAIN(p)1n←

length[p]-12fori←1ton3 doforj←

iton4 dom[i,j]←

∞5returnLOOKUP-CHAIN(p,1,n)//表示該子問題尚未解決41備忘錄LOOKUP-CHAIN(p,i,j)1ifm[i,j]<∞2 thenreturnm[i,j]3ifi=j4 thenm[i,j]←05 elsefork←

itoj-16 doq←LOOKUP-CHAIN(p,i,k) +LOOKUP-CHAIN(p,k+1,j)+pi-1

pkpj7 ifq<m[i,j]8 thenm[i,j]←

q9returnm[i,j]42自底向上的動規(guī)與備忘錄區(qū)別自底向上的動規(guī)每個子問題至少求解一次.備忘錄某些子問題根本沒有必要求解.43課堂練習(xí)：貨物儲運(yùn)問題在一個鐵路沿線順序存放著n堆裝滿貨物的集裝箱。貨物儲運(yùn)公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運(yùn)輸費用與新的一堆中集裝箱數(shù)成正比。給定各堆的集裝箱數(shù)，試制定一個運(yùn)輸方案，使總運(yùn)輸費用最少。5,3,4,1,3,2,3,4為了簡化，只算5,3,4,144貨物儲運(yùn)問題在一個鐵路沿線順序存放著n堆裝滿貨物的集裝箱。貨物儲運(yùn)公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運(yùn)輸費用與新的一堆中集裝箱數(shù)成正比。給定各堆的集裝箱數(shù)，試制定一個運(yùn)輸方案，使總運(yùn)輸費用最少。5,3,4,1,3,2,3,4設(shè)合并a[i:j]，1≤i≤j≤n，所需的最少費用為m[i,j]，則原問題的最優(yōu)值為m[1，n]。由最優(yōu)子結(jié)構(gòu)性質(zhì)可知，45貨物儲運(yùn)問題5,3,4,1m11m12m13m14m22m23m24m33m34m44

j=1234i=1

2

3

4

j=1234i=1

2

3

446課堂練習(xí)：貨物儲運(yùn)問題在一個圓形操場的四周存放著n堆裝滿貨物的集裝箱。貨物儲運(yùn)公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運(yùn)輸費用與新的一堆中集裝箱數(shù)成正比。給定各堆的集裝箱數(shù)，試制定一個運(yùn)輸方案，使總運(yùn)輸費用最少。只要求給出思路。47Floyd算法A(k+1)(i,j)=min{A(k)(i,j)

,

A(k)(i,k+1)+A(k)(k+1,j)}A(k)(i,j)表示從i到j(luò)的最短路徑,且允許的中間結(jié)點是1…k04116023∞0v1

v2v3v1v2v3123643112v1

v2v3v1v2v30411602370A(1)

=48已經(jīng)是最短經(jīng)k+1中轉(zhuǎn)是最短A(k+1)(i,j)=min{A(k)(i,j)

,

A(k)(i,k+1)+A(k)(k+1,j)}A(k)(i,j)表示從i到j(luò)的最短路徑,且允許的中間結(jié)點是1…k04116023∞0v1

v2v3v1v2v3123643112v1

v2v3v1v2v30411602370A(1)

=v1

v2v3v1v2v3046

602370A(2)

=v1

v2v3v1v2v3046502370A(3)

=49

Warshall算法Mk+1[i,j]=Mk[i,j]Floyd:

A(k+1)(i,j)=min{A(k)(i,j)

,

A(k)(i,k+1)+A(k)(k+1,j)}∨(Mk[i,k+1]∧

Mk[k+1,j])50已經(jīng)連通經(jīng)k+1中轉(zhuǎn)后連通

Warshall算法Mk+1[i,j]=Mk[i,j]∨(Mk[i,k+1]∧

Mk[k+1,j])51TRANSITIVE-CLOSURE(G)1n←|V[G]|2fori←1ton3 doforj←1ton4 doifi=jor(i,j)∈

E[G]11returnT(n)

Warshall算法52依次添加入1個節(jié)點，動態(tài)獲取連通矩陣初始化添加節(jié)點k后，更新矩陣中每個元素0-1背包問題給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?0-1背包問題是一個特殊的整數(shù)規(guī)劃問題。530-1背包問題:問題描述及舉例問題描述舉例：w=(w1,w2,w3)=(2,3,4),v=(v1,v2,v3)=(1,2,5),n=3,c=6,求Knap(1,3,6)

取x=(1,0,1)時，540-1背包問題滿足最優(yōu)性原理證明：設(shè)(y1,y2,…,yn)是Knap(1,n,c)的一個最優(yōu)解，則(y2,…,yn)是Knap(2,n,c-w1y1)子問題的一個最優(yōu)解。若不然，設(shè)(z2,…,zn)是Knap(2,n,c-w1y1)的最優(yōu)解，因此有說明(y1,z2,…,zn)是Knap(1,n,c)的一個更優(yōu)解，矛盾。550-1背包問題:遞歸關(guān)系考慮子問題：

Knap(i,n,j)j≤c(假設(shè)c,wi取整數(shù))

設(shè)其最優(yōu)值為m(i,j),即m(i,j)是背包容量為j,可選物品為i,i+1,…,n的0-1背包問題的最優(yōu)值。子問題的背包容量在變化560-1背包問題:遞歸關(guān)系遞歸式如下：不取物品i取物品i57m(i,j)：從第i號物品取到n，所得到的的最優(yōu)選擇0-1背包問題:算法voidKnapsack(intv[],intw[],intc,intn,intm[][]){//需要求出m[1][c]intjMax=min(w[n]-1,c);

for(intj=0;j<=jMax;j++)m[n][j]=0;//0≤j<wn

for(intj=w[n];j<=c;j++)m[n][j]=v[n];//j≥wn

for(inti=n-1;i>1;i--){//i>1表示對i=1不處理，因為i=1時只需求m[1][c]jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)//0≤j<wi

m[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)//j≥wi

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}if(c>=w[1])m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]);elsem[1][c]=m[2][c];}58初始化遞推公式起點根據(jù)公式求m[1][c]0-1背包問題:算法（續(xù)）voidTraceback(intw[],intc,intn,intm[][],intx[]){//輸出解x[1..n]for(inti=0;i<n;i++)if(m[i][c]=m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}x[n]=(m[n][c])?1:0;}運(yùn)行時間Knapsack:T(n)=O(cn)Traceback:O(n)592022/11/6600-1背包問題:遞歸關(guān)系換一種視角遞歸式如下：不取物品i取物品i包含從1到i號物品的最優(yōu)選擇2022/11/6610-1背包問題00000pi–1(j–wi)pi–1(j)0pi(j)0目標(biāo)

0i–1in0j–wi

jM2022/11/662

例：有5個物體，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6，背包的載重量為10，求裝入背包的物體及其總價值找零錢問題:問題描述問題描述一出納員支付一定數(shù)量的現(xiàn)金。假設(shè)他手中有幾種面值的硬幣，要求他用最少的硬幣數(shù)支付規(guī)定的現(xiàn)金。

例如，現(xiàn)有3種硬幣：它們的面值分別為1元、4元和6元。要支付8元。630-1背包問題:遞歸關(guān)系不用第i種硬幣用第i種硬幣pi(j)：前i種硬幣支付金額j所需硬幣的最少個數(shù)。640∞

∞∞0pi–1(j)0pi(j–vi)pi(j)0目標(biāo)

0i–1in0j–vi

j8651元、4元和6元。要支付8元。01234567800∞∞∞∞∞∞∞∞10123456782012312342301231212266某公司準(zhǔn)備將新招聘的4名銷售員分配到下屬3個銷售點

甲、乙和丙。各銷售點增加若干名銷售員后可增加的

月銷售額如下表：增加銷售額（千元）增1人增2人增3人增4人甲12223038乙11202430丙13253036根據(jù)此表，只要人員分配適當(dāng)，公司每月最多

可以增加銷售額（）千元。動規(guī)練習(xí)67最長公共子序列若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2，3，5，7}。給定2個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。

68最長公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk}，則(1)若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列。(2)若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長公共子序列。(3)若xm≠yn且zk≠yn，則Z是X和Yn-1的最長公共子序列。證明:P57由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。69子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時C[i][j]=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：70Xi最后一個元素不是Yj最后一個元素不是Algorithm

lcsLength(x,y,b){1:mx.length-1;2:ny.length-1;3:c[i][0]=0;c[0][i]=0;4:for(inti=1;i<=m;i++)5:for(intj=1;j<=n;j++){6:if(x[i]==y[j]){7:c[i][j]=c[i-1][j-1]+1;8:b[i][j]=1;}9:elseif(c[i-1][j]>=c[i][j-1]){10:c[i][j]=c[i-1][j];11:b[i][j]=2;}12:else{13:c[i][j]=c[i][j-1];14:b[i][j]=3;}15:}16:returnc[m][n];17:}71初始化最后元素相同的情況不含xi結(jié)果更優(yōu)不含yj結(jié)果更優(yōu)72最大子段和:問題描述給定整數(shù)序列a1,a2,…,an，求形如的子段和的最大值。規(guī)定子段和為負(fù)整數(shù)時，定義其最大子段和為0，即例如，(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)

最大子段和為73最大子段和:動態(tài)規(guī)劃算法基本思想－子問題定義考慮所有下標(biāo)以j結(jié)束的最大子段和b[j]，即－原問題與子問題的關(guān)系

－子問題解的遞歸關(guān)系74最大子段和:動態(tài)規(guī)劃算法（續(xù)）算法intMaxSubSum3(intn,inta[]){intsum=0,b=0;//sum存儲當(dāng)前最大的b[j],b存儲b[j]for(intj=1;j<=n;j++){b+=a[j];if(b<0)b=0;//一旦某個區(qū)段和為負(fù)，則從下一個位置累和

if(b>sum)sum=b;}returnsum;}運(yùn)行時間：T(n)=O(n)75最優(yōu)二叉搜索樹什么是二叉搜索樹？（1）若它的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；（2）若它的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；（3它的左、右子樹也分別為二叉排序樹45125333724100619078在隨機(jī)的情況下，二叉查找樹的平均查找長度和是等數(shù)量級的7677最優(yōu)二叉搜索樹存在的兩個問題1在實際中也會遇到不成功檢索的情況。2在實際中，不同標(biāo)識符會有不同的檢索概率。對給定的標(biāo)識符集合，希望給出構(gòu)造二分搜索樹的方法，使得所構(gòu)造的二分搜索樹具有最優(yōu)的性能。可能遇到不成功檢索的情況擴(kuò)充二叉樹：當(dāng)二叉樹里出現(xiàn)空的子樹時，就增加新的、特殊的結(jié)點——空樹葉。對于原來二叉樹里度數(shù)為1的分支結(jié)點，在它下面增加一個空樹葉；對于原來二叉樹的樹葉，在它下面增加兩個空樹葉。擴(kuò)充二叉樹是滿二叉樹，新增加的空樹葉（以下稱外部結(jié)點）的個數(shù)等于原來二叉樹的結(jié)點（以下稱內(nèi)部結(jié)點）個數(shù)加1。7879xalwanwilwenwimwulzolyozomxulyumxemyonziAA代表其值處于wim和wul之間的可能關(guān)鍵碼集合在二叉搜索樹中搜索一個元素x設(shè)S={x1,x2,···,xn}是一個有序集合，且x1,x2,···,xn表示有序集合的二叉搜索樹。利用二叉樹的頂點存儲有序集中的元素，而且具有性質(zhì)：存儲于每個頂點中的元素x

大于其左子樹中任一個頂點中存儲的元素，小于其右子樹中任意頂點中存儲的元素。二叉樹中的葉頂點是形如(xi,xi+1)

的開區(qū)間。80(1)在二叉樹的內(nèi)部頂點處找到：x=xi(2)在二叉樹的葉頂點中確定：x∈(xi,xi+1){1,2,3}可能的二分檢索樹81(a)321

231

(c)312(d)

(b)312

321

(e)82在檢索過程中，每進(jìn)行一次比較，就進(jìn)入下面一層（層數(shù)初始為0），對于成功的檢索，比較的次數(shù)就是所在的層數(shù)加1。對于不成功的檢索，被檢索的關(guān)鍵碼屬于那個外部結(jié)點代表的可能關(guān)鍵碼集合，比較次數(shù)就等于此外部結(jié)點的層數(shù)。不同標(biāo)識符有不同的檢索概率設(shè)pi是對xi檢索的概率。設(shè)qi是對滿足xi<x<xi+1,0in的標(biāo)識符x檢索的概率，(假定a0=-且an+1=＋)。83a1q(0)E0p(1)a2E1q(1)p(2)aip(i)ai+1Eiq(i)p(i+1)anp(n)Enq(n)二叉查找樹的期望耗費查找成功與不成功的概率二叉查找樹的期望耗費有個節(jié)點的二叉樹的個數(shù)為：窮舉搜索法的時間復(fù)雜度為指數(shù)級84二叉查找樹的期望耗費示例85最優(yōu)子結(jié)構(gòu)性質(zhì)假設(shè)選擇ak為樹根，則a0,a1,…,ak-1

都將位于左子樹L上，其余結(jié)點ak+1,…,an位于右子樹R上。86k

L

Ra0,a1,…,ak-1ak+1,…,an87511472063353976425431399848851147206335397642543139984設(shè)COST(L)

和COST(R)

分別是二分檢索樹T的左子樹和右子樹的成本。則檢索樹T的成本是：

P(k)+COST(L)+COST(R)+……若T

是最優(yōu)的，則上式及COST(L)和COST(R)必定都取最小值。89最優(yōu)子結(jié)構(gòu)性質(zhì)90二叉搜索樹T的一棵含有頂點xi,···,xj和葉頂點

(xi-1,xi),···,(xj,xj+1)的子樹可以看作是有序集{xi,···,xj}關(guān)于全集為{xi-1,xj＋1

}的一棵二叉搜索樹（T自身可以看作是有序集)。根據(jù)S

的存取分布概率，在該子樹中被搜索或確定區(qū)間的概率是：91左子樹的搜索概率右子樹的搜索概率設(shè)Tij是有序集{xi

,···,xj}關(guān)于存儲概率分布為{ai-1,bi,

…,bj,aj}的一棵最優(yōu)二叉搜索樹，其平均路長為pij，Tij的根頂點存儲的元素xm，其左子樹Tl和右子樹Tr的平均路長分別為pl和pr。由于Tl和Tr中頂點深度是它們在Tij中的深度減1，所以得到{xi

,···,xj}的存儲概率分布為{ai-1,bi,

…,bj,aj}，其中，ah，bk分別是下面的條件概率：92構(gòu)造最優(yōu)二叉搜索樹時，可以選擇先構(gòu)造其左右子樹，使其左右子樹最優(yōu)，然后構(gòu)造整棵樹。93遞歸計算最優(yōu)值最優(yōu)二叉搜索樹Tij的平均路長為pij，則所求的最優(yōu)值為p1,n。由二叉樹的花費公式根據(jù)最優(yōu)二叉搜索樹問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可建立計算pij的遞歸式如下初始時最優(yōu)二叉搜索樹94記wi,jpi,j為m(i,j)，則m(1,n)=w1,np1,n=p1,n為所求的最優(yōu)值。計算m(i,j)的遞歸式為根據(jù)該公式，計算樹T[i][j]的花費只用到了T[i][k-1]，T[k+1][j],可得到具體求解過程如下：1）構(gòu)造只有1個內(nèi)部結(jié)點的最優(yōu)二叉搜索樹T[1][1],T[2][2]…,T[n][n]，可以求得m[i][i]同時可以用一個數(shù)組存做根結(jié)點元素為：

s[1][1]=1,s[2][2]=2…s[n][n]=n2)構(gòu)造具有2個內(nèi)部結(jié)點的最優(yōu)二叉搜索樹9596例給出標(biāo)識符集{1,2,3}＝{do,if,stop}存取概率若P1=0.5,P2=0.1,P3=0.05,q0=0.15,q1=0.1,q2=0.05,q3=0.05構(gòu)造一棵最優(yōu)二叉搜索樹97q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.051q0q1T[1][1]w[1][1]=0.75m[1][1]=0.752q1q2T[2][2]w[2][2]=0.25m[2][2]=0.253q2q3T[3][3]w[3][3]=0.15m[3][3]=0.1512q0q1q212q0q1q2T[1][2]w[1][2]=0.9m[1][2]=0.9+m[1][1]+m[3][2]=1.65w[1][2]=0.9m[1][2]=0.9+m[1][0]+m[2][2]=1.15q0=0.15,P1=0.5,q1=0.1,P2=0.1,q2=0.05,P3=0.05,q3=0.051q0q1T[1][1]w[1][1]=0.75m[1][1]=0.752q1q2T[2][2]w[2][2]=0.25m[2][2]=0.253q2q3T[3][3]w[3][3]=0.15m[3][3]=0.1512q0q1q212q0q1q2T[1][2]w[1][2]=0.9m[1][2]=0.9+m[1][1]+m[3][2]=1.65w[1][2]=0.9m[1][2]=0