1、,7.1 一般方法和基本要素 7.2 每對(duì)結(jié)點(diǎn)間的最短路徑 7.3 矩陣連乘 7.4 最長(zhǎng)公共子序列 7.5 最優(yōu)二叉搜索樹 7.6 0/1背包 7.7 流水作業(yè)調(diào)度,第7章 動(dòng)態(tài)規(guī)劃法,20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman(理查德貝爾曼)等人在研究多階段決策過程的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，創(chuàng)立了解決這類過程優(yōu)化問題的新方法動(dòng)態(tài)規(guī)劃。 動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。 應(yīng)用領(lǐng)域：動(dòng)

2、態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。,動(dòng)態(tài)規(guī)劃法的實(shí)質(zhì)也是將較大問題分解為較小的同類子問題，這一點(diǎn)上它與分治法和貪心法類似。但動(dòng)態(tài)規(guī)劃法有自己的特點(diǎn)。分治法的子問題相互獨(dú)立，相同的子問題被重復(fù)計(jì)算，動(dòng)態(tài)規(guī)劃法解決這種子問題重疊現(xiàn)象。貪心法要求針對(duì)問題設(shè)計(jì)最優(yōu)量度標(biāo)準(zhǔn)，但這在很多情況下并不容易。動(dòng)態(tài)規(guī)劃法利用最優(yōu)子結(jié)構(gòu)，自底向上從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解，動(dòng)態(tài)規(guī)劃則可以處理不具備貪心準(zhǔn)則的問題。,7.1 一般方法和基本要素,7.1.1

3、一般方法,最優(yōu)性原理指出，一個(gè)最優(yōu)策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，其余決策必定構(gòu)成最優(yōu)策略。這便是最優(yōu)決策序列的最優(yōu)子結(jié)構(gòu)特性。,7.1.2 基本要素,一個(gè)最優(yōu)化多步?jīng)Q策問題適合用動(dòng)態(tài)規(guī)劃法求解有兩個(gè)要素：最優(yōu)子結(jié)構(gòu)特性和重疊子問題。,7.1.3 多段圖問題,例71 多段圖G=(V,E)是一個(gè)帶權(quán)有向圖，它具有如下特性：圖中的結(jié)點(diǎn)被劃分成k2個(gè)互不相交的子集Vi，1ik。其中V1和Vk分別只有一個(gè)結(jié)點(diǎn)，V1包含源點(diǎn)（source）s，Vk包含匯點(diǎn)（sink）t。對(duì)所有邊E，多段圖要求若uVi，則vVi1，1ik，每條邊的權(quán)值為c(u,v)。從s到t的路

4、徑長(zhǎng)度是這條路徑上邊的權(quán)值之和，多段圖問題（multistage graph problem）是求從s到t的一條長(zhǎng)度最短的路徑。,結(jié)點(diǎn)：結(jié)點(diǎn)集V被分成k2個(gè)不相交的集合Vi，1ik，其中V1和Vk分別只有一個(gè)結(jié)點(diǎn)：s(源結(jié)點(diǎn))和t(匯點(diǎn))。 段： 每一集合Vi定義圖中的一段共k段。 邊： 所有的邊(u,v)均具有如下性質(zhì)： 若E，則若uVi，則uVi1,即該邊將是從某段i指向i+1段，1ik1。 成本：每條邊(u,v)均附有成本c(u,v)。 s到t的路徑：是一條從第1段的源點(diǎn)s出發(fā)，依次經(jīng)過第2段的某結(jié)點(diǎn)v2i，經(jīng)第3段的某結(jié)點(diǎn)v3j、最后在第k段的匯點(diǎn)t結(jié)束的路徑。 該路徑的成本是這條路徑

5、上邊的成本和。 多段圖問題：求由s到t的最小成本路徑。,多段圖問題的多階段決策過程：生成從s到t的最小成本路徑是在k-2個(gè)階段（除s和t外）進(jìn)行某種決策的過程：從s開始，第i次決策決定Vi+1(1ik-2)中的哪個(gè)結(jié)點(diǎn)在從s到t的最短路徑上。 1.最優(yōu)性原理對(duì)多段圖問題成立 假設(shè)s,v2,v3,vk-1,t是一條由s到t的最短路徑。 初始狀態(tài)：s 初始決策：(s,v2)， v2V2 初始決策產(chǎn)生的狀態(tài)：v2 則，其余的決策：v3,.,vk-1相對(duì)于v2將構(gòu)成一個(gè)最優(yōu)決策序列最優(yōu)性原理成立。 反證：若不然，設(shè)v2,q3,qk-1,t是一條由v2到t的更短的路徑，則s, v2,q3,qk-1,t將

6、是比s,v2,v3,vk-1,t更短的從s到t的路徑。與假設(shè)矛盾。 故，最優(yōu)性原理成立,即，是v2 ，v3,.,vk-1，t構(gòu)成從v2至t的最短路徑,2. 向前處理(遞推)策略求解 設(shè) P(i,j)是一條從Vi中的結(jié)點(diǎn)j到匯點(diǎn)t的最小成本路徑， cost(i,j)是這條路徑的成本。 1) 向前遞推式 cost(k,t)=0 2) 遞推過程 第k-1段 c(j,t) E COST(k-1,j) = ,0ik-2,l1,l2,. . .,lpi+1,t,j,Vi,Vi+1,各遞推結(jié)果 第4段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2 COS

7、T(4,11) = c(11,12) = 5 第3段 COST(3,6) = min6+COST(4,9),5+COST(4,10) = 7 COST(3,7) = min4+COST(4,9),3+COST(4,10) = 5 COST(3,8) = min5+COST(4,10),6+COST(4,11) = 7 第2段 COST(2,2) = min4+COST(3,6) , 2+COST(3,7), 1+COST(3,8) = 7 COST(2,3) = 9 COST(2,4) = 18 COST(2,5) = 15 第1段 COST(1,1) = min9+COST(2,2),7+C

8、OST(2,3), 3+COST(2,4),2+COST(2,5) = 16 S到t的最小成本路徑的成本 16, 最小成本路徑的求取 記 d(i,j)每一cost(i,j)的決策 即，使c(j,p)+cost(i+1,p)取得最小值的p值。 例：d(3,6)=10, d(3,7)=10 ,d(3,8)=10 d(2,2)=7, d(2,3)=6, d(2,4)=8, d(2,5)=8 d(1,1)=2 根據(jù)d(1,1)的決策值向后遞推求取最小成本路徑： v2=d(1,1)=2 v3=d(2,d(1,1)=7 v4=d(3,d(2,d(1,1)=d(3,7)=10 故由s到t的最小成本路徑是：1

9、271012,3) 算法描述 結(jié)點(diǎn)的編號(hào)規(guī)則 源點(diǎn)s編號(hào)為0,然后依次對(duì)V2、V3Vk-1中的結(jié)點(diǎn)編號(hào)，匯點(diǎn)t編號(hào)為n-1。 目的：使對(duì)cost和d的計(jì)算僅按n-1,n-2,1的次序計(jì)算即可，無需考慮標(biāo)示結(jié)點(diǎn)所在段的第一個(gè)下標(biāo)。 算法描述,【程序71】多段圖的向前遞推算法 template void Graph:FMultiGraph(int k,int *p) /采用程序68的鄰接表存儲(chǔ)圖G。 float *cost=new floatn; int q,*d=new intn; costn-1=0,dn-1=-1;,for (int j=n-2;j=0;j-) float min=INFTY

10、; for (ENode *r=aj;r;r=r-nextArc) int v=r-adjVex; if (r-w+costvw+costv;q=v; costj=min;dj=q; p0=0;pk-1=n-1; for(j=1;j=k-2;j+) pj=dpj-1; delete cost;delete d; ,算法的時(shí)間復(fù)雜度 若G采用鄰接表表示，總計(jì)算時(shí)間為：,3. 向后處理(遞推)策略求解 設(shè) BP(i,j)是一條從源點(diǎn)s到Vi中的結(jié)點(diǎn)j的最小成本路徑，BCOST(i,j)是這條路徑的成本。 1) 向后遞推式 BCOST(k,t)=0 2) 遞推過程 第2段 c(1,j) E COST

11、(2,j) = ,各遞推結(jié)果 第2段 BCOST(2,2) = 9 BCOST(2,3) = 7 BCOST(2,4) = 3 BCOST(2,5) = 2 第3段 BCOST(3,6) = minBCOST(2,2)+4,BCOST(2,3)+2 = 9 BCOST(3,7) = minBCOST(2,2)+2,BCOST(2,3)+7, BCOST(2,5)+11 = 11 BCOST(3,8) = minBCOST(2,4)+11, BCOST(2,5)+8 = 10 第4段 BCOST(4,9) = minBCOST(3,6)+6,BCOST(3,7)+4 = 15 BCOST(4,1

12、0) = minBCOST(3,6)+5,BCOST(3,7)+3, BCOST(3,8)+5 = 14 BCOST(4,11) = minBCOST(3,8)+6 = 16 第5段 BCOST(5,12) = minBCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5 = 16 S到t的最小成本路徑的成本 16, 最小成本路徑的求取 記 BD(i,j)每一COST(i,j)的決策 即，使COST(i-1,p)+c(p,j)取得最小值的p值。 例：BD(3,6) = 3, BD(3,7)= 2 ,BD(3,8) = 5 BD(4,9) = 6, BD(4,10)

13、= 7, BD(4,11) = 8 BD(5,12) = 10 根據(jù)D(5,12)的決策值向前遞推求取最小成本路徑： v4 = BD(5,12)=10 v3 = BD(4,BD(5,12) = 7 v2 = BD(3,BD(4,BD(5,12) = BD(3,7) = 2 故由s到t的最小成本路徑是：1271012,7.1.4多段圖問題的應(yīng)用實(shí)例資源分配問題,【例72】 將n個(gè)資源分配給r個(gè)項(xiàng)目，已知如果把j個(gè)資源分配給第i個(gè)項(xiàng)目，可以收益N(i,j)，0jn，1ir。求總收益最大的資源分配方案。,問題：如何將這n個(gè)資源分配給r個(gè)項(xiàng)目才能使各項(xiàng)目獲得的收益之和達(dá)到最大。 轉(zhuǎn)換成一個(gè)多段圖問題求

14、解。,用r1段圖描述該問題： 段： 1到r之間的每個(gè)段i表示項(xiàng)目i。 結(jié)點(diǎn)： i=1時(shí)，只有一個(gè)結(jié)點(diǎn)源點(diǎn)s =V(1,0) 當(dāng)2ir時(shí)，每段有n+1個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)具有形式 V(i,j)：表示到項(xiàng)目i之前為止，共把j個(gè)資源分配給了 前i-1個(gè)項(xiàng)目，j=0,1,n。 匯點(diǎn)t=V(r+1,n) 邊的一般形式：, 0jkn,1ir 成本： 當(dāng)jk且1ir時(shí)，邊賦予成本 N(i,k-j),表示給項(xiàng)目i分配k-j個(gè)資源所可能獲得的凈利。 當(dāng)jn且i=r時(shí)，此時(shí)的邊為：,該邊賦 予成本：,指向匯點(diǎn)的邊,注，并不是分給的資源越多，得到的凈利就越大,問題的解：資源的最優(yōu)分配方案由一條s到t的最大成本路徑給出改

15、變邊成本的符號(hào)，從而將問題轉(zhuǎn)換成為求取最小成本路徑問題。,7.1.5 關(guān)鍵路徑問題,1.問題描述 求一個(gè)帶權(quán)有向無環(huán)圖中兩結(jié)點(diǎn)間的最長(zhǎng)路徑問題。 關(guān)鍵路徑問題是一個(gè)AOE網(wǎng)問題 幾個(gè)概念： 事件 活動(dòng) 持續(xù)時(shí)間 源點(diǎn) 匯點(diǎn) 最短時(shí)間 最長(zhǎng)路徑 關(guān)鍵路徑 關(guān)鍵活動(dòng),2.最優(yōu)子結(jié)構(gòu)和重疊子問題,(1)事件i的可能最早發(fā)生時(shí)間earliest(i) earliest(0)=0 earliest(j)=maxearliest(i)+w(i,j) a代表的活動(dòng)是關(guān)鍵活動(dòng)。,3.關(guān)鍵路徑算法,基本步驟 （1）對(duì)有向圖G進(jìn)行拓?fù)渑判颍_認(rèn)其是否為有向無環(huán)圖； （2）按拓?fù)浯涡蛴?jì)算earliesti , 0i

16、,計(jì)算latestj-earliesti,并檢查 latest(j)-earliest(i)是否等于 w(i,j)，從而確定關(guān)鍵活動(dòng)。,例7-3 是AOE網(wǎng)絡(luò)的一個(gè)例子，它代表一個(gè)包括11項(xiàng)活動(dòng)和9個(gè)事件的工程，其中，源點(diǎn)0表示整個(gè)工程已經(jīng)開始，匯點(diǎn)8表示整個(gè)工程結(jié)束。 關(guān)鍵路徑問題是一個(gè)帶權(quán)有向無環(huán)圖中源點(diǎn)0到匯點(diǎn)8的最長(zhǎng)路徑問題。即工程所需的最短時(shí)間。,關(guān)鍵路徑為：0,1,4,7,8 長(zhǎng)度為：19,例 求AOE網(wǎng)的關(guān)鍵路徑,關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)。 縮短非關(guān)鍵活動(dòng)都不能縮短整個(gè)工期如a6縮短為1，則整個(gè)工期仍為8。又如a6推遲3天開始，或拖延3天完成（a6=6）均不影響整個(gè)工期。 分

17、析關(guān)鍵路徑的目的是找出影響整個(gè)工期的關(guān)鍵活動(dòng)，縮短關(guān)鍵活動(dòng)的持續(xù)時(shí)間，常可以縮短整個(gè)工期。如a7縮短為1，則整個(gè)工期為7。此時(shí)，再縮短任一關(guān)鍵活動(dòng)均不能縮短整個(gè)工期。即在有多條關(guān)鍵路徑時(shí)，縮短那些在所有關(guān)鍵路徑上的關(guān)鍵活動(dòng)，才能縮短整個(gè)工期。,7.2.1 問題描述,設(shè)G=(V,E)是一個(gè)有n個(gè)結(jié)點(diǎn)的帶權(quán)有向圖，w(i,j)是權(quán)函數(shù)， 每對(duì)結(jié)點(diǎn)間的最短路徑問題是指求圖中任意一對(duì)結(jié)點(diǎn)i和j之間的最短路徑。,7.2 每對(duì)結(jié)點(diǎn)間的最短路徑,分析： 利用單源最短路徑算法求解 計(jì)算n個(gè)結(jié)點(diǎn)的單源最短路徑。 時(shí)間復(fù)雜度：(n3) 利用動(dòng)態(tài)規(guī)劃策略求解 將求解G中每對(duì)結(jié)點(diǎn)之間的最短路徑問題轉(zhuǎn)化成一個(gè)多階段決策

18、過程。 決策什么？ 最優(yōu)性原理對(duì)于該問題是否成立？,7.2.2 動(dòng)態(tài)規(guī)劃法求解,最優(yōu)子結(jié)構(gòu) 設(shè)圖G=(V,E)是帶權(quán)有向圖，(i,j)是從結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑長(zhǎng)度，k是這條路徑上的一個(gè)結(jié)點(diǎn)，(i,k) 和(k,j)分別是從i到k和從k到j(luò)的最短路徑長(zhǎng)度，則必有(i,j)= (i,k)+(k,j)。因?yàn)槿舨蝗?，則(i,j)代表的路徑就不是最短路徑。這表明每對(duì)結(jié)點(diǎn)之間的最短路徑問題的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。,最優(yōu)解的遞推關(guān)系,重疊子問題：為了計(jì)算dkij時(shí)，必須先計(jì)算 dk1ij、dk1ik和dk1ik，dk1的元素被多個(gè)dk的元素的計(jì)算共享。,7.2.3弗洛伊德（Floyd）算法,弗洛伊德

19、(Floyd)算法的基本思想是：令k=0,1,n-1，每次考察一個(gè)結(jié)點(diǎn)k。二維數(shù)組d用于保存各條最短路徑的長(zhǎng)度，其中，dij存放從結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑的長(zhǎng)度。在算法的第k步上應(yīng)作出決策：從i到j(luò)的最短路徑上是否包含結(jié)點(diǎn)k。,【程序72】弗洛伊德(Floyd)算法 template void MGraph:Floyd(T* ,for (k=0;kn;k+) for (i=0;in;i+) for (j=0;jn;j+) if (dik+dkj dij ) dij=dik+dkj; pathij=pathkj; 弗洛伊德算法的時(shí)間復(fù)雜度為O(n3),例 有向圖如圖所示 如何求每對(duì)結(jié)點(diǎn)之間的路徑

20、？,求圖中所有結(jié)點(diǎn)間最短路徑的成本矩陣,注： d(i,j) = 表明G中從i到j(luò)沒有有向路徑,7.2.4 算法正確性,定理71 弗洛伊德算法得到的dij，0i,jn-1是從i到j(luò)的最短路徑。,7.3.1 問題描述,給定n個(gè)矩陣A0,A1,An1， 其中Ai，i=0,n-1的維數(shù)為pipi+1，并且Ai與Ai+1是可乘的。考察這n個(gè)矩陣的連乘積A0A1An1，由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可有許多不同的計(jì)算次序。矩陣連乘問題是確定計(jì)算矩陣連乘積的計(jì)算次序，使得按照這一次序計(jì)算矩陣連乘積，需要的“數(shù)乘”次數(shù)最少。,7.3 矩陣連乘,完全加括號(hào)的矩陣連乘積可遞歸地定義為： 單個(gè)矩陣是完全

21、加括號(hào)的； 矩陣連乘積A是完全加括號(hào)的，則A可表示為兩個(gè)完全加括號(hào)的矩陣連乘積B和C的乘積并加括號(hào)，即A=(BC)。 由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來確定。 若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。,例74 4個(gè)矩陣連乘積ABCD，設(shè)它們的維數(shù)分別為A:5010，B:1040, C:4030, D:305。 總共有五種完全加括號(hào)的方式：,7.3.2 動(dòng)態(tài)規(guī)劃法求解,最優(yōu)子結(jié)構(gòu)（分析最優(yōu)解的結(jié)構(gòu)） 矩陣連乘AiAi+1Aj簡(jiǎn)記為Ai:j，ij

22、。于是矩陣連乘A0A1An-1可記作A0:n-1 。將這一計(jì)算次序在矩陣Ak和Ak+1，0kn-1之間斷開，則其相應(yīng)的完全加括號(hào)形式為（A0A1Ak）（Ak+1Ak+2An1）。可先分別計(jì)算A0:k和Ak+1:n-1，然后將兩個(gè)連乘積再相乘得到A0:n-1。,矩陣連乘A0:n-1的最優(yōu)計(jì)算次序的計(jì)算量等于A0:k和Ak+1:n-1兩者的最優(yōu)計(jì)算次序的計(jì)算量之和，再加上A0:k和Ak+1:n-1相乘的計(jì)算量。如果兩個(gè)矩陣子序列的計(jì)算次序不是最優(yōu)的，則原矩陣的計(jì)算次序也不可能是最優(yōu)的。這就是說，矩陣連乘問題的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。,最優(yōu)解的遞推關(guān)系 先定義一個(gè)二維數(shù)組m，用來保存矩陣連乘時(shí)所需

23、的最少計(jì)算量。,7.3.3矩陣連乘算法,【程序73】矩陣連乘算法 class MatrixChain public: MatrixChain(int mSize,int *q); int MChain(); int LookupChain(); void Traceback(); ,private: void Traceback(int i,int j); int LookupChain(int i, int j); int *p,*m,*s,n; ;,int MatrixChain:MChain() /求A0:n-1的最優(yōu)解值 for (int i=0;in;i+) mii=0;,for (

24、int r=2; r=n;r+) for (int i=0;i=n-r;i+) int j=i+r-1; mij=mi+1j+pi*pi+1*pj+1; sij=i; for (int k=i+1;kj;k+) int t=mik +mk+1j+pi*pk+1*pj+1; if (tmij) mij=t;sij=k; return m0n-1; ,void MatrixChain:Traceback(int i,int j) if(i=j) coutAi;return; if (isij) cout(; Traceback(i,sij);if (isij)cout); if(sij+1j)co

25、ut(; Traceback(sij+1,j);if(sij+1j) cout); void MatrixChain:Traceback() cout(; Traceback(0,n-1);cout); coutendl; ,例75 6個(gè)矩陣連乘積A0A1A2A3A4A5，設(shè)它們的維數(shù)分別為A0:3035，A1:3515 A2:155 A3:510，A4:1020，A5:2025。,S14=2,m11+m24+p1p2p5=0+2500+351520=13000 m14= m12+m34+p1p3p5=2625+1000+35520=7125 m13+m44+p1p4p5=4375+0+351

26、020=11375,7.3.4 備忘錄方法,矩陣連乘的備忘錄方法 備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)已經(jīng)計(jì)算的子問題建立備忘錄，即保存子問題的計(jì)算結(jié)果以備需要時(shí)引用，從而避免了相同子問題的重復(fù)求解。,【程序74】矩陣連乘的備忘錄方法 int MatrixChain:LookupChain(int i, int j) if (mij0) return mij; if(i=j) return 0; int u=LookupChain(i+1,j)+pi*pi+1*pj+1; sij=i; for (int k=i+1;kj; k+) int t=Lookup

27、Chain(i,k)+LookupChain(k+1,j) +pi*pk+1*pj+1; if (tu) u=t; sij=k; mij=u; return u; ,int MatrixChain:LookupChain() return LookupChain(0,n-1); ,（補(bǔ)充）算法的數(shù)學(xué)基礎(chǔ)集合,集合的基本性質(zhì) 一個(gè)集合中的元素排列的順序是無關(guān)緊要的。 冪級(jí) 設(shè)A是一個(gè)集合，則A的所有子集組成的集合稱為A的冪級(jí)。表示為2A，或(A) 例如：設(shè)A=a, b, c，則 假設(shè)集合A中的元素個(gè)數(shù)為n，則(A)的元素個(gè)數(shù)為：,（補(bǔ)充）算法的數(shù)學(xué)基礎(chǔ)組合,從n個(gè)元素中取出r個(gè)，不考慮他們的順序

28、，則稱為從n中取r的組合。,（補(bǔ)充）算法的數(shù)學(xué)基礎(chǔ)排列,排列 設(shè)A=a1,a2,.,an是n個(gè)不同元素的集合，任取A中r個(gè)元素按順序排成一列，稱為從A中取r個(gè)元素的排列。表示為 例如：A=a,b,c,d，r=3，從A中取3個(gè)元素的排列總數(shù)為24。,7.4.1 問題描述,定義7-1：若給定序列X=（x1,x2,xm）,則另一個(gè)序列Z=（z1,z2,zk）為X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列（i1，i2ik）使得對(duì)于所有j=1,k有zj=xij。設(shè)起始下標(biāo)為1。 定義7-2：給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。,7.4 最長(zhǎng)公共子序列,

29、給定兩個(gè)序列X=（x1,x2,xm和Y=(y1,yz2,yn，求它們的最長(zhǎng)公共子序列（longest common subsequeue,LCS）問題。 例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。,1.最優(yōu)子結(jié)構(gòu)（最長(zhǎng)公共子序列的結(jié)構(gòu)）,定理7-2 設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長(zhǎng)公共子序列為Z=z1,z2,zk ，則 (1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列； (2)若xmyn且zkxm，則Z是xm-1和Y的最長(zhǎng)公共子序列； (3)若xmyn且zkyn，則Z

30、是X和yn-1的最長(zhǎng)公共子序列。,由此可見，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。,7.4.2 動(dòng)態(tài)規(guī)劃法求解,2.最優(yōu)解得遞推關(guān)系（子問題的遞歸結(jié)構(gòu)）,由最長(zhǎng)公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列的最長(zhǎng)公共子序列的長(zhǎng)度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)Cij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：,3.計(jì)算最優(yōu)值,由于在所考慮的子問題空間中，總共有(mn)個(gè)不同的子問題，因此，用動(dòng)態(tài)規(guī)劃算

31、法自底向上地計(jì)算最優(yōu)值能提高算法的效率。,【程序7-5】 求LCS的長(zhǎng)度 class LCS public: LCS(int nx, int ny, char *x, char*y);/創(chuàng)建二維數(shù)組c、s和一維數(shù)組a、b，并進(jìn)行初始化 void LCSLength();/求最優(yōu)解值（最長(zhǎng)公共子序列長(zhǎng)度） void CLCS(); /構(gòu)造最優(yōu)解（最長(zhǎng)公共子序列） private: void CLCS(int i, int j); int *c, *s.m, n; char *a, *b; ;,int LCS:LCSLength() for(int i=1; i=cij-1) cij=ci-1j;

32、 sij=2; /由ci-1j得到cij else cij=cij-1; sij=3; /由cij-1得到cij return cmn;/返回最優(yōu)解值 ,【程序7-6】 構(gòu)造最長(zhǎng)公共子序列 void LCS:CLCS(int i, int j) if (i=0|j=0) return; if (sij=1) CLCS(i-1, j-1); coutai; else if (sij=2) CLCS(i-1, j); else CLCS(i, j-1); ,例:,設(shè)有兩個(gè)序列X=（x1,x2,x7）=（a,b,c,b,d,a,b）和Y=(y1,y2,y6）=(b,d,c,a,b,a)，求它們的最長(zhǎng)

33、公共子序列。,4.算法的改進(jìn),在算法LSCLength和CLCS中，可進(jìn)一步將數(shù)組s省去。事實(shí)上，數(shù)組元素cij的值僅由ci-1j-1，ci-1j和cij-1這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素cij，可以不借助于數(shù)組s而僅借助于c本身在時(shí)間內(nèi)確定cij的值是由ci-1j-1，ci-1j和cij-1中哪一個(gè)值所確定的。 如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上，在計(jì)算cij時(shí)，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n)。,7.5.1 問題描述,設(shè)有元素集合 a

34、1,a2,an，其中，a1a2an，p(i) 是在集合中成功查找ai 的概率，1i n，q(i)是待查元素x值滿足 aixai+1的概率,0i n（假定a0= , an+1=+）。 最優(yōu)二叉搜索樹問題是指設(shè)法構(gòu)造一棵具有最小平均搜索時(shí)間的二叉搜索樹。,7.5 最優(yōu)二叉搜索樹,7.5.2動(dòng)態(tài)規(guī)劃法求解,設(shè) c(0,n) 是由元素值集合a1,an所構(gòu)造的最優(yōu)二叉搜索樹的代價(jià)，則,一般地，c(i,j) ,ij 是元素值集合ai+1,aj所構(gòu)造的最優(yōu)二叉搜索樹的代價(jià)，設(shè)r(i,j)=k為該樹的根，要求結(jié)點(diǎn)k滿足,例77 設(shè)n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又設(shè)p(1

35、:4)=(3,3,1,1)和q(0:4)(2,3,1,1,1)。這里p和q都已乘了16。,7.5.3 最優(yōu)二叉搜索樹算法,【程序77】構(gòu)造最優(yōu)二叉搜索樹 int Find(int i,int j,int *r,float*c) float min=INFTY; int k; for (int m=i+1;m=j;m+) if (cim-1+cmj)min) min=cim-1+cmj;k=m; return k; ,void CreateOBST(float* p,float* q, float *c,int *r,float*w,int n) for (int i=0;i=n-1;i+) w

36、ii=qi;cii=0.0;rii=0; wii+1=qi+qi+1+pi+1; cii+1=qi+qi+1+pi+1; rii+1=i+1; wnn=qn;cnn=0.0;rnn=0;,for (int m=2;m=n;m+) for (i=0;i=n-m;i+) int j=i+m; wij=wij-1+pj+qj; int k = Find(i,j,r,c); cij = wij + cik-1 + ckj; rij = k; ,7.6.1 問題描述,問題 已知一個(gè)載重為M的背包和n件物品，物品編號(hào)從0到n-1。第i件物品的重量為 wi，如果將第i種物品裝入背包將獲益pi，這里，wi0，

37、pi0，0in。所謂0/1背包問題是指在物品不能分割，只能整件裝入背包或不裝入的情況下，求一種最佳裝載方案使得總收益最大。,7.6 0/1背包,7.6.2 動(dòng)態(tài)規(guī)劃法求解,最優(yōu)子結(jié)構(gòu) 0/1背包的最優(yōu)解具有最優(yōu)子結(jié)構(gòu)特性。設(shè) (x0, x1, , xn1)，xi0,1是0/1背包的最優(yōu)解，那么，(x1 ,x2, , xn1) 必然是0/1背包子問題的最優(yōu)解：背包載重Mw0 x0，共有n-1件物品，第i件物品的重量為 wi，效益pi，wi0，pi0，1in。,例78 設(shè)有0/1背包問題n=3，（w0,w1,w2）=（2,3,4），（p0,p1,p2）=（1,2,4）和M=6。,遞歸式,7.6.3

38、 0/1背包算法框架,現(xiàn)用Sj表示函數(shù)曲線f(j,X)的全部階躍點(diǎn)的集合，Sj=(Xi,Pi)| 函數(shù)曲線f(j,X)的全部階躍點(diǎn)，-1jn-1，其中S-1=(0,0)。用S1j表示函數(shù)曲線f(j-1,X-wj)+pj的全部階躍點(diǎn)的集合，S1j=(Xj,Pj)| 函數(shù)曲線f(j-1,X-wj)+pj的全部階躍點(diǎn)，0jn-1。,計(jì)算所有Sj和S1j的步驟如下： S-1=(0,0)，函數(shù)f(-1,X)只有一個(gè)階躍點(diǎn)； S1j=(X,P)|(X-wj,P-pj)Sj1，也就是說，由集合Sj-1中的每個(gè)階躍點(diǎn)（X,P），得到集合S1j中的一個(gè)階躍點(diǎn)（X+wj,P+pj）； Sj是合并集合Sj-1S1j

39、，舍棄其中被支配的階躍點(diǎn)和所有XM的階躍點(diǎn)得到。,對(duì)于例78有 S1=(0,0)，S10=(2,1) S0=(0,0),(2,1)，S11=(3,2),(5,3) S1=(0,0),(2,1),(3,2),(5,3)，S12=(4,4),(6,5),(7,6),(9,7) S2=(0,0),(2,1),(3,2),(4,4),(6,5),【程序79】0/1背包算法的粗略描述 void DKP(float *p,float *w,int n, float M, float ,(X1,P1)=Sn2中最后一個(gè)階躍點(diǎn); (X2,P2)=(X+wn1,P+pn1)，其中(X,P)是Sn-1 中 使得

40、X+wn1M的最大的階躍點(diǎn); PmaxP1,P2; If (P2P1) xn1=1; else xn1=0; 回溯確定xn2,xn-3,x0; ,7.6.5 性能分析,在最壞情況下，算法的空間復(fù)雜度是O(2n)。 在最壞情況下，算法的時(shí)間復(fù)雜度是O(2n)。,例7-9 0/1背包問題 n=6,(p0,p1,p2,p3,p4,p5)=(w0,w1,w2,w3,w4,w5)=(100,50,20,10,7,3),M=165 不使用啟發(fā)式方法的序偶集 S0=0 S1=0,100 S2=0,50,100,150 S3=0,20,50,70,100,120,150 S4=0,10,20,30,50,60

41、,70,80,100,110,120,130,150，160 S5=0,7,10,17,20,27,30,37,50,57,60,67,70,77,80,87,100, 107,110,117,120,127,130,137,150,157,160 則，f(5，165)=163 注：因物品的重量和收益取相同值，故每對(duì)序偶(X,P)僅用單一量P表示。,啟發(fā)式規(guī)則求解 分析：將物品0,1,3,5裝入背包，將占用163的重量并產(chǎn)生163的效益。 故，取期望值L163. 按照啟發(fā)式生成規(guī)則，從Si中刪除所有PProfLeft (i)L的序偶，則有 ProfLeft(0)=p0+p1+p2+p3+p4+

42、p5=190 S0=0 =100 ProfLeft(1)=p1+p2+p3+p4+p5=90 S1=100 =150 ProfLeft(2)=p2+p3+p4+p5=40 S2=150 = ProfLeft (3)=p3+p4+p5=20 (w2=20) S3=150 =160 ProfLeft(4)=p4+p5=10 S4=160 = ProfLeft (5)=p5=3 (w4=7) S5=160 ProfLeft(6)=0 f6(165)=160+3 163,7.7.1 問題描述,假定處理一個(gè)作業(yè)需要執(zhí)行若干項(xiàng)不同類型的任務(wù)，每一類任務(wù)只能在某一臺(tái)設(shè)備上執(zhí)行。設(shè)一條流水線上有n個(gè)作業(yè)J=J

43、0,J1,Jn1和m臺(tái)設(shè)備P=P1,P2,Pm。每個(gè)作業(yè)需依次執(zhí)行m個(gè)任務(wù)，其中第j個(gè)任務(wù)只能在第j臺(tái)設(shè)備上執(zhí)行，1jm。設(shè)第i個(gè)作業(yè)的第j項(xiàng)任務(wù)Tji所需時(shí)間為tji，1jm，0in。如何將這nm個(gè)任務(wù)分配給著m臺(tái)設(shè)備，使得這n個(gè)作業(yè)都能順利完成。這就是流水線作業(yè)調(diào)度(flow shop schedule)問題。,7.7 流水作業(yè)調(diào)度,例710 設(shè)有三臺(tái)設(shè)備兩個(gè)作業(yè)，每個(gè)作業(yè)包含三項(xiàng)任務(wù)。完成這些任務(wù)的時(shí)間由矩陣M給定。,作業(yè)i的完成時(shí)間fi(S)是指在調(diào)度方案S下，該作業(yè)的所有任務(wù)都已完成的時(shí)間。 完成時(shí)間F(S)是所有作業(yè)都完成的時(shí)間。 平均流動(dòng)時(shí)間(mean flow time)MFT

44、(S)定義為：,一組給定的作業(yè)的最優(yōu)完成時(shí)間是F(S)的最小值。 OFT表示指非搶先調(diào)度最優(yōu)完成時(shí)間 POFT表示搶先調(diào)度最優(yōu)完成時(shí)間。 OMFT表示非搶先調(diào)度最優(yōu)平均完成時(shí)間， POMFT表示搶先調(diào)度最優(yōu)平均完成時(shí)間。 流水作業(yè)調(diào)度問題（當(dāng)m3時(shí)）是一個(gè)難解的問題，且算法實(shí)現(xiàn)也非常復(fù)雜。 本節(jié)只討論當(dāng)m=2時(shí)獲得OFT的調(diào)度方案的算法，這就是雙機(jī)流水作業(yè)調(diào)度問題。,雙機(jī)流水作業(yè)調(diào)度描述為：設(shè)有n個(gè)作業(yè)的集合0，1，n-1，每個(gè)作業(yè)都有兩項(xiàng)任務(wù)要求在2臺(tái)設(shè)備P1和P2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序總是先在P1上加工，然后在P2上加工。P1和P2加工作業(yè)i所需的時(shí)間分別為ai和bi。流水作業(yè)調(diào)度問題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在設(shè)備P1上開始加工，到最后一個(gè)作業(yè)在設(shè)備P2上加工完成所需的時(shí)間最少。即求使