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

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

3、規(guī)劃算法通常只需要多項式時間，從而 獲得較高的解題效率。最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì) 是采用動態(tài)規(guī)劃算法的 兩個基本要素。 例1 多段圖問題 設(shè)G=（V,E）是一個賦權(quán)有向圖，其頂點集V被劃分成k2個不相交的子集V: 1_k，其中，M和Vk分別只有一個頂點s（稱為源）和一個頂點t（稱為匯），下圖 中所有的邊（u,v）的始點和終點都在相鄰的兩個子集 V和V +1 中: u V，v V +1。 s 4 2 4 6 7 9 6 9 9 4 4 2 5 3 6 2 5 3 7 1 10 7 18 1 12 11 4 7 5 8 2 1 5 5 1 6 5 8 多階段圖問題：求由S到t的最小成本路徑（

4、也叫最短路徑）。 對于每一條由s到t的路徑，可以把它看成在k-2個階段作出的某個決策序列的相應(yīng)結(jié)果：第i步?jīng)Q策就是確定V+1中哪個頂點在這條路徑上。今假設(shè)s, V2, V3,，V k-1 , t是一條由s到t的最短路徑，再假定從源點s(初始狀態(tài))開始， 已經(jīng)作出了到頂點V2的決策(初始決策)，則V2就是初始決策產(chǎn)生的狀態(tài)。若將 V2看成是原問題的子問題的初始狀態(tài)，這個子問題就是找一條由V2到t的最短路 徑。事實上，路徑V2, V 3,，V k-1, t 定是V2到t的一條最短路徑。不然， 設(shè) V2, q 3, ，q k-i, t 是一條由 V2至卩t的比 V2, v 3, ，v k-i, t

5、更短的路徑， 貝U s, V 2, q 3, ，q 巴 _是一條由 s至U t的比 s, V 2, v 3, ，v , t 更短的 路徑。與前面的假設(shè)矛盾。這說明多段圖問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 例2. 0/1背包問題 有n件物品，第i件重量和價值分別是w和pi, i=1,2,n。要將這n 件物品的某些件裝入容量為c的背包中，要求每件物品或整個裝入或不裝入，不 許分割出一部分裝入。0/1背包問題就是要給出裝包方法，使得裝入背包的物品 的總價值最大。這個問題歸結(jié)為數(shù)學(xué)規(guī)劃問題： max 二 Pi Xi i丄印 s.t. vWjXi EC, Xi 0,1, i =1,2, ,n (6.1.1) i豈

6、豈 0/1背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實上，若2,yn是最優(yōu)解， 則%, ,yn將是0/1背包問題的子問題： max pixi 2 勺切 s.t.WjXi 乞 c yw , Xi 0,1, i = 2，n 2豈勺 (6.1.2) 最優(yōu)解。因為，若y；,，yn是子問題(6.1.2)的最優(yōu)解，且使得 Piyi Pi yi 2 ln2 豈 m (6.1.3) 則,丫2,，yn將是原問題(6.1.1)的可行解，并且使得 P1、Piyi、Piyi(6.1.4) 2査至1 這與肆2,yn是最優(yōu)解相悖。 例3.矩陣連乘問題 給定n個數(shù)字矩陣A，A,，An，其中A與A+1是可乘的，i=1,2，,n-1. 求

7、矩陣連乘AAA的加括號方法，使得所用的數(shù)乘次數(shù)最少。 考察兩個矩陣相成的情形：C=AB如果矩陣A, B分別是px r和r x q矩陣, 則它們的乘積C將是px q矩陣，其(i, j) 元素為 r Cij 八 aik bkj(6.1.5) i=1,p, j=1,q,因而AB所用的數(shù)乘次數(shù)是prq。如果有至少3個以上的 矩陣連乘，貝U涉及到乘積次序問題，即加括號方法。例如3個矩陣連乘的加括號 方法有兩種：(AiA)A3)和(Ai(AA)。設(shè) A, A, A 分別是 poX pi, pi x p2, p2X P3矩陣，則以上兩種乘法次序所用的數(shù)乘次數(shù)分別為：卩0卩22+5郵3和PoPlP3+PlP2

8、P3。 如果po=io, p 1=100, p 2=5, p 3=50,則兩種乘法所用的數(shù)乘次數(shù)分別為：7500和 750000。可見，由于加括號的方法不同，使得連乘所用的數(shù)乘次數(shù)有很大差別。 對于n個矩陣的連乘積，令P(n)記連乘積的完全加括號數(shù)，則有如下遞歸關(guān)系 彳n =1 P(n )1、 彳(6.1.6) Z P(k)P(n -k) n1/ k A 由此不難算出P=C(n-1)，其中C表示Catalan數(shù)： C(門)=丄 2nLo(4n/n3/2)(6.1.7) n +Un 丿 也就是說，P(n)是隨n指數(shù)增長的，所以，我們不能希望列舉所有可能次序的連 乘積，從中找到具有最少數(shù)乘次數(shù)的連

9、乘積算法。 事實上，矩陣連乘積問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì)，我們可以采用動態(tài)規(guī)劃的方法，在多項式時間內(nèi)找到最優(yōu)的連 乘積次序。 用Ai:j表示連乘積AA +1A。分析計算A1:n的一個最優(yōu)次序。設(shè)這個 計算次序在矩陣 A和A+1之間將矩陣鏈分開，1_kn,則完全加括號方式為 (A1A2 A)( A+1 A)，依此次序，我們先分別計算 A1:k和Ak+1:n,然后將 計算的結(jié)果相乘得到 A1:n。可見，A1:n的一個最優(yōu)序所包含的矩陣計算子 鏈A1:k和Ak+1:n的次序也一定是最優(yōu)的。也就是說，矩陣連乘問題具有最 優(yōu)子結(jié)構(gòu)性質(zhì)。 如上三個例子都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這個性質(zhì)決定了解決此類問題的基本

10、思路是： 首先確定原問題的最優(yōu)值和其子問題的最優(yōu)值之間的遞推關(guān)系(自上向 下)，然后自底向上遞歸地構(gòu)造出最優(yōu)解(自下向上)。 最優(yōu)子結(jié)構(gòu)性質(zhì)是最優(yōu)化原理得以采用的先決條件。一般說來，分階段選 擇策略確定最優(yōu)解的問題往往會形成一個決策序列。Bellman認(rèn)為，利用最優(yōu)化 原理以及所獲得的遞推關(guān)系式去求解最優(yōu)決策序列，可以使枚舉數(shù)量急劇下降。 這里有一個問題值得注意：最優(yōu)子結(jié)構(gòu)性質(zhì)提示我們使用最優(yōu)化原則產(chǎn)生的算法 是遞歸算法，簡單地使用遞歸算法可能會增加時間與空間開銷。例如，用遞歸式 直接計算矩陣連乘積A1:n的算法RecurMatrixChain 的時間復(fù)雜度將是 “(2n): 程序6-1-1計

11、算矩陣連乘的遞歸算法 int RecurMatrixChai n(int i, i nt j) if (i=j) retur n 0; int u=RecurMatrixCha in (i, i) +RecurMatrixChai n(i+1,j) +pi-1*pi*pj； sij=i; for(int k=i+1; kj; k+) int t=RecurMatrixChai n(i,k) +RecurMatrixChai n(k+1,j) +pi-1*pk*pj; if (tu) u=t; sij=k; return u; 如果用T(n)表示該算法的計算A1:n的時間，則有如下遞歸關(guān)系式：

12、O(1) T(n)糾 I n -4 1 k 1 仃(k) T(n - k) 1) nVnnV T(n) _1 (n -1)二 T(k)二 T(n k)二 n 2 T(k), kmk=ikm 可用數(shù)學(xué)歸納法直接證明： T(n) -2n4 =-J(2n)，這顯然不是我們所期望的。 注意到，在用遞歸算法自上向下求解具有最優(yōu)子結(jié)構(gòu)的問題時，每次產(chǎn)生 的子問題并不總是新問題，有些問題被反復(fù)計算多次。如果對每一個問題只解一 次，而后將其解保存在一個表格中，當(dāng)再次需要解此問題時，只是簡單地用常數(shù) 時間查看一下結(jié)果。則可以節(jié)省大量的時間。在矩陣的連乘積問題中，若用mij表示由第i個矩陣到第j個矩陣的連乘積所用

13、的最少數(shù)乘次數(shù)，則計算 m1n時共有a(n2)個子問題。這是因為，對于1卻乞j乞n，不同的有序?qū)?i, j)對應(yīng)于不同的子問題，不同子問題最多只有n +n= G(n2)個。下面將會看到, 丿 用動態(tài)規(guī)劃解此問題時，可在多項式時間內(nèi)完成。 程序6-1-2求矩陣連乘最優(yōu)次序的動態(tài)規(guī)劃算法 void MatrixCha in (i nt p, int n, int * *m, int * *s) for (i nt i=1; i=n; i+) mii=0; for (int r=2; r=n; r+) for (i nt i=1; i=n-r+1; i+) int j=i+r-1; r是跨度 mij

14、= mi+1j+pi-1*pi*pj; sij=i; for (int k=i+1; kj; k+) int t= mik+ mk+1j+pi-1*pk*pj; if (t mij) mij=t; sij=k; 算法MatrixChain的主要計算量取決于程序中對 r, i和k的三重循環(huán)，循 環(huán)體內(nèi)的計算量為0(1)，三重循環(huán)的總次數(shù)是0(n)，所以，算法的計算時間上 界為O(n3)。 例子求以下6個矩陣連乘積最少數(shù)乘計算次數(shù)及所采用乘法次序。 A :30 35;A2:35 15;A3:15 5;幾：5 10;乓：10 20; Ae : 20 25 m(22 m35 p1p2p0 2500 3

15、5 15 20 =13000 m25 =min m23 +m4 5 + p1 p3p5 = 2625 +1000 +35 漢 5漢 20 = 7125 m(24 m5 5 p1 p4 p 4375 0 35 10 20 = 11375 = 7125 般的計算mij以及sij的過程如下圖所示: 1 2 34 5 6 0 15750 7875 9375 11375 15125 02625 4375 7125 10500 07502500 5375 01000 3500 05000 0 1 2 i 3 4 5 6 1 0 1 1 3 3 3 2 0 2 3 3 3 3 0 3 3 3 4 5 0 4

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

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