章動(dòng)態(tài)規(guī)劃課件

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

2、解此問(wèn)題時(shí)，用常數(shù)時(shí)間查看一下結(jié)果。因此，用動(dòng)態(tài)規(guī)劃算法通常只需要多項(xiàng)式時(shí)間。動(dòng)態(tài)規(guī)劃算法的基本要素2.重疊子問(wèn)題在用遞歸算法自頂向下解此問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)3.備忘錄方法用一個(gè)表格來(lái)保存已解決的子問(wèn)題的答案，用的時(shí)候查表即可。采用的遞歸方式是自頂向下，動(dòng)態(tài)規(guī)劃是自低向上初始化為每個(gè)子問(wèn)題的記錄存入一個(gè)特殊的值，表示并未求解。在求解過(guò)程中，查看相應(yīng)記錄如果是特殊值，表示未求解，否則只要取出該子問(wèn)題的解答即可。動(dòng)態(tài)規(guī)劃算法的基本要素3.備忘錄方法用一個(gè)表格來(lái)保存已解決的子問(wèn)題的答案，用的時(shí)候備忘錄方法解矩陣乘int MemoizedMatrixChain(int n,int *m,int *s

3、) for(int i=1;i=n;i+) for(int j=i;j0) return mij; if(i=j) return 0; int u=LookupChain(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è) 是作業(yè)集S在機(jī)器M2等待時(shí)間b(1)時(shí)的一個(gè)最優(yōu)調(diào)度，則(1),(2), (n)是N的一個(gè)調(diào)度。 該調(diào)度所需的時(shí)間為a(1) + T( S, b(1

4、) ) ai等待時(shí)間t= t ai + biM1M2t aiM1M2t ai流水作業(yè)調(diào)度t=aiaiajtbibjtbibjttbibibjbjt ai + bi ajtij = t ai + bi -aj+ bjbiajtij = bi ai + bjbj+maxbi+(t-ai)-aj,0bj+ maxbi-aj,0tai流水作業(yè)調(diào)度t=aiaiajtbibjtbibjt 如果調(diào)換i，j的加工順序，則得到另一調(diào)度，它的加工時(shí)間變?yōu)榱魉鳂I(yè)調(diào)度考慮對(duì)于相同的 ai, aj, bi, bj，不同的加工順序?qū)е率Ｓ嗳蝿?wù)的等待時(shí)間tij與tji的大小關(guān)系 如果調(diào)換i，j的加工順序，則得到另一調(diào)度，

5、它的加工時(shí)間稱(chēng)作業(yè)i和j滿(mǎn)足Johnson不等式，如果作業(yè)i和j不滿(mǎn)足Johnson不等式，則交換作業(yè)i和作業(yè)j的加工順序后，他們滿(mǎn)足Johnson不等式交換作業(yè)的加工順序后，它需要的加工時(shí)間為如果作業(yè)i和j滿(mǎn)足 流水作業(yè)調(diào)度稱(chēng)作業(yè)i和j滿(mǎn)足Johnson不等式，如果作業(yè)i和j不滿(mǎn)足J如果作業(yè)i和j滿(mǎn)足Johnson不等式流水作業(yè)調(diào)度則如果作業(yè)i和j滿(mǎn)足Johnson不等式流水作業(yè)調(diào)度則Johnson法則的調(diào)度對(duì)于流水作業(yè)調(diào)度問(wèn)題，必存在一個(gè)最優(yōu)調(diào)度，使得(i)和(i+1)滿(mǎn)足Johnson不等式 minb (i) ,a (i+1)minb (i+1) ,a(i) minb (i) ,a (j

6、)minb (j) ,a(i) ij 流水作業(yè)調(diào)度Johnson法則的調(diào)度對(duì)于流水作業(yè)調(diào)度問(wèn)題，必存在一個(gè)最優(yōu)Johnson算法流水作業(yè)調(diào)度考慮這樣構(gòu)成的調(diào)度一定滿(mǎn)足Johnson法則嗎Johnson算法流水作業(yè)調(diào)度考慮這樣構(gòu)成的調(diào)度一定滿(mǎn)足Jo算法描述流水作業(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; bool job; ; Jobtype *d =

7、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; delete d;return k;保存最后的調(diào)用順

8、序ai和bi中較小者該任務(wù)的下標(biāo)若ai=bi,則job為true算法描述流水作業(yè)調(diào)度int FlowShop( int n5.計(jì)算復(fù)雜性分析算法的主要計(jì)算時(shí)間是排序，因此，最壞情況下算法所需的時(shí)間復(fù)雜度為 O（nlogn）流水作業(yè)調(diào)度5.計(jì)算復(fù)雜性分析算法的主要計(jì)算時(shí)間是排序，因此，最壞情況下最優(yōu)化原理 多階段過(guò)程的最優(yōu)決策序列應(yīng)當(dāng)具有性質(zhì)： 無(wú)論過(guò)程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。流水作業(yè)調(diào)度最優(yōu)化原理 多階段過(guò)程的最優(yōu)決策序列應(yīng)當(dāng)具有性質(zhì)：流水作業(yè)最優(yōu)決策是否存在依賴(lài)于該問(wèn)題是否 有最優(yōu)子結(jié)構(gòu)性質(zhì)：原問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解。流水作業(yè)調(diào)度最優(yōu)決策是否存在依賴(lài)于該問(wèn)題是否