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

1第6

章

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

2矩陣連乘問題

4最長公共子序列問題

18最佳二元搜索樹問題

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

35最長遞增子序列問題

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

S0(初始集合)

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

(0

j

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

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。這個順序(5)最好！當n較大時，有太多的順序，窮舉法不可取。10動態(tài)規(guī)劃的方法假設(shè)n個矩陣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}定義子問題任何子序列，Ai

Ai+1

Ai+2…Aj

(1

i

j

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

={Ai

Ai+1

Ai+2…Aj

|1

i

j

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

的子問題就是原問題A1A2A3…An。11

12例6.2

用動態(tài)規(guī)劃解例6.1中矩陣連乘問題

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

22

4040

1515

30計算表M

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

i

1to

n，M(i,i)

0，endfor //初始解集合

for

l

2to

n

//l是子問題的規(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)造的連乗順序(二叉樹)183.最長公共子序列問題問題定義給定字符序列

X和Y，另有序列Z，如果Z既是X的子序列也是Y的子序列，那么，Z是X和Y的公共子序列。最長公共子序列問題就是找出一個X和Y的最長的公共子序列

(LongestCommonSubsequence)，簡稱LCS。19設(shè)

X

=<a1,a2,…,am

> Y

=<b1,b2,…,bn

>定義子問題

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

=

Xi

=<a1,a2,…,ai

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

=

Yj=<b1,b2,…,bj

>,j=1,2,…,n。子問題是：求每個

Xi

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

C(i,j)

=Xi

和Yj之間的LCS的長度。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解釋：當ai=bj時，把ai

和bj配上，再加上Xi-1

和Yj-1

之間的LCS。當ai≠bj時，ai

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

和Yj

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

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

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

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

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

(1≤j≤n)的值。在計算第i行時，按從左到右的順序，即先算出C(i,1)，再算出C(i,2)，…，等等，最后算出C(i,n)。為記錄C(i,j)和更小子問題關(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)。偽碼見下頁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)開始，順箭頭回溯到邊界。遇到D(i,

j)

=

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

，

A[n+1]=

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

y

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

i

n)。25

26動態(tài)規(guī)劃算法定義子問題：為子序列

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

i

j

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

(1

i

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

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

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

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

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

=dt到子樹根距離+1。(接下頁)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)造最佳二元搜索樹。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說明，完成所有搜索任務(wù)需要96次比較。由root表構(gòu)造的搜索樹如下。沒有更好的二元搜索樹了。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多級圖及其應(yīng)用sabfdcegt531825246647594例(圖6-9)V1

V2

V3

V4V5定義：一個k級圖的頂點可分為k個不相交的子集，V=V1

V2

…

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

Vi,v

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

和Vk

分別只含一個頂點，記為

s和

t。36給定一個

k級圖，常見問題是，找出從

s到

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

s到

t的最長路徑，找最短路徑類似。定義子問題：我們?yōu)槊總€v

V，定義一個子問題，就是找出從

s到

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

(1

i

k)中所有頂點的子問題組成集合

Si

={P(s,v)|v

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

v

Vi

(2

i

k)，則有：

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

Vi-1}這是因為，任何一條

s到

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

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

vertexv

V

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

=

D(v)

，

(v)

nilendforD(s)

0 //初始解fori

1to

k-1 foreachvertex

u

Vi foreachedge

(u,v)

E

//頂點u的每一個鄰居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以外，每級Vi有兩個頂點，分別表示Si的兩個狀態(tài)。從Vi的每個頂點到Vi+1的每個頂點之間有一條有向邊，其權(quán)值為Si和Si+1在對應(yīng)狀態(tài)下R[i]

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

6.4

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

(v)。例如，點

v=[7,9]旁邊標注(40,0)，表示D(v)=40，它的父親是前一級中狀態(tài)為0的那個點，即

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

狀態(tài)是W(2)=0。最佳解是T(n)=217。由父親指針(圖中紅色箭頭)可得最長路徑。所以最佳狀態(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.

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

給定序列

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

子序列

3，5，5，8，11

是一個遞增的子序列且最長。一個簡單的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的最長公共子序列End42簡單算法有局限性，不便用在其他類似問題上，且難以改進時間復(fù)雜度。動態(tài)規(guī)劃法如下。定義子問題：為每一個子序列A[1]，A[2]，…，A[i](1

i

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

最長的LIS(i)就是原問題解。初始集合和初始解：初始集合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é)束的遞增子序列后面。如果沒有k使

A[k]

A[i]，那么L(i)

=1，

(i)

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

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