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

3.2動(dòng)態(tài)規(guī)劃算法的基本要素

ElementsofDynamicProgramming

1最優(yōu)子結(jié)構(gòu)性質(zhì) OptimalSubstructure

2重疊子問(wèn)題性質(zhì)OverlappingSubproblems

11.最優(yōu)子結(jié)構(gòu)

OptimalSubstructure

當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解時(shí)，稱該問(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)出矛盾。3.2動(dòng)態(tài)規(guī)劃算法的基本要素22.重疊子問(wèn)題

OverlappingSubproblems

在用遞歸算法自頂向下解此問(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)再次需要解此問(wèn)題時(shí)，用常數(shù)時(shí)間查看一下結(jié)果。因此，用動(dòng)態(tài)規(guī)劃算法通常只需要多項(xiàng)式時(shí)間。動(dòng)態(tài)規(guī)劃算法的基本要素3.2動(dòng)態(tài)規(guī)劃算法的基本要素33.備忘錄方法

Memoization

用一個(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.2動(dòng)態(tài)規(guī)劃算法的基本要素4備忘錄方法解矩陣乘intMemoizedMatrixChain(intn,int**m,int**s){for(inti=1;i<=n;i++)for(intj=i;j<=n;j++)m[i][j]=0;returnLookupChain(1,n);}動(dòng)態(tài)規(guī)劃算法的基本要素3.2動(dòng)態(tài)規(guī)劃算法的基本要素5intLookupChain(inti,intj){if(m[i][j]>0)returnm[i][j];if(i==j)return0;intu=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[k]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;returnu;}動(dòng)態(tài)規(guī)劃算法的基本要素表示該子問(wèn)題已經(jīng)求解遞歸求解斷開(kāi)位置為i時(shí)的計(jì)算量循環(huán)每個(gè)可取斷開(kāi)位置求計(jì)算量作業(yè)：請(qǐng)寫(xiě)出利用備忘錄方法計(jì)算A[1:4]時(shí)都計(jì)算了哪些子問(wèn)題?3.2動(dòng)態(tài)規(guī)劃算法的基本要素6動(dòng)態(tài)規(guī)劃算法的基本要素備忘錄采用自頂向下的計(jì)算，將計(jì)算結(jié)果存入矩陣后返回，每個(gè)子問(wèn)題僅在第一次被調(diào)用時(shí)計(jì)算。m[i][j]共有O(n2)個(gè)備忘記錄項(xiàng)，初始化需要O(n2)時(shí)間，每個(gè)記錄項(xiàng)只填入一次，共耗費(fèi)O(n)時(shí)間，所以備忘錄方法耗時(shí)O(n3)。3.2動(dòng)態(tài)規(guī)劃算法的基本要素7當(dāng)一個(gè)問(wèn)題的所有子問(wèn)題都至少要解一次時(shí)，則用動(dòng)態(tài)規(guī)劃算法比備忘錄方法好。當(dāng)子問(wèn)題空間中的部分子問(wèn)題可不必求解時(shí)，用備忘錄方法則較有利，因?yàn)閺钠淇刂平Y(jié)構(gòu)可以看出，該方法只解哪些確實(shí)需要求解的子問(wèn)題。動(dòng)態(tài)規(guī)劃算法的基本要素3.2動(dòng)態(tài)規(guī)劃算法的基本要素83.3流水作業(yè)調(diào)度

SchedulingtoMaximizeProfit

已知n個(gè)作業(yè){1,2,...,n}要在由兩臺(tái)機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi，1≤i≤n。流水作業(yè)調(diào)度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)加工次序，使得從第一個(gè)作業(yè)在機(jī)器M1上開(kāi)始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少。問(wèn)題描述：9aibiajbjM1M2M1M2aiajbjajbibjaibiai+bi+bjaj+ai+bi設(shè)有兩個(gè)任務(wù)i和j，它們?cè)贛1和M2上執(zhí)行的時(shí)間分別為ai,bi和aj,bj，如下圖所示，假設(shè)M1和M2都處于空閑狀態(tài)，考慮按不同順序執(zhí)行兩個(gè)任務(wù)的過(guò)程。taskitaskj例1：3.3流水作業(yè)調(diào)度作業(yè)積壓M2空閑10記N={1,2,...,n}，S為N的子集合。一般情況下，當(dāng)機(jī)器M1開(kāi)始加工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)值即是

。流水作業(yè)調(diào)度T(N,0)M1M2a1b1M1M2aibit3.3流水作業(yè)調(diào)度111.流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)π是n個(gè)流水作業(yè)的一個(gè)最優(yōu)調(diào)度（實(shí)際上是作業(yè)的一個(gè)排序），π(1)，···π(n)表示π中各個(gè)作業(yè)。該最優(yōu)調(diào)度的加工時(shí)間為aπ(1)+T’,其中T’是在機(jī)器M2的等待時(shí)間為bπ(1)時(shí)，安排作業(yè)π(2)，···π(n)所需的時(shí)間。流水作業(yè)調(diào)度證明最優(yōu)子結(jié)構(gòu)性質(zhì)就是證明如果π是最優(yōu)調(diào)度，那么π中除去π(1)，在M2上等待時(shí)間為bπ(1)時(shí)，按照π中順序安排π(2)，···π(n)的順序是最優(yōu)的。3.3流水作業(yè)調(diào)度12

若記S=N-{π(1)}，則T(S,bπ(1))為在M2上等待時(shí)間為bπ(1)時(shí)S的最優(yōu)調(diào)度時(shí)間。證明T’=T(S,bπ(1))證明：由T’定義知，T’≥T(S,bπ(1)

)。

若T’>T(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)

)<aπ(1)+T’。這與π是N的一個(gè)最優(yōu)調(diào)度矛盾，所以T’=T(S,bπ(1)

)，說(shuō)明流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度132.遞歸計(jì)算最優(yōu)值由流水作業(yè)調(diào)度問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知,流水作業(yè)調(diào)度M1M2aibiajbj3.3流水作業(yè)調(diào)度14M1M2aibiajbjtt>ai等待時(shí)間t’=t–ai+biM1M2t<=ai等待時(shí)間t’=0+biajbjaibit上述關(guān)系式可以推廣到一般情形計(jì)算T(S,t)：通過(guò)該式可給出流水調(diào)度的動(dòng)態(tài)規(guī)劃算法，但是其時(shí)間復(fù)雜度將是O(2n)?？刹捎孟率鯦onhson算法。3.3流水作業(yè)調(diào)度153.流水作業(yè)調(diào)度的Johnson法則本節(jié)后面推導(dǎo)要說(shuō)明的問(wèn)題如果作業(yè)i和j滿足min{bi,aj}≥

min{bj,ai}，則稱作業(yè)i和j滿足Johnson不等式。如果作業(yè)i和j不滿足Johnson不等式，則交換作業(yè)i和作業(yè)j的加工順序，之后作業(yè)i和j將滿足Johnson不等式，且不增加加工時(shí)間。流水作業(yè)調(diào)度原問(wèn)題轉(zhuǎn)化為求滿足Johnson法則的調(diào)度問(wèn)題，即找到的調(diào)度順序中任意兩個(gè)相鄰作業(yè)滿足Johnson法則。3.3流水作業(yè)調(diào)度163.流水作業(yè)調(diào)度的Johnson法則設(shè)π是所給n個(gè)流水作業(yè)的一個(gè)最優(yōu)調(diào)度，若在這個(gè)調(diào)度中，安排在最前面的兩個(gè)作業(yè)分別是i和j，即π(1)=i,π(2)=j，則動(dòng)態(tài)規(guī)劃遞歸式可得：tij為i和j在M1上結(jié)束后，需要等待多少時(shí)間才能開(kāi)始在M2上加工。流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度17t>ai流水作業(yè)調(diào)度t<=aiaiajtbibjtbibjttbibibjbj3.3流水作業(yè)調(diào)度18

如果調(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)系。3.3流水作業(yè)調(diào)度19稱作業(yè)i和j滿足Johnson不等式，如果作業(yè)i和j不滿足Johnson不等式，則交換作業(yè)i和作業(yè)j的加工順序后，他們滿足Johnson不等式。交換作業(yè)的加工順序后，它需要的加工時(shí)間為：如果作業(yè)i和j滿足

流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度20如果作業(yè)i和j滿足Johnson不等式流水作業(yè)調(diào)度則3.3流水作業(yè)調(diào)度21Johnson法則的調(diào)度對(duì)于流水作業(yè)調(diào)度問(wèn)題，必存在一個(gè)最優(yōu)調(diào)度π，使得π(i)和π(i+1)滿足Johnson不等式min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}min{bπ(i),aπ(j)}≥min{bπ(j),aπ(i)}i<j

流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度22Johnson算法流水作業(yè)調(diào)度考慮這樣構(gòu)成的調(diào)度一定滿足Johnson法則嗎？3.3流水作業(yè)調(diào)度23算法描述流水作業(yè)調(diào)度intFlowShop(intn,int*a,int*b,int*c){classJobtype{public:intoperator<=(Jobtypea)const{return(key<=a.key);}intkey;intindex;booljob;};Jobtype*d=newJobtype[n];for(inti=0;i<n;i++){d[i].key=a[i]>b[i]?b[i]:a[i];d[i].job=a[i]<=b[i];d[i].index=I;}sort(d,n);intj=0,k=n-1;for(inti=0;i<n;i++){if(d[i].job)c[j++]=d[i].index;elsec[k--]=d[i].index;}j=a[c[0]];k=j+b[c[0]];for(inti=1;i<n;i++){j+=a[c[i]];k=j<k?k+b[c[i]]:j+b[c[i]];}deleted;returnk;}3.3流水作業(yè)調(diào)度245.計(jì)算復(fù)雜性分析算法的主要計(jì)算時(shí)間是排序，因此，最壞情況下算法所需的時(shí)間復(fù)雜度為O（nlogn）流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度25最優(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)度3.3流水作業(yè)調(diào)度26最優(yōu)決策是否存在依賴于該問(wèn)題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)：原問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解。流水作業(yè)調(diào)度