算法設計與分析第四講動態規劃哈爾濱工業大學王宏志wangzh@/pages/wang/請各位評審老師提出寶貴建議！謝謝！本講內容

4.1動態規劃的原理 4.2矩陣乘法問題

4.3最長公共子序列問題

4.40-1背包問題2分治技術的問題子問題是相互獨立的如果子問題不是相互獨立的，分治方法將重復計算公共子問題，效率很低優化問題給定一組約束條件和一個代價函數，在解空間中搜索具有最小或最大代價的優化解很多優化問題可分為多個子問題，子問題相互關聯，子問題的解被重復使用Why?動態規劃的特點把原始問題劃分成一系列子問題求解每個子問題僅一次，并將其結果保存在一個表中，以后用到時直接存取，不重復計算，節省計算時間自底向上地計算適用范圍一類優化問題：可分為多個相關子問題，子問題的解被重復使用What?

使用動態規劃的條件優化子結構當一個問題的優化解包含了子問題的優化解時，我們說這個問題具有優化子結構。縮小子問題集合，只需那些優化問題中包含的子問題，降低實現復雜性優化子結構使得我們能自下而上地完成求解過程重疊子問題在問題的求解過程中，很多子問題的解將被多次使用How?動態規劃算法的設計步驟分析優化解的結構遞歸地定義最優解的代價自底向上地計算優化解的代價保存之，并獲取構造最優解的信息根據構造最優解的信息構造優化解

請各位評審老師提出寶貴建議！謝謝！本講內容

4.1動態規劃的原理

4.2矩陣乘法問題

4.3最長公共子序列問題4.40-1背包問題7輸入：<A1,A2,...,An>,

Ai是矩陣輸出：計算A1

A2

...

An的最小代價方法問題的定義矩陣乘法的代價/復雜性:乘法的次數若A是p

q矩陣，B是q

r矩陣，則A

B的代價是O(pqr)矩陣鏈乘法的實現矩陣乘法滿足結合率。計算一個矩陣鏈的乘法可有多種方法:

例如,（A1

A2

A3

A4）=（A1

(A2

(A3

A4)))=（(A1

A2)

(A3

A4）)

=(（A1

A2）

A3)

A4)動機矩陣鏈乘法的代價與計算順序的關系設A1=10

100矩陣,A2=100

5矩陣,A3=5

50矩陣T((A1

A2)

A3)=10

100

5+10

5

50=7500T(A1(A2

A3))=100

5

50+10

100

50=750000結論:不同計算順序有不同的代價p(n)=1ifn=1p(n)=ifn>1p(n)=C(n-1)=Catalan數==

(4n/n3/2)

矩陣鏈乘法優化問題的解空間設p(n)=計算n個矩陣乘積的方法數

p(n)的遞歸方程（A1

…Ak)(Ak+1…An)如此之大的解空間是無法用枚舉方法求出最優解的！

下邊開始設計求解矩陣鏈乘法問題的動態規劃算法分析優化解的結構遞歸地定義最優解的代價自底向上地計算優化解的代價保存之,并獲取構造最優解的信息根據構造最優解的信息構造優化解

兩個記號Ai-j=Ai

Ai+1

Ajcost(Ai-j)=計算Ai-j的代價優化解的結構若計算A1

n的優化順序在k處斷開矩陣鏈,即A1

n=A1

k

Ak+1

n，則在A1

n的優化順序中，對應于子問題A1

k的解必須是A1-k的優化解，對應于子問題Ak+1

n的解必須是Ak+1

n的優化解

分析優化解的結構具有優化子結構：問題的優化解包括子問題優化解子問題重疊性A1

A2

A3

A4(A1)

(A2

A3

A4)(A1

A2)

(A3

A4)(A1

A2

A3)

(A4)(A2

A3)(A3

A4)(A1

A2)(A3

A4)(A1

A2)(A2

A4)具有子問題重疊性(A3

A4)(A3

A4)(A1

A2)(A1

A2)假設m[i,j]=計算Aij的最小乘法數m[1,n]=計算A1n的最小乘法數A1...AkAk+1An是優化解(k實際上是不可預知)代價方程m[i,i]=

計算Ai

i

的最小乘法數=0m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj其中,pi-1pkpj是計算Ai

k

Ak+1

j所需乘法數,Ai

k和Ak+1j分別是pi-1

pk和pk

pj矩陣.遞歸地定義最優解的代價考慮到所有的k，優化解的代價方程為

m[i,j]=0ifi=jm[i,j]=mini

k<j{m[i,k]+m[k+1,j]+pi-1pkpj}

ifi<j

自底向上計算優化解的代價m[i,j]=mini

k<j{m[i,k]+m[k+1,j]+p0pkp5}m[1,5]m[1,1]m[4,4]m[5,5]m[2,2]m[3,3]m[4,5]m[3,4]m[2,3]m[1,2]m[1,3]m[2,4]m[3,5]m[1,4]m[2,5]m[2,4]=min{m[2,2]+m[3,4]m[2,3]+m[4,4]m[i,j]=mini

k<j{m[i,k]+m[k+1,j]+pi-1pkpj}m[1,5]m[1,1]m[4,4]m[5,5]m[2,2]m[3,3]m[4,5]m[3,4]m[2,3]m[1,2]m[1,3]m[2,4]m[3,5]m[1,4]m[2,5]Matrix-Chain-Order(p)n=length(p)-1；FORi=1TOnDO

m[i,i]=0;FORl=2TOnDO/*計算地l對角線*/FORi=1TOn-l+1DO

j=i+l-1;

m[i,j]=∞;

FORk

iToj-1DO/*計算m[i,j]*/

q=m[i,k]+m[k+1,j]+pi-1pkpjIFq<m[i,j]THENm[i,j]=q;Returnm.

Matrix-Chain-Order(p)n=length(p)-1；FORi=1TOnDO

m[i,i]=0;FORl=2TOnDOFORi=1TOn-l+1DO

j=i+l-1;

m[i,j]=∞;FORk

iToj-1DO

q=m[i,k]+m[k+1,j]+pi-1pkpjIFq<m[i,j]THENm[i,j]=q，s[i,j]=k;Returnmands.獲取構造最優解的信息S[i,j]記錄AiAi+1…Aj的最優劃分處在Ak與Ak+1之間

Print-Optimal-Parens(s,i,j)IFj=iTHENPrint“A”i;

ELSEPrint“(”Print-Optimal-Parens(s,i,s[i,j])Print-Optimal-Parens(s,s[i,j]+1,j)Print“)”

構造最優解調用Print-Optimal-Parens(s,1,n)即可輸出A1

n的優化計算順序S[i,j]記錄Ai…Aj的最優劃分處；S[i,S[i,j]]記錄Ai…As[i,j]的最優劃分處；S[S[i,j]+1,j]記錄As[i,j]+1…Aj的最優劃分處.?DKE-LAB(2009)時間復雜性計算代價的時間(l,i,k)三層循環,每層至多n-1步O(n3)構造最優解的時間:

O(n)總時間復雜性為：O(n3)空間復雜性

使用數組m和S需要空間O(n2)算法復雜性請各位評審老師提出寶貴建議！謝謝！本講內容

4.1動態規劃的原理 4.2矩陣乘法問題

4.3最長公共子序列問題4.40-1背包問題23子序列X=(A,B,C,B,D,B)Z=(B,C,D,B)是X的子序例W=(B,D,A)不是X的子序例公共子序列Z是序列X與Y的公共子序列如果Z是X的子序也是Y的子序列。問題的定義最長公共子序列（LCS）問題輸入：X=(x1,x2,...,xn)，Y=(y1,y2,...ym)輸出：Z=X與Y的最長公共子序列最長公共子序列結構分析第i前綴設X=(x1,x2,...,xn)是一個序列，X的第i前綴Xi是一個序列，定義為Xi=(x1,...,xi)

例.

X=(A,B,D,C,A),X1=(A),X2=(A,B),X3=(A,B,D)優化子結構定理1（優化子結構）設X=(x1,...,xm)、Y=(y1,...,yn)是兩個序列，Z=(z1,...,zk)是X與Y的LCS，我們有：

⑴

如果xm=yn,

則zk=xm=yn,

Zk-1是Xm-1和Yn-1的LCS，即，LCSXY=LCSXm-1Yn-1+<xm=yn>.

⑵

如果xm

yn，且zk

xm，則Z是Xm-1和Y的LCS，即LCSXY=LCSXm-1Y

⑶

如果xm

yn,且zk

yn,則Z是X與Yn-1的LCS，即LCSXY=LCSXYn-1?DKE-LAB(2009)證明:

⑴.X=<x1,…,xm-1,xm>,Y=<y1,…,yn-1,xm>，則LCSXY=LCSXm-1Yn-1+<xm=yn>.

設zk

xm，則可加xm=yn到Z，得到一個長為k+1的X與Y的公共序列，與Z是X和Y的LCS矛盾。于是zk=xm=yn。

現在證明Zk-1是Xm-1與Yn-1的LCS。顯然Zk-1是Xm-1與Yn-1的公共序列。我們需要證明Zk-1是LCS。設不然，則存在Xm-1與Yn-1的公共子序列W，W的長大于k-1。增加xm=yn到W，我們得到一個長大于k的X與Y的公共序列，與Z是LCS矛盾。于是，Zk-1是Xm-1與Yn-1的LCS.⑵X=<x1,…,xm-1,xm>,Y=<y1,…,yn-1,yn>，xm

yn，zk

xm，則

LCSXY=LCSXm-1Y

由于zk

xm，Z是Xm-1與Y的公共子序列。我們來證Z是Xm-1與Y的LCS。設Xm-1與Y有一個公共子序列W，W的長大于k,則W也是X與Y

的公共子序列，與Z是LCS矛盾。

⑶同⑵可證。X和Y的LCS的優化解結構為

LCSXY=LCSXm-1Yn-1+<xm=yn>ifxm=yn

LCSXY=LCSXm-1Y

ifxm

yn,zk

xm

LCSXY=LCSXYn-1

if

xm

yn,zk

yn子問題重疊性LCSXYLCSXm-1Yn-1LCSXm-1YLCSXYn-1LCSXm-2Yn-2LCSXm-2Yn-1LCSXm-1Yn-2……LCS問題具有子問題重疊性建立LCS長度的遞歸方程C[i,j]=Xi與Yj的LCS的長度LCS長度的遞歸方程

C[i,j]=0ifi=0或

j=0C[i,j]=C[i-1,j-1]+1ifi,j>0且xi=yjC[i,j]=Max(C[i,j-1],C[i-1,j])ifi,j>0且xi

yj

基本思想自底向上計算LCS的長度C[i-1,j-1]C[i-1,j]C[i,j-1]

C[i,j]計算過程C[0,0]C[0,1]C[0,3]C[0,2]C[0,4]C[1,0]C[2,0]C[3,0]C[1,1]C[2,1]C[3,1]C[1,2]C[1,3]C[1,4]C[2,2]C[2,3]C[2,4]C[3,2]C[3,3]C[3,4]計算LCS長度的算法數據結構

C[0:m,0:n]:C[i,j]是Xi與Yj的LCS的長度

B[1:m,1:n]:B[i,j]是指針，指向計算C[i,j]時所選擇的子問題的優化解所對應的C表的表項?DKE-LAB(2009)

LCS-length(X,Y)

m

length(X)；n

length(Y)；Fori

1TomDoC[i,0]

0;Forj

1TonDoC[0,j]

0;Fori

1TomDoForj

1TonDoIfxi=yj

ThenC[i,j]

C[i-1,j-1]+1；B[i,j]

“↖”;ElseIfC[i-1,j]

C[i,j-1]ThenC[i,j]

C[i-1,j];B[i,j]

“↑”;ElseC[i,j]

C[i,j-1];B[i,j]

“←”;ReturnCandB.

基本思想從B[m,n]開始按指針搜索若B[i,j]=“↖”，則xi=yj是LCS的一個元素如此找到的“LCS”是X與Y的LCS構造優化解Print-LCS(B,X,i,j)IFi=0orj=0THENReturn;IFB[i,j]=“↖”THENPrint-LCS(B,X,i-1,j-1);Printxi;ELSEIfB[i,j]=“↑”THENPrint-LCS(B,X,i-1,j);ELSEPrint-LCS(B,X,i,j-1).Print-LCS(B,X,length(X),length(Y))可打印出X與Y的LCS。

時間復雜性計算代價的時間(i,j)兩層循環,i循環m步,j循環n步O(mn)構造最優解的時間:

O(m+n)總時間復雜性為：O(mn)空降復雜性

使用數組C和B需要空間O(mn)算法復雜性請各位評審老師提出寶貴建議！謝謝！本講內容

4.1動態規劃的原理 4.2矩陣乘法問題

4.3最長公共子序列問題4.40-1背包問題40問題的定義

給定n種物品和一個背包，物品i的重量是wi，價值vi,背包容量為C,問如何選擇裝入背包的物品，使裝入背包中的物品的總價值最大？對于每種物品只能選擇完全裝入或不裝入，一個物品至多裝入一次。輸入：C>0,wi>0,vi>0,1

i

n

輸出：(x1,x2,…,xn),xi

{0,1},滿足

1

i

nwixi

C,

1

i

nvixi

最大等價的整數規劃問題max

1invixi

1inwixiCxi{0,1},1i

n?DKE-LAB(2009)優化解結構的分析定理(優化子結構)

如果(y1,y2,…,yn)是0-1背包問題的優化解，則(y2,…,yn)是如下子問題的優化解：max

2invixi

2inwixiC–w1y1xi{0,1},2i

n證明：如果(y2,…,yn)不是子問題優化解,則存在(z2,…,zn)是子問題更優的解。于是,(y1,z2,…,zn)是原問題比(y1,y2,…,yn)更優解，矛盾。建立優化解代價的遞歸方程設子問題max

iknvkxk

iknwkxkjxk{0,1},ik

n

的最優解代價為m(i,j).即m(i,j)是背包容量為j,可選物品為i,i+1,…,n

時問題最優解的代價.遞歸方程

m(i,j)=m(i+1,j)0j<wim(i,j)=max{m(i+1,j),m(i+1,j-wi)+vi}jwi