計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第6章 動(dòng)態(tài)規(guī)劃

1第6

章

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

2矩陣連乘問(wèn)題

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

18最佳二元搜索樹(shù)問(wèn)題

24多級(jí)圖及其應(yīng)用

35最長(zhǎng)遞增子序列問(wèn)題

41類(lèi)似分治法，把大問(wèn)題分為較小的子問(wèn)題來(lái)解決，但方法不同。分治法一開(kāi)始就決定如何分解，每層都遵循一樣的分解規(guī)則。分解到底后，把底解出，然后再逐層向上合并，稱(chēng)為由頂向下的方法。有些問(wèn)題在不同規(guī)?；虿煌斎霐?shù)據(jù)時(shí)，最佳的劃分會(huì)不同。這時(shí)，分治法無(wú)法給出最佳結(jié)果或復(fù)雜度會(huì)很高。動(dòng)態(tài)規(guī)劃考慮原問(wèn)題的所有可能的分解，并保證所有子問(wèn)題的最佳解都已在前面步驟中獲得。我們只需比較一下哪種分解最好即可。要獲得子問(wèn)題的最佳解又需要把它分解為更小的子問(wèn)題，這樣下去直到最底層。所以，動(dòng)態(tài)規(guī)劃的第一步是把所有規(guī)模最小的子問(wèn)題解決掉，然后解決稍大些它們的父問(wèn)題，接著解決更大些的父問(wèn)題，直到解決原問(wèn)題。所以，動(dòng)態(tài)規(guī)劃是一個(gè)由底向上的方法，它要求所有子問(wèn)題和原問(wèn)題必須獲得最佳解。21.基本原理3動(dòng)態(tài)規(guī)劃的步驟：初始化 定義最小規(guī)模的子問(wèn)題的集合

S0(初始集合)

和初始解集合。2 從下向上歸納在S0的基礎(chǔ)上，歸納定義一系列子問(wèn)題的集合，S1，S2，…，Sk。集合Si+1中子問(wèn)題是Sj

(0

j

i)中子問(wèn)題的父問(wèn)題，進(jìn)行到當(dāng)集合Sk包含規(guī)模為n的原問(wèn)題時(shí)為止。一個(gè)子問(wèn)題或原問(wèn)題的解有一個(gè)目標(biāo)值，一個(gè)優(yōu)化問(wèn)題追求的解是使目標(biāo)值達(dá)到最大，或最小，稱(chēng)為最佳。找出父問(wèn)題的最佳目標(biāo)值和子問(wèn)題的最佳目標(biāo)值之間的關(guān)系，稱(chēng)為歸納公式。設(shè)計(jì)基於歸納公式的算法，用于逐層構(gòu)造所有子問(wèn)題的解，并計(jì)算它們的最佳目標(biāo)值。42.矩陣連乘問(wèn)題

5讓我們考察一下不同順序的情況。(1) (((AB)C)D)乘法次數(shù)=25

2

40+25

40

15+25

15

30=2000+15000+11250=28,250。

ABCD維數(shù)25

22

4040

1515

306(A(B(CD)))乘法次數(shù)=40

15

30+2

40

30+25

2

30=18000+2400+1500=21,900。7(3) ((AB)(CD))乘法次數(shù)=25

2

40+40

15

30+25

40

30

=2000+18000+30000=50,000。8((A(BC))D)乘法次數(shù)=2

40

15+25

2

15+25

15

30

=1200+750+11250=13,200。9(A((BC)D))乘法次數(shù)=2

40

15+2

15

30+25

2

30=1200+900+1500=3,600。這個(gè)順序(5)最好！當(dāng)n較大時(shí)，有太多的順序，窮舉法不可取。10動(dòng)態(tài)規(guī)劃的方法假設(shè)n個(gè)矩陣A1,A2,A3,…,An

的維數(shù)分別是：p0

p1，p1

p2，…，pn-1

pn。即維數(shù)序列是：p0，p1，…，pn-1，pn。初始化初始集合S1=

{Ai

|1

i

n}={A1，A2，A3，…，An}定義子問(wèn)題任何子序列，Ai

Ai+1

Ai+2…Aj

(1

i

j

n)的連乗問(wèn)題都是我們要考慮的子問(wèn)題。長(zhǎng)度l=j-i+1是這個(gè)子問(wèn)題的規(guī)模。我們可定義：Sl

={Ai

Ai+1

Ai+2…Aj

|1

i

j

n,j-i+1=l}，l=1,2,…,n。Sn

的子問(wèn)題就是原問(wèn)題A1A2A3…An。11

12例6.2

用動(dòng)態(tài)規(guī)劃解例6.1中矩陣連乘問(wèn)題

A(=A1)B(=A2)C(=A3)D(=A4)維數(shù)25

22

4040

1515

30計(jì)算表M

和K。中間是M(i,j)，左上角是A[i,j]，右下角是它的維數(shù)。131415矩陣連乗的偽碼見(jiàn)下頁(yè)。16Matrix-Chain-Order(P[0..n]) //輸入是n個(gè)矩陣的維數(shù)序列for

i

1to

n，M(i,i)

0，endfor //初始解集合

for

l

2to

n

//l是子問(wèn)題的規(guī)模

for

i

1to

n–(l-1)

j

i+l-1，M(i,j)

for

k

i

to

j-1

q

M(i,k)

+M(k+1,j)

+P[i-1]

P[k]

P[j]

if

q<M(i,j)

then

M(i,j)

q，K(i,j)

k

endif

endfor

endforendforreturn

MandKEnd 復(fù)雜度是O(n3)17由表K(i,j)

構(gòu)造的連乗順序(二叉樹(shù))183.最長(zhǎng)公共子序列問(wèn)題問(wèn)題定義給定字符序列

X和Y，另有序列Z，如果Z既是X的子序列也是Y的子序列，那么，Z是X和Y的公共子序列。最長(zhǎng)公共子序列問(wèn)題就是找出一個(gè)X和Y的最長(zhǎng)的公共子序列

(LongestCommonSubsequence)，簡(jiǎn)稱(chēng)LCS。19設(shè)

X

=<a1,a2,…,am

> Y

=<b1,b2,…,bn

>定義子問(wèn)題

定義X和Y的所有前綴如下： X0

=

Xi

=<a1,a2,…,ai

>,i=1,2,…,m， Y0

=

Yj=<b1,b2,…,bj

>,j=1,2,…,n。子問(wèn)題是：求每個(gè)

Xi

和每個(gè)Yj之間的LCS，記LCS(Xi,Yj)。它的長(zhǎng)度定義為：

C(i,j)

=Xi

和Yj之間的LCS的長(zhǎng)度。20歸納公式：初始解

C(0,j)

=C(i,0)=0

(0≤i≤m,0≤j≤n)(2)歸納公式(6.4式) C(i,j)

=C(i-1,j-1)+1

如果ai=bj C(i,j)

=max{C(i-1,j),C(i,j-1)}

如果ai

bj解釋?zhuān)寒?dāng)ai=bj時(shí)，把a(bǔ)i

和bj配上，再加上Xi-1

和Yj-1

之間的LCS。當(dāng)ai≠bj時(shí)，ai

和bj不能同時(shí)被選入LCS中。如不選ai，那么LCS就是Xi-1

和Yj

的LCS，長(zhǎng)度為C(i-1,j)如不選bj，那么LCS就是Xi

和Yj-1的LCS，長(zhǎng)度為C(i,j-1)。21算法簡(jiǎn)介初始化C(0,j)

=C(i,0)=0后，一行一行計(jì)算C(i,j)先算出所有C(1,j)

(1≤j≤n)的值，再算出所有C(2,j)

(1≤j≤n)的值，…，最后算出所有C(m,j)

(1≤j≤n)的值。在計(jì)算第i行時(shí)，按從左到右的順序，即先算出C(i,1)，再算出C(i,2)，…，等等，最后算出C(i,n)。為記錄C(i,j)和更小子問(wèn)題關(guān)系，用D(i,

j)

=“” 表示C(i,j)

=C(i-1,j-1)+1，用D(i,

j)

=“

”

表示C(i,j)=

C(i-1,j)，用D(i,

j)

=“

”

表示C(i,j)=

C(i,j-1)。偽碼見(jiàn)下頁(yè)22LCS-Length(X[1..m],Y[1..n],C,D)fori

0to

m，C(i,0)

0，

endfor

//LCS(Xi,Y0)的初始解forj

1to

n，

C(0,j)

0，

endfor //LCS(X0,Yj)的初始解fori

1to

m

forj

1to

n

if

X[i]

=Y[j]

then

C(i,j)

C(i-1,j-1)+1，D(i,j)

“

”

else ifC(i-1,j)

C(i,j-1)

then

C(i,j)

C(i-1,j)，D(i,j)

“

”

else

C(i,j)

C(i,j-1)，D(i,j)

“

”

endif

endif

endforendforreturn

CandDEnd23例(6.2)從D(m,n)開(kāi)始，順箭頭回溯到邊界。遇到D(i,

j)

=

時(shí)，說(shuō)明X[i]=Y[j]，則把該字符選出。這樣找到的字符序列就是解。該例解是BCBA。244.最佳二元搜索樹(shù)問(wèn)題定義6.1(二元搜索樹(shù))給定A[1]≤A[2]≤…≤A[n]，為方便，設(shè)A[0]=-

，

A[n+1]=

。它的一棵二元搜索樹(shù)是有n個(gè)內(nèi)結(jié)點(diǎn)的完全二叉樹(shù)，分別存放這n個(gè)數(shù)字，并滿足：任一內(nèi)結(jié)點(diǎn)y的左子樹(shù)中任一數(shù)字

y

y的右子樹(shù)中任一數(shù)字。葉結(jié)點(diǎn)代表搜索x失敗，di表示A[i-1]<x<A[i](1

i

n)。25

26動(dòng)態(tài)規(guī)劃算法定義子問(wèn)題：為子序列

A[i]≤A[i+1]≤…≤A[j]構(gòu)造最佳二元搜索樹(shù)T[i,j](1

i

j

n)，其E(T)值記為E(i,j)。另外，最小的子樹(shù)可以是一片葉子，所以初始集合{d0,d1,…,dn}也包含在子問(wèn)題中。di對(duì)應(yīng)的葉子可用T[i+1,i]表示。初始解集合初始集合{d0,d1,…,dn}對(duì)應(yīng)的初始解為E(i,i-1)=qi-1

(1

i

n+1)。對(duì)于初始集合及初始解的理解在下面的討論中會(huì)得到進(jìn)一步理解。歸納公式考慮如何把子序列

A[i]≤A[i+1]≤…≤A[j](i

j)分配給左子樹(shù)，根，和右子樹(shù)。(接下頁(yè))27

28歸納公式(繼續(xù)

2)如下圖所示，樹(shù)中A[t]到根A[k]的距離=A[t]到子樹(shù)根距離+1。葉結(jié)點(diǎn)dt到根A[k]的距離

=dt到子樹(shù)根距離+1。(接下頁(yè))29

30

31

32Optimal-BST(繼續(xù))

for

l

1to

n fori

1to

n-l+1

j

i+l–1 E(i,j)

W[i,j]

W[i,j-1]+pj

+qj

for

k

i

to

j

t

E(i,k-1)+E(k+1,j)

ift<E(i,j)

then

E(i,j)

t

root(i,j)

k

endif

E(i,j)

E(i,j)

+W[i,j]

endfor，endfor，endforreturn

EandrootEnd

算法的復(fù)雜度顯然是O(n3)。33例6.3

為如下權(quán)值序列構(gòu)造最佳二元搜索樹(shù)。i

012345pi

38265qi214312Wj=012345i

=126182330372

1131825323

4916234

310175

186

2Ej

=012345i=129314872962

1183557783

41633504

314315

1116

2root

j=12345i=1

122222

22343

3444

445

534例6.3(繼續(xù))E表中，E(1,5)=96說(shuō)明，完成所有搜索任務(wù)需要96次比較。由root表構(gòu)造的搜索樹(shù)如下。沒(méi)有更好的二元搜索樹(shù)了。i

012345pi

38265qi214312搜索任務(wù)包括有3次x=A[1]，8次x=A[2]，2次x=A[3]，6次x=A[4]，5次x=A[5]，2次-

<x<A[1]， 1次A[1]<x<A[2]， 4次A[2]<x<A[3]，3次A[3]<x<A[4]，1次A[4]<x<A[5]， 2次A[5]<x<

。35多級(jí)圖及其應(yīng)用sabfdcegt531825246647594例(圖6-9)V1

V2

V3

V4V5定義：一個(gè)k級(jí)圖的頂點(diǎn)可分為k個(gè)不相交的子集，V=V1

V2

…

Vk。每條邊只能指向下一個(gè)相鄰子集中某個(gè)頂點(diǎn)，即邊(u,v)必須滿足u

Vi,v

Vi+1(1≤i≤k-1)。通常V1

和Vk

分別只含一個(gè)頂點(diǎn)，記為

s和

t。36給定一個(gè)

k級(jí)圖，常見(jiàn)問(wèn)題是，找出從

s到

t的最長(zhǎng)(或最短)路徑。這都可在O(n+m)時(shí)間里完成，且允許權(quán)值可正可負(fù)。我們只討論如何用動(dòng)態(tài)規(guī)劃找出從

s到

t的最長(zhǎng)路徑，找最短路徑類(lèi)似。定義子問(wèn)題：我們?yōu)槊總€(gè)v

V，定義一個(gè)子問(wèn)題，就是找出從

s到

v的最長(zhǎng)路徑P(s,v)，其長(zhǎng)記為D(v)。Vi

(1

i

k)中所有頂點(diǎn)的子問(wèn)題組成集合

Si

={P(s,v)|v

Vi}。歸納公式：初始子問(wèn)題集合是S1={P(s,s)}，初始解是D(s)=0。歸納公式是，如果

v

Vi

(2

i

k)，則有：

D(v)=max{D(u)+w(u,v)|u

Vi-1}這是因?yàn)椋魏我粭l

s到

v的路徑必定經(jīng)過(guò)Vi-1中某點(diǎn)u。使D(v)最大的點(diǎn)u稱(chēng)為v的父親，記為

(v)=u。P(s,v)可以通過(guò)父親指針逐級(jí)找到。37找最長(zhǎng)路徑偽碼Longest-path(G(V,E)，k) //G(V,E)是個(gè)k級(jí)圖foreach

vertexv

V

//為每個(gè)v，初始化D(v)

=

D(v)

，

(v)

nilendforD(s)

0 //初始解fori

1to

k-1 foreachvertex

u

Vi foreachedge

(u,v)

E

//頂點(diǎn)u的每一個(gè)鄰居v if

D(u)

+w(u,v)>D(v)

then

D(v)

D(u)

+w(u,v)

(v)

u

endif

endfor

endfor，endforEnd38

56S142S297S357S439S51110S639除s和t以外，每級(jí)Vi有兩個(gè)頂點(diǎn)，分別表示Si的兩個(gè)狀態(tài)。從Vi的每個(gè)頂點(diǎn)到Vi+1的每個(gè)頂點(diǎn)之間有一條有向邊，其權(quán)值為Si和Si+1在對(duì)應(yīng)狀態(tài)下R[i]

L[i+1]的值?？梢?jiàn)，一條從s到t的路徑對(duì)應(yīng)一個(gè)骨牌的狀態(tài)順序，反之亦然。其路徑長(zhǎng)度就是對(duì)應(yīng)的T(n)值。最長(zhǎng)路徑對(duì)應(yīng)最佳解。例

6.4

(繼續(xù)1)56S142S297S357S439S51110S6構(gòu)造如下多級(jí)圖(6-10)40如上圖，我們逐級(jí)逐點(diǎn)算出D(v)和

(v)。例如，點(diǎn)

v=[7,9]旁邊標(biāo)注(40,0)，表示D(v)=40，它的父親是前一級(jí)中狀態(tài)為0的那個(gè)點(diǎn)，即

(v)=[5,6]，也就是S2

狀態(tài)是W(2)=0。最佳解是T(n)=217。由父親指針(圖中紅色箭頭)可得最長(zhǎng)路徑。所以最佳狀態(tài)序列是：W[1]=0，W[2]=0，W[3]=0。W[4]=1，W[5]=0，W[6]=1。例6.4(繼續(xù)2)s562479573910116542977593111000001220102428183614454963352145156399309033t0012,040,085,0103,0118,1208,0217,0217,1148,148,024,0416.

最長(zhǎng)遞增子序列問(wèn)題定義：在序列A[1]，A[2]，…，A[n]中找出最長(zhǎng)的一個(gè)遞增(不減)的子序列稱(chēng)為最長(zhǎng)遞增子序列問(wèn)題。例：

給定序列

3，5，9，5，12，8，11

子序列

3，5，5，8，11

是一個(gè)遞增的子序列且最長(zhǎng)。一個(gè)簡(jiǎn)單的O(n2)算法：Simple-Longest-Increasing-Subsequence(A[1..n],l)1 fori=1to

n

2

B[i]

A[i]3 endfor4 StablesortarrayBsuchthatB[1]≤B[2]≤…≤B[n] //穩(wěn)定排序5 LCS(A[1..n],B[1..n],C,D,l) //A和B的最長(zhǎng)公共子序列End42簡(jiǎn)單算法有局限性，不便用在其他類(lèi)似問(wèn)題上，且難以改進(jìn)時(shí)間復(fù)雜度。動(dòng)態(tài)規(guī)劃法如下。定義子問(wèn)題：為每一個(gè)子序列A[1]，A[2]，…，A[i](1

i

n)，定義一個(gè)子問(wèn)題如下：找出以A[i]結(jié)束的最長(zhǎng)的一個(gè)遞增的子序列，記作LIS[i]，其長(zhǎng)度記作L(i)。

最長(zhǎng)的LIS(i)就是原問(wèn)題解。初始集合和初始解：初始集合S0={A[1]}，初始解是L(1)

=1。歸納公式：L(i)

=1+max{L(k)

|A[k]

A[i]并且1≤k<i}。

(i)

=k表示A[i]應(yīng)該接在以A[k]結(jié)束的遞增子序列后面。如果沒(méi)有k使

A[k]

A[i]，那么L(i)

=1，

(i)

=nil。43例(圖6-13)i1234567A[i]3594121011L(i)1232445

(i)nil121336例子的最長(zhǎng)遞增子序列是：3，5，9，10，11。偽碼如下：Longest-Increasing-Subsequence(A[1..n],L,B,length)L(1)