算法設(shè)計(jì)與分析 ch4 學(xué)習(xí)課件

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

4.1動(dòng)態(tài)規(guī)劃的原理 4.2矩陣乘法問(wèn)題

4.3最長(zhǎng)公共子序列問(wèn)題

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

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

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

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

4.2矩陣乘法問(wèn)題

4.3最長(zhǎng)公共子序列問(wèn)題4.40-1背包問(wèn)題7輸入：<A1,A2,...,An>,

Ai是矩陣輸出：計(jì)算A1

A2

...

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

q矩陣，B是q

r矩陣，則A

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

例如,（A1

A2

A3

A4）=（A1

(A2

(A3

A4)))=（(A1

A2)

(A3

A4）)

=(（A1

A2）

A3)

A4)動(dòng)機(jī)矩陣鏈乘法的代價(jià)與計(jì)算順序的關(guān)系設(shè)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é)論:不同計(jì)算順序有不同的代價(jià)p(n)=1ifn=1p(n)=ifn>1p(n)=C(n-1)=Catalan數(shù)==

(4n/n3/2)

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

p(n)的遞歸方程（A1

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

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

兩個(gè)記號(hào)Ai-j=Ai

Ai+1

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

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

n=A1

k

Ak+1

n，則在A1

n的優(yōu)化順序中，對(duì)應(yīng)于子問(wèn)題A1

k的解必須是A1-k的優(yōu)化解，對(duì)應(yīng)于子問(wèn)題Ak+1

n的解必須是Ak+1

n的優(yōu)化解

分析優(yōu)化解的結(jié)構(gòu)具有優(yōu)化子結(jié)構(gòu)：?jiǎn)栴}的優(yōu)化解包括子問(wèn)題優(yōu)化解子問(wè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)具有子問(wèn)題重疊性(A3

A4)(A3

A4)(A1

A2)(A1

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

計(jì)算Ai

i

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

k

Ak+1

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

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

pk和pk

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

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

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

ifi<j

自底向上計(jì)算優(yōu)化解的代價(jià)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/*計(jì)算地l對(duì)角線(xiàn)*/FORi=1TOn-l+1DO

j=i+l-1;

m[i,j]=∞;

FORk

iToj-1DO/*計(jì)算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“(”P(pán)rint-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)化計(jì)算順序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)時(shí)間復(fù)雜性計(jì)算代價(jià)的時(shí)間(l,i,k)三層循環(huán),每層至多n-1步O(n3)構(gòu)造最優(yōu)解的時(shí)間:

O(n)總時(shí)間復(fù)雜性為：O(n3)空間復(fù)雜性

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

4.1動(dòng)態(tài)規(guī)劃的原理 4.2矩陣乘法問(wèn)題

4.3最長(zhǎng)公共子序列問(wèn)題4.40-1背包問(wèn)題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的子序列。問(wèn)題的定義最長(zhǎng)公共子序列（LCS）問(wèn)題輸入：X=(x1,x2,...,xn)，Y=(y1,y2,...ym)輸出：Z=X與Y的最長(zhǎng)公共子序列最長(zhǎng)公共子序列結(jié)構(gòu)分析第i前綴設(shè)X=(x1,x2,...,xn)是一個(gè)序列，X的第i前綴Xi是一個(gè)序列，定義為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)）設(shè)X=(x1,...,xm)、Y=(y1,...,yn)是兩個(gè)序列，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>.

設(shè)zk

xm，則可加xm=yn到Z，得到一個(gè)長(zhǎng)為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。設(shè)不然，則存在Xm-1與Yn-1的公共子序列W，W的長(zhǎng)大于k-1。增加xm=yn到W，我們得到一個(gè)長(zhǎng)大于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的公共子序列。我們來(lái)證Z是Xm-1與Y的LCS。設(shè)Xm-1與Y有一個(gè)公共子序列W，W的長(zhǎng)大于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子問(wèn)題重疊性L(fǎng)CSXYLCSXm-1Yn-1LCSXm-1YLCSXYn-1LCSXm-2Yn-2LCSXm-2Yn-1LCSXm-1Yn-2……LCS問(wèn)題具有子問(wèn)題重疊性建立LCS長(zhǎng)度的遞歸方程C[i,j]=Xi與Yj的LCS的長(zhǎng)度LCS長(zhǎng)度的遞歸方程

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

基本思想自底向上計(jì)算LCS的長(zhǎng)度C[i-1,j-1]C[i-1,j]C[i,j-1]

C[i,j]計(jì)算過(guò)程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]計(jì)算LCS長(zhǎng)度的算法數(shù)據(jù)結(jié)構(gòu)

C[0:m,0:n]:C[i,j]是Xi與Yj的LCS的長(zhǎng)度

B[1:m,1:n]:B[i,j]是指針，指向計(jì)算C[i,j]時(shí)所選擇的子問(wèn)題的優(yōu)化解所對(duì)應(yīng)的C表的表項(xiàng)?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]開(kāi)始按指針?biāo)阉魅鬊[i,j]=“↖”，則xi=yj是LCS的一個(gè)元素如此找到的“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。

時(shí)間復(fù)雜性計(jì)算代價(jià)的時(shí)間(i,j)兩層循環(huán),i循環(huán)m步,j循環(huán)n步O(mn)構(gòu)造最優(yōu)解的時(shí)間:

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

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

4.1動(dòng)態(tài)規(guī)劃的原理 4.2矩陣乘法問(wèn)題

4.3最長(zhǎng)公共子序列問(wèn)題4.40-1背包問(wèn)題40問(wèn)題的定義

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

i

n

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

{0,1},滿(mǎn)足

1

i

nwixi

C,

1

i

nvixi

最大等價(jià)的整數(shù)規(guī)劃問(wèn)題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背包問(wèn)題的優(yōu)化解，則(y2,…,yn)是如下子問(wèn)題的優(yōu)化解：max

2invixi

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

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

iknvkxk

iknwkxkjxk{0,1},ik

n

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

時(shí)問(wèn)題最優(yōu)解的代價(jià).遞歸方程

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