算法設(shè)計(jì)與分析動(dòng)態(tài)規(guī)劃算法_百度文庫(kù)

1、第六章動(dòng)態(tài)規(guī)劃算法.動(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ò)程。在 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)題的最

2、優(yōu)解包含了其子問(wèn)題的一個(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)

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

4、這條路徑上。今假設(shè) s, v2, v3, , , vk-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, v3,vk-1, t一定是v2到t的一條最短路徑。不然，設(shè) v2, q3, , , qk-1, t是一條由v2 到t的比v2, v3, , , vk-1, t更短的路徑，則s, v2, q3, , , qk-1, t是一條由s到t的比s v2, v3, , , vk-1, t更短的路徑。與前面的假

5、設(shè)矛盾。這說(shuō)明多段圖問(wèn)題具有最優(yōu)子 結(jié)構(gòu)性質(zhì)。例2. 0/1背包問(wèn)題有n件物品，第i件重量和價(jià)值分別是wi和pi, i=1,2, , n。要將這n件物品的一 部分裝入容量為c的背包中，要求每件物品或整個(gè)裝入或不裝入，不許分割出一 部分裝入。0/1背包問(wèn)題就是要給出裝包方法，使得裝入背包的物品的總價(jià)值最 大。這個(gè)問(wèn)題歸結(jié)為數(shù)學(xué)規(guī)劃問(wèn)題：max pixi1 i ns.t.1 i nwixi c.0/1背包問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實(shí)上，若m 儀】是最優(yōu)解，則將是0/1背包問(wèn)題的子問(wèn)題：max s.t.2 i nPxii工i2、.n（6.1.2）若y三 Fn是子問(wèn)題(6.1.2)的最優(yōu)解，且使得將是

6、原問(wèn)題(6.1.1)的可行解，并且使得plyl這與卩】是最優(yōu)解相悖。 例3.矩陣連乘問(wèn)題給定n個(gè)數(shù)字矩陣A1，A2，,，An，其中Ai與Ai+1是可乘的，i=1,2,n-1.求矩 陣連乘的加括號(hào)方法，使得所用的數(shù)乘次數(shù)最少?？疾靸蓚€(gè)矩陣相成的情形：C=AB。如果矩陣A，B分別是pk和r q矩陣，則它 們的乘積C將是pq矩陣，其(i, j)元素為cij aikbkj (6,1.5)k It丨i=1,p, j=1,q,因而AB所用的數(shù)乘次數(shù)是prq。如果有至少3個(gè)以上的矩陣連 乘，則涉及到乘積次序問(wèn)題，即加括號(hào)方法。例如3個(gè)矩陣連乘的加括號(hào)方法有兩種：(A1A2)A3)和(A1(A2A3)。設(shè) A

7、1，A2，A3 分別是 pO)1, p1)2，p2)3 矩陣，則以上兩種乘法次序所用的數(shù)乘次數(shù)分別為：p0p1p2+p0p2p3和p0p1p3+p1p2p3如果pO=1O, p仁100, p2=5, p3=50,則兩種乘法所用的數(shù)乘次數(shù)分 別為：7500和750000?？梢姡捎诩永ㄌ?hào)的方法不同，使得連乘所用的數(shù)乘次 數(shù)有很大差別。對(duì)于n個(gè)矩陣的連乘積，令P( n)記連乘積的完全加括號(hào)數(shù)，則有 如下遞歸關(guān)系由此不難算出P=C(n-1)，其中C表示Catalan數(shù)：1 2n C(n) (4n/nJ/2) (t. I ：/) n I n也就是說(shuō)，P(n)是隨n指數(shù)增長(zhǎng)的，所以，我們不能希望列舉所有

8、可能次序的連 乘積，從中找到具有最少數(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表示連乘積AiAi +1 Aj。分析計(jì)算A1:n的一個(gè)最優(yōu)次序。設(shè)這個(gè) 計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈分開，則完全加括號(hào)方式為+n)，依此次序，我們先分別計(jì)算 A1:k和Ak+1:n，然后將計(jì)算的結(jié)果相乘得到 A1:n。可見，A1:n的一個(gè)最優(yōu)序所包含 的矩陣計(jì)算子鏈A1:k和Ak+1:n的次序也一定是最優(yōu)的。也就是說(shuō)，矩陣連乘 問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。如上三個(gè)例子都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這個(gè)性質(zhì)決定了解決此類

9、問(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)化原理以及所獲得的遞推關(guān)系式去求解最優(yōu)決策序列，可以使枚舉數(shù)量急劇下降。4這里有一個(gè)問(wèn)題值得注意：最優(yōu)子結(jié)構(gòu)性質(zhì)提示我們使用最優(yōu)化原則產(chǎn)生的算 法是遞歸算法，簡(jiǎn)單地使用遞歸算法可能會(huì)增加時(shí)間與空間開銷。例如，用遞歸式直接計(jì)算矩陣連乘積 A1:n的算法RecurMatrixChain的時(shí)間復(fù)雜度將是:程序6-1-1計(jì)算矩陣連乘

10、的遞歸算法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)表示該算法的計(jì)算A1:n的時(shí)間，則有如下遞歸關(guān)系式:注意到，在用遞歸算法自上向下

11、求解具有最優(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)題中，若用 mij表示由第i個(gè)矩陣到第j個(gè)矩陣的連乘積所用的最少數(shù)乘次數(shù)，則計(jì)算 m1n時(shí)共有(1個(gè)子問(wèn)題。這是因?yàn)?，?duì)于 i j n，不同的有序?qū)?i, 對(duì)應(yīng)于不同的子問(wèn)題，不同子問(wèn)題最多只有下面將會(huì)看到，Z n二也)個(gè)。2用動(dòng)態(tài)規(guī)劃解此問(wèn)題時(shí)，可在多項(xiàng)式時(shí)間內(nèi)完成。 程序6-1-2求矩陣連乘最優(yōu)次序的動(dòng)態(tài)規(guī)劃算法for (i nt i=1; i=n; i+

12、) 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= 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：1U 2U；A6：2(J 2、Jm|2|2|plpZpi U3、 lb 2()13(川 U m|2| min m|2|3|m|4| plp3p2必 10U03) j 7Q 7125m|2|4| m|5|5| ppp 4375 (J 35 10 20 11375145nrn一般的

13、計(jì)算mij以及sij的過(guò)程如下圖所示：0113330333033304505n佚、iSTSQ 湘頭937, H幻+25 弟漢沬：胚urm I亠初* 2500 5375 ，1000, S5Q0koe1 2 3 4 5 61 2 3 4 5 6 j1 2 3 4 5 6 i1 2 3 4 5 6i mij sij注意，上述算法只是明確給出了矩陣最優(yōu)連乘次序所用的數(shù)乘次數(shù)m1n，并未明確給出最優(yōu)連乘次序，即完全加括號(hào)方法。但是以sij為元素的2維數(shù)組卻給出了足夠的信息。事實(shí)上，sij=k說(shuō)明，計(jì)算連乘積Ai:j的最佳方式應(yīng)該在 矩陣Ak和Ak+1之間斷開，即最優(yōu)加括號(hào)方式為(Ai:k)(Ak+1:j

14、)。下面的算法 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) retur n;Traceback(i, sij, s); Traceback(sij+1, j, s);cout “ Multiply A ” i “, ” sij; cout “and A ” (sij +1) en dl; 總結(jié)上面解矩陣連乘積問(wèn)題，我們可以歸納出使用動(dòng)態(tài)規(guī)劃算法的基本步驟：1. 分析最優(yōu)解的結(jié)構(gòu)在這一步中，

15、應(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)系為- lpkFpji j i k j在0/1背包問(wèn)題中的遞歸關(guān)系是(gj(X)表示0/1背包問(wèn)題Knap(j+1,n,X)的最優(yōu) 值)gj(X) maxgj KXXgj 1(X 兩1) pj 1 (6,1.8)在多段圖問(wèn)題中的遞歸關(guān)系是COST(ij) 1 Vi lj)E min c(jj) COSTfi 1J)(6.1.9)這里j表示取Vi

16、中的頂點(diǎn)j。3. 計(jì)算最優(yōu)值依據(jù)遞歸關(guān)系式可以自底向上的方式(或自頂向下的方式一備忘錄方法)進(jìn)行計(jì) 算，在計(jì)算過(guò)程中保存已經(jīng)解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次，而在后 面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終獲得多項(xiàng)式時(shí)間的算 法。4. 構(gòu)造最優(yōu)解依據(jù)求最優(yōu)值時(shí)記錄的信息，構(gòu)造出最優(yōu)解(如矩陣連乘積)。上述歸納的4個(gè)階段是一個(gè)整體，必要時(shí)才分步完成，很多時(shí)是統(tǒng)一來(lái)完成的。 .多段圖問(wèn)題多段圖是一種簡(jiǎn)單而經(jīng)典的使用動(dòng)態(tài)規(guī)劃算法的模型，它既能有效地反映動(dòng)態(tài)規(guī) 劃算法的基本特征，而且在實(shí)際問(wèn)題中有較多的應(yīng)用。圖6-2-1多段圖的動(dòng)態(tài)規(guī)劃算法執(zhí)行過(guò)程最優(yōu)值遞推關(guān)系式為c(U) COST

17、(i 1,1)(621)其中，COST(ij)表示i段中頂點(diǎn)j到匯點(diǎn)t的最小成本路徑的成本。根據(jù)(621) 式，我們可以由后向前逐步確定各階段中的頂點(diǎn)到匯頂點(diǎn) t的最短路徑。對(duì)于如 上的5階段網(wǎng)絡(luò)圖，藍(lán)色字體標(biāo)出了各頂點(diǎn)到匯頂點(diǎn) t的最短距離。事實(shí)上，我們也可以由前向后逐步確定由源頂點(diǎn)s到各階段中頂點(diǎn)的最短路徑，此時(shí)，最小成本的遞歸關(guān)系為BCOSl(i LD MLj) (6.2.2) BCOSrl(ij) 1 Vminm下圖中的紅色字體標(biāo)出了由源頂點(diǎn) s到各頂點(diǎn)的最短距離。a |圖6-2-2由前向后的處理方法(備忘錄方法) 程序6-2-2多段圖的動(dòng)態(tài)規(guī)劃算法偽代碼MultiGraph(E, k

18、, n, P) /有n個(gè)頂點(diǎn)的k段圖G (按段序統(tǒng)一 編號(hào))，E是邊集, c(i, j)是邊(i, j)的成本，P1:k是最小成本路徑。1 real COST(n); integer D(n-1)，P(k), r, j, k, n; 2 COST(n)=0; 3 4 5 6 7 8 9for j from n-1 by - to 1 do設(shè)r是這樣一個(gè)頂點(diǎn)，且使得c(j, r)+COST(r)取最小值COST(j)= c(j, r)+COST(r); D(j)=r; endforP(1)=1; P(k)=n; for j from 2 to k-1 do1011P(j)=D(P(j-1); e

19、ndfor 12 end MultiGraph這里，D(j)將由j到匯頂點(diǎn)t的最短路徑上j后面的頂點(diǎn)記錄下來(lái)，P(j)則記錄由源 頂點(diǎn)s到匯頂點(diǎn)t的最短路徑上處于第j階段中的頂點(diǎn)。語(yǔ)句10是根據(jù)數(shù)組D中 的信息逐段尋找到由源頂點(diǎn)s到匯頂點(diǎn)t的最短路徑上的各個(gè)頂點(diǎn)。如果用鄰接 表表示圖G，則語(yǔ)句4中r的確定可以在與d+ (j)成正比的時(shí)間內(nèi)完成。因此， 語(yǔ)句3 7的for循環(huán)所需的時(shí)間是。循環(huán)體9 11所需時(shí)間是出 n,因而算法MultiGraph的時(shí)間復(fù)雜度是(n B)o下面給出的備忘錄算法的時(shí)間復(fù)雜度也是如此。程序6-2-3多段圖的備忘錄算法偽代碼MemorizedMultiGraph(E,

20、 k, n, P) /有 n 個(gè)頂點(diǎn)的 k 段圖 G (按段序統(tǒng)一編號(hào))，E是邊集，c(I, j)是邊(I, j)的成本，P1:k是最小成本路徑。1 real BCOST(n); integer D(n-1), P(k), r, j, k, n;232 BCOST(1)=0; for j from 2 to n do設(shè)r是這樣一個(gè)頂點(diǎn)，(匚j)上且使得 BCOST(r)+ c(r, j)取最小值3 BCOST(j)= BCOST(r)+ c(r, j);4 D(j)=r;5 en dfor86 P(1)=1; P(k)=n; for j from k-1 by to 2 do7 P(j)=D(

21、P(j+1);8 en dfor9 end MemorizedMultiGraph. 0/1背包問(wèn)題本節(jié)將使用動(dòng)態(tài)規(guī)劃的由前向后處理方法(也稱備忘錄算法)處理 0/1背包問(wèn)題：max pixi1 1 1110 s.t.11 n W1X1 c. (631) XI : U打 1.2. ,11通過(guò)作出變量x的取值序列來(lái)給出最優(yōu)解。這個(gè)取值序列的對(duì)應(yīng)決策序列是xilAll L上。在對(duì)xn作出決策之后，冋題處于下列兩種狀態(tài)之一：背 包剩余的容量仍為c,此時(shí)未產(chǎn)生任何效益；背包的剩余容量為，此時(shí)的效益值增長(zhǎng)了 pn。因而1 |c wn| pn (6.3.2)一般地，如果記0/1背包子問(wèn)題：max pixi

22、1 i ks.t.1 I k vvx Xjixi1.2, A (63.3)_最優(yōu)解的值為mkX，則有m|k|X| maxm|k l|XLm|k 1|X wk| pk (6.3.4)這里，而且。為使(6.13)式能夠有效地遞推下去，需要延拓 k和X的取值范圍：；補(bǔ)充定義：ilX 0;m0兇 mk 01 L2, n(6.3,5) OifX 0;事實(shí)上，我們的主要目的是計(jì)算出mnc，根據(jù)(6.11)式，我們可能需要計(jì)算，而為了計(jì)算，可能需要計(jì)算，如此等等，在遞推公式(6.13)中用到的X值可能為負(fù)數(shù)。另外，如果將mkX看作X的函數(shù)，則是一個(gè)分段函數(shù)，而且當(dāng)取常值。所以將X的取值范圍延拓至全體實(shí)數(shù)。例

23、子。丨i k wi時(shí)X Om0X,0X 0X 0mflirX 00 X 2maxJO.O 1 IX 2X 000 X 212 X 3 maxL0 2 23 X 5LI 2 3X 5 max0 1 2 2.0 5 5m2VX max門3,0 5 5 max max3.1 5 6max3.2 5 7 23 5 8 maxX00 X 22 X 33 X 44 X 55 X 66 X 77 X 9X 9m 0X wl pl in川X w2 p2m2X w3 p3上述諸函數(shù)mkX具有如下性質(zhì)：1每個(gè)階梯函數(shù)mkX都是由其跳躍點(diǎn)偶(b,mkb)決定的。如果有個(gè)跳 躍點(diǎn)，各點(diǎn)的函數(shù)值分別是vO,，貝Um|k

24、|X| viitbi X bi Li ()丄 j (6.3.6)這里約定加I 。2令Sk是階梯函數(shù)mkX的跳躍點(diǎn)偶的集合，貝U階梯函數(shù)的跳躍點(diǎn)偶之集去掉點(diǎn)偶(0,0)后，恰是集合i-(b,v)|(b wk:v pk) Sk 1 (63.7) Sa12這是因?yàn)楹瘮?shù)的圖象恰是由函數(shù)叫k川X的圖象先向右平移wk，然后再向上移動(dòng)pk而得。如前面例子3llX-w J + pi2 .HI K I0 1 2 3 4 5 6 0 1 2 3 4 5 6 712S=(0,0), (2,1) (w2, p2)=(3, 2) Sa= (3,2), (5,3)I1j11J11 一 卜卜1I2S=(0,0), (2,1

25、), (3,2), (5,3) 0 1 2 3 4 5 6 7kk-1kk-1k根據(jù)遞推公式(634), S是從5 切中去掉那些點(diǎn)偶(bi,vi):在5 M 中存在點(diǎn)偶(bk,vk)使得bi bk而且疏vk,此時(shí)我們說(shuō)(bk,vk)淹沒(bi,vi)。前面例子 的諸Sk計(jì)算如下：ISO U0.(J);(wLpl) (2J),Sa (wLpl) SO (2J)閒 1衛(wèi)2)(蘋)抄 何Zp2) SI (3J)臚小 |S2 QU)，a)Q2)Qj;(wp勺(A* |卩出丈(4Q)他|S3 (0肋、(ZUG2)：(43h他饑億幾(90爪 |3在由S2、Sa向S3的歸并過(guò)程中，(5, 3)被(4, 5)

26、淹沒。k 3 在處理實(shí)際問(wèn)題時(shí)，由于要求，在計(jì)算時(shí)應(yīng)該去掉那些使得的跳躍點(diǎn)偶(b,v)。根據(jù)前面的提到的淹沒規(guī)則，如果將 S中的元素按照第一個(gè)分量的遞增次序排列，則第二個(gè)分量也呈遞增的次序，而且Sn的最后一個(gè)元素，設(shè)為(b,v)，的v值即是0/1背包問(wèn)題(6.3.1 )的最優(yōu)值mnc。k4.最優(yōu)解的獲得可以通過(guò)檢查諸Sk來(lái)確定。設(shè)(bkn,vkn)是Sn的最后一個(gè)元素。若(bkn?vkn) Sn 1,則x口 0.因?yàn)榇藭r(shí)函數(shù)mnX和函數(shù)mn 1X在X C 范圍內(nèi)的最大值一致，表明0/1背包問(wèn)題(6.3.1)與其子問(wèn)題maxs.t.l i n 1 px ii1 i n 1 wx c w.iinx

27、i OJj 1,2, .n 1 (638)有相同的最優(yōu)值。若，貝U。因?yàn)?，此時(shí)函數(shù)mnX在X (:范圍內(nèi)的最大值是函數(shù)1X的最大值加pn,相應(yīng)地，0/1背包問(wèn)題(6.3.1)的最優(yōu)值是其子問(wèn)題(6.3.8)的最優(yōu)值加pn。注意到此時(shí)跳躍點(diǎn)偶一定具有 形式(bkn/kn) (wn?pn) (bhi Lkn 1) (6.3.9)其中(bkii l:vkn 1) Sn 1。于是，我們可以依(bkii l.vkn 1) Sn 2與否而 決定功 1取0或1。如此等等，我們可以逐一確定XHA11 1,川的值。在上述例子中，整理后的諸 Sk為：so |Si (W);q (山切厶|S3 W(),(2),2),

28、(4.5),(d6).2(6, 6)是S3的最后一個(gè)跳躍點(diǎn)偶，所以該 0/1問(wèn)題的最優(yōu)值是6。這個(gè)點(diǎn)偶不在 S2中，因而又，據(jù)此判斷x2的取值。因?yàn)?，所?；最后由知，所以最優(yōu)解為(1,0,1).為實(shí)現(xiàn)上述算法，可以用兩個(gè)一維數(shù)組B和V來(lái)存放所有的跳躍點(diǎn)偶(b, v)，跳躍點(diǎn)偶集互相鄰接地存放(將諸Si中的全部元素統(tǒng)一編號(hào)，從 Si生成時(shí)，元素也是遞升地產(chǎn)生，而且使用淹沒規(guī)則)，并用指針 F(k)來(lái)指示集合Sk,即卩Sk的第一個(gè)元素的位置，而F(n)-1是 1中最后一個(gè)元素的位 置(這里不存放Sn是由于我們只需要它的最后一個(gè)元素，而這個(gè)元素或者是Sn-1的最后一個(gè)元素，此時(shí)Sn-1與Sn有相同

29、的最后元素；或者具有形式(6.3.9)，而 14且vkn是滿足bkn 1 vn c的最大值。所以，確定s的最后元素不必將s的 元素全部求出來(lái)。而且確定最優(yōu)解的其它變量時(shí)也不使用數(shù)據(jù)Sn)。因?yàn)楫a(chǎn)生 kSk僅使用信息Sk-1和(wk,pk)，所以不必存儲(chǔ)Sa。根據(jù)以上分析，我們不難給 出nn 動(dòng)態(tài)規(guī)劃解0/1背包問(wèn)題的算法偽代碼。程序6-3-1 0/1背包冋題動(dòng)態(tài)規(guī)劃算法偽代碼DKnapsack(w, p, c, n, m) /數(shù)組w, p中的元素分別代表各件物品的重量和價(jià)值，n是物品個(gè)數(shù)，c代表背包容量real p(n), w( n), B(m), V(m), ww, pp, c;in teg

30、er FO:n , I, h, i, j, p, n ext;F0=1; B0=V0=0; l=1; h=1; /SO的首和尾F(1)=2; next=2; / B、V 中的第一個(gè)空位for i from 1 to n-1 dok=l;口=最大指標(biāo)r,使得1h而且Br+wi c;for j from I to u do(ww, pp)=( Bj+wi, Vj+pi); /Sia 中的下一個(gè)元素while k h& Bk Vn ext-1 the n(Bnext, Vnext)=(ww, pp);n ext=n ext+1;en difwhile k h & Vk吒 Vnext-1 do 清除k

31、=k+1;en dwhileen dfor將Si-1剩余的元素并入Si(Bnext, Vnext)= (Bk, Vk);n ext=n ext+1; k=k+1;en dwhilel=h+1; h=next-1; F(i+1)=next; / 為 Si+1 賦初值en dfortraceparts 逐一確定 XHAH 匕 Alend Dknapsack算法DKnapsack的主要工作是產(chǎn)生諸 Si。在i 0的情況下，每個(gè)Si由Si-1和Sia歸并而成，并且-1|。因此-1|，1 1 n 1 Si 11i ii 1 2i 11 2n 115算法DKnapsack的時(shí)間復(fù)雜度為0(2n)。如果物品

32、的重量wi和所產(chǎn)生的效益值pi都是整數(shù)，那么，Si中的元素(b,v)的分 量b和v也都是整數(shù)，且也都是不同的，故。又Si中不同的元素對(duì)應(yīng)的各分量Si| 11廠1 丁飛卄丁廠11 丁為一2口 由此知，算法DKnapsack的空間復(fù)雜度是0(2n)。 由Si-1生成Si需要間為(|Sl 1|)的時(shí)間，因此，計(jì)算S05L ,S11 1總共需要的時(shí)11 k 1 pk |S|1 nun wk.c 1 k 1D 此時(shí)算法DKnapsack的時(shí)間復(fù)雜度為0(mm Jmcai pk )附：從組合的角度來(lái)理解0/1背包問(wèn)題先假定背包的容量是充分大的，考慮有 k件物品往背包里裝時(shí)，背包中物品總重 量的各種可能出現(xiàn)

33、的情況：k 0:W00k 1:W10,wlk 2:V2U.wL認(rèn)2許 1 w2k 3:W3 0,wLw2.wl w2av3,w1 w3,w2 w3;wl w2 w316 一般地，k Wk xiwixi 0,1(639) i 1而k 12 ,n 1(6.3.10) Wk 1 Wkwk 1 Wk ，k遞推關(guān)系式(6310)正是我們計(jì)算諸Sk和Sa的依據(jù)，這只需將各種 重量”情 k況所對(duì)應(yīng)的總價(jià)值帶上，即產(chǎn)生元素對(duì)(b,v)，就能獲得諸Sk和Sa。如上面的例 子：1麗(訓(xùn)1)切(2) | |S1 SO (wl,pl) SO (0仇(2);(w2,p2) (3耳丨 2Sa (w2,p2) SI (3t

34、2)/5J)|S2 SI (w22) SI 他小(2)32)53);何切3)他5), | 3Sa (w3屈)S2 (4,5)(6,6)/7,7)紗於)|S3 S2 (w3屈)S2何仇2匕2)他5)6)仏7),儀8)1去掉被淹沒的(5,3)最 后將S3截?cái)?根據(jù)約束條件)，即去掉重量”大于背包容量的點(diǎn)對(duì)，就得到所 需要的點(diǎn)對(duì)集得到最大價(jià)值是6,因?yàn)镾2,應(yīng)該是在前面的基礎(chǔ)上增加了而獲得的，這個(gè) 基礎(chǔ)”就是，所以，最優(yōu)解中，。再考慮的情況，在最優(yōu)解中應(yīng)有。最后由S0知，在最優(yōu)解中xl 1。所以，(1,0,1)就是上面背包問(wèn)題的一個(gè)最優(yōu) 解。.流水作業(yè)調(diào)度問(wèn)題問(wèn)題描述：已知n個(gè)作業(yè)1,2, . .

35、. , n要在由兩臺(tái)機(jī)器M1和M2組成的流水線上 完成加工。每個(gè)作業(yè)加工的順序都是先在 M1上加工，然后在M2上加工。M1和 M2加工作業(yè)i所需的時(shí)間分別為ai和bi, 1 i 11。流水作業(yè)調(diào)度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)加工次序，使得從第一個(gè)作業(yè)在機(jī)器M1上開始加工，到最后一個(gè)作業(yè)在機(jī)器 M2上加工完成所需的時(shí)間最少。記N=1,2, . . . , n，S為N的子集合。一般情況下，當(dāng)機(jī)器 M1開始加工S中的 作業(yè)時(shí)，機(jī)器M2可能正在加工其它的作業(yè)，要等待時(shí)間 t后才可用來(lái)加工S中 的作業(yè)。將這種情況下流水線完成 S中的作業(yè)所需的最短時(shí)間記為 T(S, t)，則流 水作業(yè)調(diào)度問(wèn)題的最優(yōu)值即是

36、T(N, 0)。流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實(shí)上，設(shè)是n個(gè)流水作業(yè)的一個(gè)最優(yōu)調(diào)度(實(shí)際上是作業(yè)的一個(gè)排序)，其所需要的加工時(shí)間為，其中，T是在機(jī)器M2的等待時(shí)間為時(shí)，調(diào)度 安排作業(yè)所需的時(shí)間。若記，我們證明。首先由T的定義知。如果，設(shè):是作業(yè)集S在機(jī)器M2等待時(shí)間為b情況下的一個(gè)最優(yōu)調(diào)度，貝U是N的一個(gè)調(diào)度，該調(diào)度所需的時(shí)間為a，這與是N的最優(yōu)調(diào)度矛盾。所以T TfS.b (1),說(shuō)明流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)性 質(zhì)。關(guān)于流水作業(yè)調(diào)度問(wèn)題的最優(yōu)值遞推關(guān)系式，我們可以如下建立。容易看出T(N、O) minai T(N i,bi) (6.4.1) 1 i n上述關(guān)系式可以推廣到一般情

37、形：T(S) minai T(S i,bi maxi 訕) (6.4.2) i 旳其中，這一項(xiàng)是由于在機(jī)器 M2上，作業(yè)i必須在maxt,ai時(shí)間之后才能開工。因此，在機(jī)器 M1完成作業(yè)i之后，機(jī)器M2還需等待bi maxlfai ai bi maxi ai:0 時(shí)間后才能完成對(duì)作業(yè)i的加工。按照遞推關(guān)系(642)，我們?nèi)菀捉o出流水調(diào)度問(wèn)題的動(dòng)態(tài)規(guī)劃算法，但是其時(shí)間 復(fù)雜度將是0(2n)。以下我們將根據(jù)這一問(wèn)題的特點(diǎn)，采用Johnson法則簡(jiǎn)化算法，使得到時(shí)間復(fù)雜度為0( nl og n)。則由遞推關(guān)系設(shè) 是作業(yè)集S在機(jī)器M2的等待時(shí)間為t時(shí)的任一最優(yōu)調(diào)度。若在這個(gè)調(diào)度 中，安排在最前面的兩個(gè)

38、作業(yè)分別是i和j,即ai.LI-o-X -aItaxmR-xsai.246bj bi maxft ai aj,max aj, bi(上述推導(dǎo)中用到了關(guān)系式A.BL max；A BL .A Bl；)如果作業(yè)i和j滿足mjnjai.bj mjnjaj.bi (6.4.3)則稱作業(yè)i和j滿足Johnson不等式；不等式(643)等價(jià)于maxj aj, tn max-j aL bj (6.4.4)此時(shí)，hj iji。因而i,j,tji) (645)如果作業(yè)i和j不滿足Johnson不等式，則交換作業(yè)i和j的加工次序使?jié)M足Johnson不等式。在作業(yè)集S當(dāng)機(jī)器M2的等待時(shí)間為t時(shí)的調(diào)度中，交換作業(yè)i和j

39、的加工次序，得到作業(yè)集S的另一個(gè)調(diào)度I，它所需的加工時(shí)間為i,j,tji)根據(jù)(6.4.5)式，。說(shuō)明當(dāng)作業(yè)i和j不滿足Johnson不等式時(shí)，交換它們的加工次序后，不會(huì)增加加工時(shí)間。由此可知，對(duì)于流水作業(yè)調(diào)度問(wèn)題，必 然存在一個(gè)最優(yōu)調(diào)度，使得作業(yè)和滿足Johnson不等式：口亂b (11)(1 lb i u 1|一般地，可以證明，上述不等式與不等式mina (i):b (j) min|a (j),bi j n (6.4,4)等價(jià)。以下給出的是流水作業(yè)調(diào)度問(wèn)題的Joh nson算法：(1) 令(2) 將AB中作業(yè)依ai的非減次序排列；將BA中作業(yè)依bi的非增次序排列；AB中作業(yè)接BA中作業(yè)即構(gòu)

40、成滿足Johnson法則的最優(yōu)調(diào)度。程序 6-4-1 流水作業(yè)調(diào)度問(wèn)題的 Johnson算法 int FlowShop(int n, int a, int b, int c)class Jobtypepublic:int operator = (Jobtype a) constreturn (key = a.key);int key;int in dex;bool job;Jobtype *d=new Jobtype n;for (i nt i = 0; i bi ? bi : ai;Di.job = ai = bi;Di.i ndex = i;sort(d, n)int j = 0, k =

41、 n-1;for (i nt i = 0; i n; i+) if ( di.job ) cj+ = di.i ndex;else ck- = di.i ndex;j = ac0;k = j + bc0;for (i nt i = 1; i n; i+) j + =aci;k = j k ? k + bci : j + bci;20 delete d;return k;上述算法的時(shí)間主要花在排序上，因此，在最壞情況下的時(shí)間復(fù)雜度為O(nlogn)?？臻g復(fù)雜度為0(n)更容易看出。.最優(yōu)二叉搜索樹設(shè)是一個(gè)有序集合，且表示有序集合的二叉搜索樹是利用二叉樹的頂點(diǎn)存儲(chǔ)有序集中的元素，而且具有性質(zhì)：存儲(chǔ)

42、于每個(gè)頂點(diǎn) 中的元素x大于其左子樹中任一個(gè)頂點(diǎn)中存儲(chǔ)的元素，小于其右子樹中任意頂點(diǎn) 中存儲(chǔ)的元素。二叉樹中的葉頂點(diǎn)是形如的開區(qū)間。在二叉搜索樹中搜索一個(gè)元素X，返回的結(jié)果或是在二叉樹的內(nèi)部頂點(diǎn)處找到：或是在二叉樹的葉頂點(diǎn)中確定：x現(xiàn)在假定在第一種情況出現(xiàn)，即的概率為bi;在第二種情況出現(xiàn)，即的概率為ai.這里約定AH 1顯然ai 0,0 i n:bj 0?l j n; ai bj 1 (6.5.1)|i 0, Inn |集合JaO.bLal.稱為有序集S的存取概率分布在一個(gè)表示S的二叉搜索樹T中，設(shè)存儲(chǔ)元素xi的頂點(diǎn)深度(從根到該頂點(diǎn)的距 離)為ci，葉頂點(diǎn)的深度為di，則.2)I lj Unn表示在二叉搜索樹T中做一次搜索所需的平均比較次數(shù)。p也稱為二叉搜索樹T 的平均路長(zhǎng)。最優(yōu)二叉搜索樹問(wèn)題是對(duì)于有序集S及其存取概率分布，在所有表示S的二叉搜索樹中，找出