算法設計與分析 ch4 學習課件

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

4.1動態(tài)規(guī)劃的原理 4.2矩陣乘法問題

4.3最長公共子序列問題

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

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

請各位評審老師提出寶貴建議！謝謝！本講內(nèi)容

4.1動態(tài)規(guī)劃的原理

4.2矩陣乘法問題

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

Ai是矩陣輸出：計算A1

A2

...

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

q矩陣，B是q

r矩陣，則A

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

例如,（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結(jié)論:不同計算順序有不同的代價p(n)=1ifn=1p(n)=ifn>1p(n)=C(n-1)=Catalan數(shù)==

(4n/n3/2)

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

p(n)的遞歸方程（A1

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

下邊開始設計求解矩陣鏈乘法問題的動態(tài)規(guī)劃算法分析優(yōu)化解的結(jié)構(gòu)遞歸地定義最優(yōu)解的代價自底向上地計算優(yōu)化解的代價保存之,并獲取構(gòu)造最優(yōu)解的信息根據(jù)構(gòu)造最優(yōu)解的信息構(gòu)造優(yōu)化解

兩個記號Ai-j=Ai

Ai+1

Ajcost(Ai-j)=計算Ai-j的代價優(yōu)化解的結(jié)構(gòu)若計算A1

n的優(yōu)化順序在k處斷開矩陣鏈,即A1

n=A1

k

Ak+1

n，則在A1

n的優(yōu)化順序中，對應于子問題A1

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

n的解必須是Ak+1

n的優(yōu)化解

分析優(yōu)化解的結(jié)構(gòu)具有優(yōu)化子結(jié)構(gòu)：問題的優(yōu)化解包括子問題優(yōu)化解子問題重疊性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的最小乘法數(shù)m[1,n]=計算A1n的最小乘法數(shù)A1...AkAk+1An是優(yōu)化解(k實際上是不可預知)代價方程m[i,i]=

計算Ai

i

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

k

Ak+1

j所需乘法數(shù),Ai

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

pk和pk

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

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

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

ifi<j

自底向上計算優(yōu)化解的代價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.獲取構(gòu)造最優(yōu)解的信息S[i,j]記錄AiAi+1…Aj的最優(yōu)劃分處在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“)”

構(gòu)造最優(yōu)解調(diào)用Print-Optimal-Parens(s,1,n)即可輸出A1

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

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

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

4.1動態(tài)規(guī)劃的原理 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的最長公共子序列最長公共子序列結(jié)構(gòu)分析第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)優(yōu)化子結(jié)構(gòu)定理1（優(yōu)化子結(jié)構(gòu)）設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。

現(xiàn)在證明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的優(yōu)化解結(jié)構(gòu)為

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長度的算法數(shù)據(jù)結(jié)構(gòu)

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

B[1:m,1:n]:B[i,j]是指針，指向計算C[i,j]時所選擇的子問題的優(yōu)化解所對應的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構(gòu)造優(yōu)化解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)兩層循環(huán),i循環(huán)m步,j循環(huán)n步O(mn)構(gòu)造最優(yōu)解的時間:

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

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

4.1動態(tài)規(guī)劃的原理 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

最大等價的整數(shù)規(guī)劃問題max

1invixi

1inwixiCxi{0,1},1i

n?DKE-LAB(2009)優(yōu)化解結(jié)構(gòu)的分析定理(優(yōu)化子結(jié)構(gòu))

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

2invixi

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

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

iknvkxk

iknwkxkjxk{0,1},ik

n

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

時問題最優(yōu)解的代價.遞歸方程

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