第3章動態(tài)規(guī)劃2

1、13.2 動態(tài)規(guī)劃算法的基本要素動態(tài)規(guī)劃算法的基本要素 Elements of Dynamic Programming 1 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) Optimal Substructure 2 重疊子問題性質(zhì)重疊子問題性質(zhì) Overlapping Subproblems 21. 最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu) Optimal Substructure 當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。 分析最優(yōu)子結(jié)構(gòu)性質(zhì)時，一般假設(shè)由問題分析最優(yōu)子結(jié)構(gòu)性質(zhì)時，一般假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題不是最優(yōu)的，然后的最優(yōu)

2、解導(dǎo)出的子問題不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可以構(gòu)造出一個再設(shè)法說明在這個假設(shè)下可以構(gòu)造出一個比原問題更優(yōu)解更好的解，從而導(dǎo)出矛盾。比原問題更優(yōu)解更好的解，從而導(dǎo)出矛盾。3.2動態(tài)規(guī)劃算法的基本要素動態(tài)規(guī)劃算法的基本要素32.重疊子問題重疊子問題 Overlapping Subproblems 在用遞歸算法自頂向下解此問題時，每次在用遞歸算法自頂向下解此問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。題被反復(fù)計(jì)算多次。 動態(tài)規(guī)劃算法對每個問題只解一次，而后動態(tài)規(guī)劃算法對每個問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解將其解

3、保存在一個表格中，當(dāng)再次需要解此問題時，用常數(shù)時間查看一下結(jié)果。此問題時，用常數(shù)時間查看一下結(jié)果。 因此，用動態(tài)規(guī)劃算法通常只需要多項(xiàng)式因此，用動態(tài)規(guī)劃算法通常只需要多項(xiàng)式時間。時間。動態(tài)規(guī)劃算法的基本要素動態(tài)規(guī)劃算法的基本要素3.2動態(tài)規(guī)劃算法的基本要素動態(tài)規(guī)劃算法的基本要素43.備忘錄方法備忘錄方法Memoization 用一個表格來保存已解決的子問題的答案，用的用一個表格來保存已解決的子問題的答案，用的時候查表即可。時候查表即可。 采用的遞歸方式是采用的遞歸方式是自頂向下自頂向下，動態(tài)規(guī)劃是，動態(tài)規(guī)劃是自底向自底向上。上。 初始化為每個子問題的記錄存入一個特殊的值，初始化為每個子問題的記

4、錄存入一個特殊的值，表示并未求解。在求解過程中，查看相應(yīng)記錄如表示并未求解。在求解過程中，查看相應(yīng)記錄如果是特殊值，表示未求解，否則只要取出該子問果是特殊值，表示未求解，否則只要取出該子問題的解答即可。題的解答即可。動態(tài)規(guī)劃算法的基本要素動態(tài)規(guī)劃算法的基本要素3.2動態(tài)規(guī)劃算法的基本要素動態(tài)規(guī)劃算法的基本要素5備忘錄方法解矩陣乘備忘錄方法解矩陣乘int MemoizedMatrixChain(int n,int *m,int *s) for(int i=1;i=n;i+) for(int j=i;j0) return mij; if(i=j) return 0; int u=LookupCha

5、in(i,i)+LookupChain(i+1,j) +pi-1*pk*pj; sij=i; for(int k=i+1;kj;k+) int t=LookupChain(i,k) +LookupChain(k+1,j) +pi-1*pk*pj; if(tT( S, b(1) )，設(shè)設(shè) 是作業(yè)集是作業(yè)集S在機(jī)器在機(jī)器M2等待時等待時間間b(1)時的一個最優(yōu)調(diào)度，則時的一個最優(yōu)調(diào)度，則(1),(2), (n)是是N的一個調(diào)度。的一個調(diào)度。 該調(diào)度所需的時間為該調(diào)度所需的時間為a(1) + T( S, b(1) ) ai等待時間等待時間t= t ai + biM1M2t ai流水作業(yè)調(diào)度流水作業(yè)調(diào)

6、度t=aiaiajtbibjtbibjttbibibjbj3.3流水作業(yè)調(diào)度流水作業(yè)調(diào)度19 如果調(diào)換如果調(diào)換i，j的加工順序，則得到另一調(diào)度，它的加工順序，則得到另一調(diào)度，它的加工時間變?yōu)榈募庸r間變?yōu)閖it流水作業(yè)調(diào)度流水作業(yè)調(diào)度考慮對于相同的考慮對于相同的 ai, aj, bi, bj，不同的加工順序?qū)е?，不同的加工順序?qū)е率Ｓ嗳蝿?wù)的等待時間剩余任務(wù)的等待時間tij與與tji的大小關(guān)系。的大小關(guān)系。3.3流水作業(yè)調(diào)度流水作業(yè)調(diào)度20 稱作業(yè)i和j滿足Johnson不等式，如果作業(yè)i和j不滿足Johnson不等式，則交換作業(yè)i和作業(yè)j的加工順序后，他們滿足Johnson不等式。 交換作業(yè)的

7、加工順序后，它需要的加工時間為：),/(),(jijitjiSTaatsT如果作業(yè)如果作業(yè)i和和j滿足滿足 ,maxjjjiijijjiabaataabbt流水作業(yè)調(diào)度流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度流水作業(yè)調(diào)度21如果作業(yè)如果作業(yè)i和和j滿足滿足Johnson不等式不等式流水作業(yè)調(diào)度流水作業(yè)調(diào)度則則3.3流水作業(yè)調(diào)度流水作業(yè)調(diào)度22Johnson法則的調(diào)度法則的調(diào)度 對于流水作業(yè)調(diào)度問題，必存在一個最優(yōu)對于流水作業(yè)調(diào)度問題，必存在一個最優(yōu)調(diào)度調(diào)度，使得，使得(i)和和(i+1)滿足滿足Johnson不等不等式式 minb (i) ,a (i+1)minb (i+1) ,a(i) minb (i

8、) ,a (j)minb (j) ,a(i) ij 流水作業(yè)調(diào)度流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度流水作業(yè)調(diào)度23Johnson算法算法流水作業(yè)調(diào)度流水作業(yè)調(diào)度考慮這樣構(gòu)成的調(diào)考慮這樣構(gòu)成的調(diào)度一定滿足度一定滿足Johnson法則嗎？法則嗎？3.3流水作業(yè)調(diào)度流水作業(yè)調(diào)度24算法描述算法描述流水作業(yè)調(diào)度流水作業(yè)調(diào)度int FlowShop( int n, int* a, int* b, int* c) class Jobtype public: int operator = ( Jobtype a) const return ( key = a.key ); int key; int index;

9、 bool job; ; Jobtype *d = new Jobtype n; for ( int i= 0; i b i ? bi: ai; d i .job = a i = bi; d i .index = I; sort(d, n);int j = 0, k = n - 1;for( int i = 0 ; in; i+) if( di.job) c j+ = di.index; else c k- - = di.index; j = ac0;k = j + bc0;for (int i =1; in ; i+) j+ = aci; k = j k? k+ bci: j + bci;

10、delete d;return k;3.3流水作業(yè)調(diào)度流水作業(yè)調(diào)度255.計(jì)算復(fù)雜性分析 算法的主要計(jì)算時間是排序，因此，最壞情況下算法所需的時間復(fù)雜度為 O（nlogn）流水作業(yè)調(diào)度流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度流水作業(yè)調(diào)度26最優(yōu)化原理最優(yōu)化原理 多階段過程的最優(yōu)決策序列應(yīng)當(dāng)具有性質(zhì)：多階段過程的最優(yōu)決策序列應(yīng)當(dāng)具有性質(zhì)： 無論過程的初始狀態(tài)和初始決策是什么，其無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個最優(yōu)決策序列。態(tài)構(gòu)成一個最優(yōu)決策序列。流水作業(yè)調(diào)度流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度流水作業(yè)調(diào)度27 最優(yōu)決策是

11、否存在依賴于該問題是否最優(yōu)決策是否存在依賴于該問題是否 有最優(yōu)子結(jié)構(gòu)性質(zhì)：有最優(yōu)子結(jié)構(gòu)性質(zhì)：原問題的最優(yōu)解包含了其子問題的最優(yōu)解。原問題的最優(yōu)解包含了其子問題的最優(yōu)解。流水作業(yè)調(diào)度流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度流水作業(yè)調(diào)度28設(shè)計(jì)步驟設(shè)計(jì)步驟 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。 遞歸地定義最優(yōu)值。遞歸地定義最優(yōu)值。 以自底向上的方式計(jì)算出最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。 根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造一個根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。最優(yōu)解。流水作業(yè)調(diào)度流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度流水作業(yè)調(diào)度29Exercises Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIX-CHAIN? Justify your answer. 30E