算法設(shè)計(jì)及分析動(dòng)態(tài)規(guī)劃基本思想

1、動(dòng)態(tài)規(guī)劃算法的基本思想動(dòng)態(tài)規(guī)劃方法是處理分段過(guò)程最優(yōu)化問(wèn)題的一類及其有效的方法。在實(shí)際生活中，有一類問(wèn)題的活動(dòng)過(guò)程可以分成若干個(gè)階段，而且在任一階段后的行為依賴于該階段的狀態(tài)，與該階段之前的過(guò)程是如何達(dá)到這種狀態(tài)的方式無(wú)關(guān)。這類 問(wèn)題的解決是多階段的決策過(guò)程。20世紀(jì)50年代，貝爾曼（Richard Bellman） 等人提出了解決這類問(wèn)題的“最優(yōu)化原則”，從而創(chuàng)建了最優(yōu)化問(wèn)題的一種新的 算法動(dòng)態(tài)規(guī)劃算法。最優(yōu)化原則指出，多階段過(guò)程的最優(yōu)決策序列應(yīng)當(dāng)具有性質(zhì)：無(wú)論過(guò)程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。這要求原問(wèn)題的最優(yōu)解包含了其子問(wèn)題的

2、一個(gè)最優(yōu)解（稱為最優(yōu)子結(jié)構(gòu)性質(zhì)）。動(dòng)態(tài)規(guī)劃算法采用最優(yōu)原則來(lái)建立遞歸關(guān)系式（關(guān)于求最優(yōu)值的），在求解問(wèn)題時(shí)有必要驗(yàn)證該遞歸關(guān)系式是否保持最優(yōu)原則。若不保持，則不可用動(dòng)態(tài)規(guī)劃算法。在得到最優(yōu)值的遞歸式之后，需要執(zhí)行回溯以構(gòu)造最優(yōu)解。在使用動(dòng)態(tài) 規(guī)劃算法自頂向下（Top-Down求解時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有 些子問(wèn)題反復(fù)計(jì)算多次，動(dòng)態(tài)規(guī)劃算法正是利用了這種 子問(wèn)題重疊性質(zhì)。對(duì)每一 個(gè)問(wèn)題只計(jì)算一次，而后將其解保存在一個(gè)表格中，當(dāng)再次要解此子問(wèn)題時(shí)，只 是簡(jiǎn)單地調(diào)用（用常數(shù)時(shí)間）一下已有的結(jié)果。通常，不同的子問(wèn)題個(gè)數(shù)隨著輸 入問(wèn)題的規(guī)模呈多項(xiàng)式增長(zhǎng)，因此，動(dòng)態(tài)規(guī)劃算法通常只需要多項(xiàng)式時(shí)

3、間， 從而 獲得較高的解題效率。最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì) 是采用動(dòng)態(tài)規(guī)劃算法的 兩個(gè)基本要素。例1.多段圖問(wèn)題V1V3V566422sL745856的最小成本路徑（也叫最短路徑）。8求由S到t711V44993V2725設(shè)G=（V,E）是一個(gè)賦權(quán)有向圖，其頂點(diǎn)集V被劃分成k2個(gè)不相交的子集V: 10蘭k，其中，V1和Vk分別只有一個(gè)頂點(diǎn)s（稱為源）和一個(gè)頂點(diǎn)t（稱為匯），下圖 中所有的邊（u,v）的始點(diǎn)和終點(diǎn)都在相鄰的兩個(gè)子集 V和V +1 中: u迂V，vV +1。多階段圖問(wèn)題：對(duì)于每一條由S到t的路徑，可以把它看成在k-2個(gè)階段作出的某個(gè)決策序列的相應(yīng)結(jié)果：第i步?jīng)Q策就是確定V+1中

4、哪個(gè)頂點(diǎn)在這條路徑上。今假設(shè)s, V2, V3,，V k-1, t是一條由s到t的最短路徑，再假定從源點(diǎn)s(初始狀態(tài))開始， 已經(jīng)作出了到頂點(diǎn)V2的決策(初始決策)，則V2就是初始決策產(chǎn)生的狀態(tài)。若將 V2看成是原問(wèn)題的子問(wèn)題的初始狀態(tài)，這個(gè)子問(wèn)題就是找一條由V2到t的最短路 徑。事實(shí)上，路徑V2, V 3,，V k-1, t 定是V2到t的一條最短路徑。不然， 設(shè) V2, q 3, ，q k-1, t 是一條由 V2至y t的比 V2, V 3, ，v k-1, t 更短的路徑， 貝y S, V 2, q 3, ，q 空,t 是一條由 s至卩t的比 s, V ?, V ?, ，V 巴，t 更

5、短的 路徑。與前面的假設(shè)矛盾。這說(shuō)明多段圖問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。例2. 0/1背包問(wèn)題有n件物品，第i件重量和價(jià)值分別是W和Pi, i=1,2,n。要將這n件物品的某些件裝入容量為c的背包中，要求每件物品或整個(gè)裝入或不裝入，不 許分割出一部分裝入。0/1背包問(wèn)題就是要給出裝包方法，使得裝入背包的物品 的總價(jià)值最大。這個(gè)問(wèn)題歸結(jié)為數(shù)學(xué)規(guī)劃問(wèn)題：max 2 Pi Xi1s.t. Z：WiXicXi 0,1, i =1,2，n (6.1.1)10/1背包問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實(shí)上，若yi,y2,，yn是最優(yōu)解則 y2,yn將是0/1背包問(wèn)題的子問(wèn)題:s.t.(6.1.2)max E pixi2

6、 M2 WjXi 2 Pi Yi2并且使得p1Y1 + 壬 Pi yi21Ik由此不難算出P=C(n-1)，其中C表示Catalan數(shù):C(n)計(jì) 2nn +1 (n 丿= Q(4n / n3/2)(6.1.7)也就是說(shuō)，P(n)是隨n指數(shù)增長(zhǎng)的，所以，我們不能希望列舉所有可能次序的連 乘積，從中找到具有最少數(shù)乘次數(shù)的連乘積算法。 事實(shí)上，矩陣連乘積問(wèn)題具有 最優(yōu)子結(jié)構(gòu)性質(zhì)，我們可以采用動(dòng)態(tài)規(guī)劃的方法，在多項(xiàng)式時(shí)間內(nèi)找到最優(yōu)的連 乘積次序。用Ai:j表示連乘積AA + 1“A。分析計(jì)算A1:n的一個(gè)最優(yōu)次序。設(shè)這個(gè) 仁kv n,則完全加括號(hào)方式為，依此次序，我們先分別計(jì)算 A1:k和Ak+1:

7、n,然后將 A1:n?？梢姡珹1:n的一個(gè)最優(yōu)序所包含的矩陣計(jì)算子 的次序也一定是最優(yōu)的。也就是說(shuō)，矩陣連乘問(wèn)題具有最計(jì)算次序在矩陣 A和A+1之間將矩陣鏈分開，(A1A A)( A+1 A)計(jì)算的結(jié)果相乘得到鏈 A1:k和 Ak+1: n優(yōu)子結(jié)構(gòu)性質(zhì)。如上三個(gè)例子都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這個(gè)性質(zhì)決定了解決此類問(wèn)題的基本 思路是：首先確定原問(wèn)題的最優(yōu)值和其子問(wèn)題的最優(yōu)值之間的遞推關(guān)系(自上向 下)，然后自底向上遞歸地構(gòu)造出最優(yōu)解(自下向上)。最優(yōu)子結(jié)構(gòu)性質(zhì)是最優(yōu)化原理得以采用的先決條件。一般說(shuō)來(lái)，分階段選 擇策略確定最優(yōu)解的問(wèn)題往往會(huì)形成一個(gè)決策序列。Bellman認(rèn)為，利用最優(yōu)化原理以及所獲得

8、的遞推關(guān)系式去求解最優(yōu)決策序列，可以使枚舉數(shù)量急劇下降。這里有一個(gè)問(wèn)題值得注意：最優(yōu)子結(jié)構(gòu)性質(zhì)提示我們使用最優(yōu)化原則產(chǎn)生的算法 是遞歸算法，簡(jiǎn)單地使用遞歸算法可能會(huì)增加時(shí)間與空間開銷。例如，用遞歸式直接計(jì)算矩陣連乘積A1:n的算法RecurMatrixChain的時(shí)間復(fù)雜度將是O(2n):程序6-1-1計(jì)算矩陣連乘的遞歸算法int RecurMatrixChain(int i, int j)if (i=j) retu rn 0;int u=RecurMatrixCha in (i, i)+RecurMatrixChai n(i+1,j)+pi-1* p i* pj;sij=i;for(i nt

9、 k=i+1; kj; k+)int t=RecurMatrixChai n(i,k)+RecurMatrixChai n(k+1,j)+p i-1* Pk* pj；if (t1 +(n 1) + Z T(k) T(n k) = n + T(k)，krn心可用數(shù)學(xué)歸納法直接證明：T(n)2n=Q(2n)，這顯然不是我們所期望的。注意到，在用遞歸算法自上向下求解具有最優(yōu)子結(jié)構(gòu)的問(wèn)題時(shí)，每次產(chǎn)生 的子問(wèn)題并不總是新問(wèn)題，有些問(wèn)題被反復(fù)計(jì)算多次。如果對(duì)每一個(gè)問(wèn)題只解一 次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù) 時(shí)間查看一下結(jié)果。則可以節(jié)省大量的時(shí)間。在矩陣的連乘積問(wèn)題中

10、，若用mij表示由第i個(gè)矩陣到第j個(gè)矩陣的連乘積所用的最少數(shù)乘次數(shù)，則計(jì)算+ n= G(n2)個(gè)。下面將會(huì)看到,m1 n時(shí)共有(n2)個(gè)子問(wèn)題。這是因?yàn)?，?duì)于1n，不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問(wèn)題，不同子問(wèn)題最多只有i I2丿用動(dòng)態(tài)規(guī)劃解此問(wèn)題時(shí)，可在多項(xiàng)式時(shí)間內(nèi)完成。程序6-1-2求矩陣連乘最優(yōu)次序的動(dòng)態(tài)規(guī)劃算法void MatrixChai n(int p, int n, i nt * *m, i nt * *s) for (i nt i=1; i=n; i+) mii=0;for (int r=2; rv=n;葉+)for (i nt i=1; iv=n-r+1; i+)int

11、j=i+r-1; r是跨度mij= mi+1j+p i-1* p i* pj; sij=i;for (i nt k=i+1; kj; k+)int t= mik+ mk+1j+pi-1* pk* pj; if (t mij) mij=t;sij=k; 算法Matrixchain的主要計(jì)算量取決于程序中對(duì) r, i和k的三重循環(huán)，循 環(huán)體內(nèi)的計(jì)算量為0(1)，三重循環(huán)的總次數(shù)是om3)，所以，算法的計(jì)算時(shí)間上 界為0(n3)。例子求以下6個(gè)矩陣連乘積最少數(shù)乘計(jì)算次數(shù)及所采用乘法次序。A :30汽35; A :35心5; A3 :15汽5; A :5勺0; A :10氷 20;傀：20汽 25口2

12、2 + m35 + P1P2P5 =0 + 2500 +35兀 15兀 20 = 13000m25 =min 佃23 +m45 + pjPsP5 = 2625 +1000 +35 5 20 = 71251口24 + m 55 + ppp 5 =4375 +0+ 31211375= 7125一般的計(jì)算mij以及sij的過(guò)程如下圖所示:12345612345612i 3456、0 15750、7875 . 9375. 11875 15125 . 0. “2625 .4375 . .7125、10500 U、 750； 25005375.0、. 1000 35000、5000140123456333

13、033340333550si jmi j注意，上述算法只是明確給出了矩陣最優(yōu)連乘次序所用的數(shù)乘次數(shù) m1n，并未明確給出最優(yōu)連乘次序，即完全加括號(hào)方法。但是以sij 為元素的2維數(shù)組卻給出了足夠的信息。事實(shí)上，sij=k 說(shuō)明，計(jì)算連乘積Ai:j 的最佳方式應(yīng)該在矩陣 A和 A+1之間斷開，即最優(yōu)加括號(hào)方式為 (Ai:k)(Ak+1:j)。下面的算法Traceback按算法MatrixChain 計(jì)算出的斷點(diǎn)信息s指示的加括號(hào)方式輸出計(jì)算 Ai:j的最優(yōu)次序。程序6-1-3根據(jù)最優(yōu)值算法構(gòu)造最優(yōu)解Void Traceback(i nt i, i nt j, i nt * * s)if (i=j

14、) return;Traceback(i, sij, s);Traceback(sij+1, j, s); sij;“,” j endl;cout “ Mult ip ly A ” i “, ”cout “and A” (sij +1) 總結(jié)上面解矩陣連乘積問(wèn)題，我們可以歸納出使用動(dòng)態(tài)規(guī)劃算法的基本步驟：1 .分析最優(yōu)解的結(jié)構(gòu)在這一步中，應(yīng)該確定要解決的問(wèn)題應(yīng)該是具有最小子結(jié)構(gòu)性質(zhì)，這是選擇動(dòng)態(tài)規(guī)劃算法的基礎(chǔ)。2. 建立遞歸關(guān)系第一步的結(jié)構(gòu)分析已經(jīng)為建立遞歸關(guān)系奠定了基礎(chǔ)。這一步的主要任務(wù)是遞歸地例如在矩陣連乘定義最優(yōu)值，并建立該問(wèn)題與其子問(wèn)題最優(yōu)值之間的遞歸關(guān)系。 積問(wèn)題中，遞歸關(guān)系為0i = j叫|門=(minmi k + mk +1 j +pi - 1* pk* pj icjI i在0/1背包問(wèn)題中的遞歸關(guān)系是(gj(X)表示0/1背包問(wèn)題Knap(j+1,n,X)的最 優(yōu)值)gj(X) = maxigj*(X),gjMX WjG + Pj V(6.1.8)在多段圖問(wèn)題中的遞歸關(guān)系是COST(i,j)= min c( j,l)+COS