1、教學(xué)目標(biāo),理解動態(tài)規(guī)劃的思想 掌握動態(tài)規(guī)劃的基本要素 掌握動態(tài)規(guī)劃的設(shè)計步驟 通過實例學(xué)習(xí)，掌握動態(tài)規(guī)劃設(shè)計的策略,學(xué)習(xí)動態(tài)規(guī)劃的意義,動態(tài)規(guī)劃問世以來，在經(jīng)濟管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用，例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解，因此研究該算法具有很強的實際意義。 動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題，

2、,動態(tài)規(guī)劃的基本思想,基本思想 適合采用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的各個子問題往往不是相互獨立的。在求解過程中，將已解決的子問題的解進行保存，在需要時可以輕松找出。這樣就避免了大量的無意義的重復(fù)計算，從而降低算法的時間復(fù)雜性。如何對已解決的子問題的解進行保存呢？通常采用表的形式，即在實際求解過程中，一旦某個子問題被計算過，不管該問題以后是否用得到，都將其計算結(jié)果填入該表，需要的時候就從表中找出該子問題的解，具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。,動態(tài)規(guī)劃的解題步驟,（1）分析最優(yōu)解的性質(zhì)，刻畫最優(yōu)解的結(jié)構(gòu)特征考察是否適合采用動態(tài)規(guī)劃法。 （2）遞歸定義最優(yōu)值（即建立遞歸式

3、或動態(tài)規(guī)劃方程）。 （3）以自底向上的方式計算出最優(yōu)值，并記錄相關(guān)信息。 （4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造出最優(yōu)解。,動態(tài)規(guī)劃的基本要素,最優(yōu)子結(jié)構(gòu)性質(zhì) 子問題重疊性質(zhì) 遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題出現(xiàn)多次，這種性質(zhì)稱為子問題的重疊性質(zhì)。 在應(yīng)用動態(tài)規(guī)劃時，對于重復(fù)出現(xiàn)的子問題，只需在第一次遇到時就加以解決，并把已解決的各個子問題的解儲存在表中，便于以后遇到時直接引用，從而不必重新求解，可大大提高解題的效率。 自底向上的求解方式,實例,矩陣連乘 裝配線調(diào)度 最長公共子序列 最優(yōu)二叉搜索樹 背包問題,矩陣連乘,給定n個矩陣A1,A2,A3,An，其中Ai與

4、Ai+1(i=1,2,3, ,n-1)是可乘的。用加括號的方法表示矩陣連乘的次序，不同加括號的方法所對應(yīng)的計算次序是不同的。 矩陣的乘法滿足結(jié)合律,無論怎樣加括號結(jié)果相同 矩陣鏈,五種不同方式加全部括號,兩個矩陣相乘的代價,A1 10*100 A2 100*5 A3 5*50,建立最優(yōu)值的遞歸關(guān)系式,AiAi+1Aj矩陣連乘，其中矩陣Am的行數(shù)為pm，列數(shù)為qm(m=i,i+1,j)且相鄰矩陣是可乘的(即qm=pm+1)。設(shè)它們的最佳計算次序所對應(yīng)的乘法次數(shù)為mij，則AiAi+1Ak的最佳計算次序?qū)?yīng)的乘法次數(shù)為mik，Ak+1Ak+2Aj的最佳計算次序?qū)?yīng)的乘法次數(shù)為mk+1j。 當(dāng)i=j

5、時，只有一個矩陣,故mii=0； 當(dāng)ij時，將n個矩陣的行數(shù)和列數(shù)存儲在數(shù)組P0:n,則上述遞歸式可改寫為：,算法設(shè)計,步驟1：確定合適的數(shù)據(jù)結(jié)構(gòu)。采用數(shù)組m來存放各個子問題的最優(yōu)值，數(shù)組s來存放各個子問題的最優(yōu)決策; 步驟2：初始化。令mii=0，sii0，其中i=1,2,n； 步驟3：循環(huán)階段。 步驟3-1：按照遞歸關(guān)系式計算2個矩陣AiAi+1相乘時的最優(yōu)值并將其存入mii+1，同時將最優(yōu)決策記入sii+1，i=1,2,n-1； 步驟3-2：按照遞歸關(guān)系式計算3個矩陣AiAi+1Ai+2相乘時的最優(yōu)值并將其存入mii+2，同時將最優(yōu)決策記入sii+2，i=1,2,n-2； 依此類推，直到

6、 步驟3-(n-1)：按照遞歸關(guān)系式計算n個矩陣A1A2An相乘時的最優(yōu)值并將其存入m1n，同時將最優(yōu)決策記入s1n。 至此，m1n即為原問題的最優(yōu)值。 步驟4：根據(jù)數(shù)組s記錄的最優(yōu)決策信息來構(gòu)造最優(yōu)解。 步驟4-1：遞歸構(gòu)造A1As1n的最優(yōu)解，直到包含一個矩陣結(jié)束； 步驟4-2：遞歸構(gòu)造As1n+1An的最優(yōu)解，直到包含一個矩陣結(jié)束； 步驟4-3：將步驟4-1和步驟4-2遞歸的結(jié)果加括號。,構(gòu)造實例,求矩陣A1（32）、A2（25）、A3（510）、A4（102）和A5（23）連乘的最佳計算次序。,表4-6 實例最優(yōu)值mij 表4-7 實例最優(yōu)決策sij,遞歸構(gòu)造最優(yōu)解,算法分析,語句in

7、t t=mik+mk+1j+pi-1*pk*pj; 為算法MatrixChain的基本語句，最壞情況下該語句的執(zhí)行次數(shù)為O(n3)，故該算法的最壞時間復(fù)雜性為O(n3)。 構(gòu)造最優(yōu)解的Traceback算法的時間主要取決于遞歸。最壞情況下時間復(fù)雜性的遞歸式為： 解此遞歸式得T(n)=O(n)。,最長公共子序列問題,基本概念 （1）子序列 給定序列 X=x1, x2, , xn、Z=z1, z2, , zk，若Z是X的子序列，當(dāng)且僅當(dāng)存在一個嚴(yán)格遞增的下標(biāo)序列 i1, i2, , ik，對j1, 2, , k有zj=x。 （2）公共子序列 給定序列X和Y，序列Z是X的子序列，也是Y的子序列，則稱

8、Z是X和Y的公共子序列。 （3）最長公共子序列 包含元素最多的公共子序列即為最長公共子序列。,建立最優(yōu)值的遞歸關(guān)系式,設(shè)cij表示序列Xi和Yj的最長公共子序列的長度。則：,算法設(shè)計,步驟1：確定合適的數(shù)據(jù)結(jié)構(gòu)。采用數(shù)組c來存放各個子問題的最優(yōu)值，數(shù)組b來存放各個子問題最優(yōu)值的來源。數(shù)組x1:m和y1:n分別存放X序列和Y序列； 步驟2：初始化。令ci00，c0j=0，其中0im，0jn； 步驟3：循環(huán)階段。根據(jù)遞歸關(guān)系式，確定序列Xi和Y的最長公共子序列長度； 步驟3-1：i=1時，求出c1j，同時記錄b1j，1jn； 步驟3-2：i=2時，求出c2j，同時記錄b2j，1jn； 依此類推，直

9、到 步驟3-m：i=m時，求出cmj，同時記錄bmj，1jn。此時，cmn便是序列X和Y的最長公共子序列長度； 步驟4：根據(jù)二維數(shù)組b記錄的相關(guān)信息以自底向上的方式來構(gòu)造最優(yōu)解； 步驟4-1：初始時，i=m，j=n； 步驟4-2：如果bij=1，則輸出xi，同時遞推到bi-1j-1; 如果bij=2，則遞推到bij-1; 如果bij=3，則遞推到bi-1j； 重復(fù)執(zhí)行步驟4-2，直到i=0或j=0，此時就可得到序列X和Y的最長公共子序列。,實例構(gòu)造,【例】給定序列X=A, B, C, B, D, A, B和Y=B, D, C, A, B, A，求它們的最長公共子序列。 （1）m=7，n=6，將

10、停止條件填入數(shù)組c中，即ci00，c0j=0，其中0im，0jn。 （2）當(dāng)i=1時，X1=A，最后一個字符為A；Yj的規(guī)模從1逐步放大到6，其最后一個字符分別為B、D、C、A、B、A； 依此類推，直到i=7。,從i=7，j=6處向前遞推 ，找到X和Y的最長公共子序列為B,C,B,A,加工順序問題,問題描述 設(shè)有n個工件需要在機器Ml和M2上加工，每個工件的加工順序都是先在Ml上加工，然后在M2上加工。t1j，t2j分別表示工件j在M1，M2上所需的加工時間(j=1,2,n)。問應(yīng)如何在兩機器上安排生產(chǎn)，使得第一個工件從在M1上加工開始到最后一個工件在M2上加工完所需的總加工時間最短？,最優(yōu)子

11、結(jié)構(gòu)性質(zhì)分析,將n個工件的集合看作N=1,2,n，設(shè)P是給定n個工件的一個最優(yōu)加工順序方案，P(i)是該調(diào)度方案的第i個要調(diào)度的工件(i=1,2,n)。 從集合S中的第一個工件開始在機器M1上加工到最后一個工件在機器M2上加工結(jié)束時所耗的時間為T(S，t)。設(shè)集合S的最優(yōu)加工順序中第一個要加工的工件為i，那么，經(jīng)過的時間，進入的狀態(tài)為第一臺機器M1開始加工集合S-i中的工件時，第二臺機器M2需要時間才能空閑下來，這種情況下機器M2加工完S-i中的工件所需的時間為T(S-i，t)，其中，即t=t2i+maxt-t1i，0，則,T(S，t)= t1i +T(S-i，t2i +maxt- t1i，0

12、) （4-1） 從式（4-1）可以看出，如果T(S，t)是最小的，那么肯定包含T(S-i, t2i +maxt- t1i，0)也是最小的。整體最優(yōu)一定包含子問題最優(yōu)。,建立最優(yōu)值的遞歸關(guān)系式,設(shè)T(S，t)表示從集合S中的第一個工件開始在機器M1上加工到最后一個工件在機器M2上加工結(jié)束時所耗的最短時間，則： 當(dāng)S為空集時，耗時為M2閑下來所需要的時間，即T(S，t)=t； 當(dāng)S不為空集時，,Johnson-Bellmans Rule,如果加工工件i和j滿足min t1j，t2i大于等于min t1i，t2j不等式，稱加工工件i和j滿足Johnson Bellmans Rule。設(shè)最優(yōu)加工順序為

13、P，則P的任意相鄰的兩個加工工件P(i)和P(i+1)滿足 進一步可以證明，最優(yōu)加工順序的第i個和第j個要加工的工件，如果ij，則 即：滿足Johnson Bellmans Rule的加工順序方案為最優(yōu)方案。,算法設(shè)計,步驟1：令N1=i|t1it2i,N2=i|t1it2i； 步驟2：將N1中工件按t1i非減序排序；將N2中工件按t2i非增序排序； 步驟3：N1中工件接N2中工件，即N1N2就是所求的滿足Johnson Bellmans Rule的最優(yōu)加工順序,算法分析,顯然，F(xiàn)lowShop算法的時間復(fù)雜性取決于Sort函數(shù)的執(zhí)行時間，由于Sort函數(shù)的執(zhí)行時間為O(nlogn)，因此Fl

14、owShop算法的時間復(fù)雜性為O(nlogn)。,0-1背包問題,問題描述 0-1背包問題可描述為：n個物品和1個背包。對物品i，其價值為vi，重量為wi，背包的容量為W。如何選取物品裝入背包，使背包中所裝入的物品的總價值最大？ 約束條件： （4-7） 目標(biāo)函數(shù)： （4-8） 于是，問題歸結(jié)為尋找一個滿足約束條件（4-7），并使目標(biāo)函數(shù)（4-8）達(dá)到最大的解向量X=(x1, x2, xn)。,最優(yōu)子結(jié)構(gòu)性質(zhì)分析,假設(shè)（x1, x2, xn)是所給0-1背包問題的一個最優(yōu)解，則（x2, xn）是下面相應(yīng)子問題的一個最優(yōu)解： 約束條件： 目標(biāo)函數(shù)：,運用反證法來證明,建立最優(yōu)值的遞歸關(guān)系式,令Ci

15、j= C0j=Ci0=0 （4-10),（4-11),算法設(shè)計求裝入背包的最大價值,步驟1：設(shè)計算法所需的數(shù)據(jù)結(jié)構(gòu)。采用數(shù)組wn來存放n個物品的重量；數(shù)組vn來存放n個物品的價值，背包容量為W，數(shù)組Cn+1W+1來存放每一次迭代的執(zhí)行結(jié)果；數(shù)組xn用來存儲所裝入背包的物品狀態(tài)； 步驟2：初始化。按式(4-10)初始化數(shù)組C； 步驟3：循環(huán)階段。按式（4-11）確定前i個物品能夠裝入背包的情況下得到的最優(yōu)值； 步驟3-1：i=1時，求出C1j，1jW； 步驟3-2：i=2時，求出C2j，1jW； 依此類推，直到 步驟3-n：i=n時，求出CnW。此時，CnW便是最優(yōu)值；,算法設(shè)計確定裝入背包的具

16、體物品,從CnW的值向前推，如果CnW Cn-1W，表明第n個物品被裝入背包，則xn=1，前n-1個物品被裝入容量為W-wn的背包中；否則，第n個物品沒有被裝入背包，則xn=0，前n-1個物品被裝入容量為W的背包中。依此類推，直到確定第1個物品是否被裝入背包中為止。由此，得到下面關(guān)系式： （4-12） 按照式（4-12），從CnW的值向前倒推，即j初始為W，i初始為n，即可確定裝入背包的具體物品。,構(gòu)造實例,【例4-8】有5個物品，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6。背包容量為10，物品不可分割，求裝入背包的物品和獲得的最大價值。 行i表示物品，列j表示背包容量，表中

17、數(shù)據(jù)表示Cij,確定裝入背包的具體物品,從CnW的值根據(jù)式（4-12）向前推，最終可求出裝入背包的具體物品，即問題的最優(yōu)解。 初始時，j=W，i=5。 如果Cij=Ci-1j，說明第i個物品沒有被裝入背包，則xi =0； 如果CijCi-1j，說明第i個物品被裝入背包，則xi =1，j=j-wi。 由于CnW=C510=15C410=14，說明物品5被裝入了背包，因此x5=1，且更新j=j-w5=10-4=6。由于C4j=C46=9=C36，說明物品4沒有被裝入背包，因此x4 =0；由于C3j=C36=9=C26=9，說明物品3沒有被裝入背包，因此x3=0。由于C2j=C26=9C16=6，說

18、明物品2被裝入了背包，因此x2=1，且更新j=j-w2=6-2=4。由于C1j=C14=6C04=0，說明物品1被裝入了背包，因此x1=1，且更新j=j-w1=4-2=2。最終可求得裝入背包的物品的最優(yōu)解X=(x1, x2, xn)=(1,1,0,0,1)。,算法分析,在算法KnapSack中，第3個循環(huán)是兩層嵌套的for循環(huán)，為此，可選定語句if(j2n時，算法需要O(n2n)的計算時間。因此，在這里設(shè)計了對算法KnapSack的改進方法，采用該方法可克服這兩大缺點。,改進算法,改進思路 由Cij的遞歸式（4-11）容易證明：在一般情況下，對每一個確定的i(1in)，函數(shù)Cij是關(guān)于變量j的

19、階梯狀單調(diào)不減函數(shù)（事實上，計算Cij的遞歸式在變量j是連續(xù)變量，即為實數(shù)時仍成立）。跳躍點是這一類函數(shù)的描述特征。在一般情況下，函數(shù)Cij由其全部跳躍點唯一確定。,改進步驟,（a）對每一個確定的i，用一個表pi來存儲函數(shù)Cij的全部跳躍點。對每一個確定的實數(shù)j，可以通過查找pi來確定函數(shù)Cij的值。pi中的全部跳躍點(j，Cij)按j升序排列。由于函數(shù)Cij是關(guān)于j的階梯狀單調(diào)不減函數(shù)，故pi中全部跳躍點的Cij值也是遞增排列的。 （b）pi可通過計算pi-1得到。 （c）清除受控點。 （d）由此可得，在遞歸地由pi-1計算pi時，可先由pi-1計算出qi-1，然后合并pi-1和qi-1，并

20、清除其中的受控跳躍點得到pi。 改進后算法的計算時間復(fù)雜性為O(minnW，2n ),最優(yōu)二叉查找樹,定義 最優(yōu)二叉查找樹是在所有表示有序序列S的二叉查找樹中，具有最小平均比較次數(shù)的二叉查找樹。 注意：在查找概率不等的情況下，最優(yōu)二叉樹并不一定是高度最小的二叉查找樹。,最優(yōu)子結(jié)構(gòu)性質(zhì)分析,將由實結(jié)點s1,s2,sn和虛結(jié)點e0,e1, ,en構(gòu)成的二叉查找樹記為T(1，n)。設(shè)定元素sk作為該樹的根結(jié)點，1kn。則二叉查找樹T(1，n)的左子樹由實結(jié)點s1,sk-1和虛結(jié)點e0,ek-1組成，記為T(1，k-1)，而右子樹由實結(jié)點sk+1,sn和虛結(jié)點ek,en組成，記為T(k+1，n)。 如

21、果T(1，n)是最優(yōu)二叉查找樹，則左子樹T(1，k-1)和右子樹T(k+1，n)也是最優(yōu)二叉查找樹。如若不然，假設(shè)T (k+1，n)是比T(k+1，n)更優(yōu)的二叉查找樹，則T (k+1，n)的平均比較次數(shù)小于T(k+1，n)的平均比較次數(shù)，從而由T(1，k-1)、sk和T (k+1，n)構(gòu)成的二叉查找樹T (1，n)的平均比較次數(shù)小于T(1，n)的平均比較次數(shù)，這與T(1，n)是最優(yōu)二叉樹的前提相矛盾。因此，最優(yōu)二叉查找樹具有最優(yōu)子結(jié)構(gòu)性質(zhì)得證。,建立最優(yōu)值的遞歸關(guān)系式,(4-21) 其中 （4-22） 初始時，C(i，i-1)=0; wi(i-1)=qi-1 ，其中1in。 (4-23) 式

22、（4-21）和（4-23）即為建立的最優(yōu)值遞歸定義式。,算法設(shè)計,步驟1：設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)。設(shè)有序序列S=s1,sn，數(shù)組sn存儲序列S中的元素；數(shù)組pn存儲序列S中相應(yīng)元素的查找概率；二維數(shù)組Cn+1n+1，其中Cij表示二叉查找樹T(i，j)的平均比較次數(shù)；二維數(shù)組Rn+1n+1，其中Rij表示二叉查找樹T(i，j)中作為根結(jié)點的元素在序列S中的位置。數(shù)組qn存儲虛結(jié)點e0,e1,en的查找概率。為了提高效率，不是每次計算C(i，j)時都計算wij的值，而是把這些值存儲在二維數(shù)組Wij中； 步驟2：初始化。設(shè)置Cii-1=0；Wii-1=qi-1； 步驟3：循環(huán)階段。采用自底向上的方式逐步構(gòu)造最優(yōu)二叉查找樹； 步驟3-1：字符集規(guī)模為1的時候，即Sij=si，i=1,2, ,n且j=i，顯然這種規(guī)模的子問題有n個，即首先要構(gòu)造出n棵最優(yōu)二叉查找樹T(1，1)，T(2，2),T(n，n)。依據(jù)公式(4-20)(4-22)，很容易求得Wii和Cii。同時，對于所構(gòu)造的n棵最優(yōu)二叉查找樹，它們的根分別記為：R11=1，R22=2