版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
3.2動(dòng)態(tài)規(guī)劃算法的基本要素
ElementsofDynamicProgramming
1最優(yōu)子結(jié)構(gòu)性質(zhì) OptimalSubstructure
2重疊子問題性質(zhì)OverlappingSubproblems
11.最優(yōu)子結(jié)構(gòu)
OptimalSubstructure
當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時(shí),稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。分析最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí),一般假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題不是最優(yōu)的,然后再設(shè)法說明在這個(gè)假設(shè)下可以構(gòu)造出一個(gè)比原問題更優(yōu)解更好的解,從而導(dǎo)出矛盾。3.2動(dòng)態(tài)規(guī)劃算法的基本要素22.重疊子問題
OverlappingSubproblems
在用遞歸算法自頂向下解此問題時(shí),每次產(chǎn)生的子問題并不總是新問題,有些子問題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法對(duì)每個(gè)問題只解一次,而后將其解保存在一個(gè)表格中,當(dāng)再次需要解此問題時(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è)表格來保存已解決的子問題的答案,用的時(shí)候查表即可。采用的遞歸方式是自頂向下,動(dòng)態(tài)規(guī)劃是自底向上。初始化為每個(gè)子問題的記錄存入一個(gè)特殊的值,表示并未求解。在求解過程中,查看相應(yīng)記錄如果是特殊值,表示未求解,否則只要取出該子問題的解答即可。動(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ī)劃算法的基本要素表示該子問題已經(jīng)求解遞歸求解斷開位置為i時(shí)的計(jì)算量循環(huán)每個(gè)可取斷開位置求計(jì)算量作業(yè):請(qǐng)寫出利用備忘錄方法計(jì)算A[1:4]時(shí)都計(jì)算了哪些子問題?3.2動(dòng)態(tài)規(guī)劃算法的基本要素6動(dòng)態(tài)規(guī)劃算法的基本要素備忘錄采用自頂向下的計(jì)算,將計(jì)算結(jié)果存入矩陣后返回,每個(gè)子問題僅在第一次被調(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è)問題的所有子問題都至少要解一次時(shí),則用動(dòng)態(tài)規(guī)劃算法比備忘錄方法好。當(dāng)子問題空間中的部分子問題可不必求解時(shí),用備忘錄方法則較有利,因?yàn)閺钠淇刂平Y(jié)構(gòu)可以看出,該方法只解哪些確實(shí)需要求解的子問題。動(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)度問題要求確定這n個(gè)作業(yè)的最優(yōu)加工次序,使得從第一個(gè)作業(yè)在機(jī)器M1上開始加工,到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少。問題描述: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ù)的過程。taskitaskj例1:3.3流水作業(yè)調(diào)度作業(yè)積壓M2空閑10記N={1,2,...,n},S為N的子集合。一般情況下,當(dāng)機(jī)器M1開始加工S中的作業(yè)時(shí),機(jī)器M2可能正在加工其它的作業(yè),要等待時(shí)間t后才可用來加工S中的作業(yè)。將這種情況下流水線完成S中的作業(yè)所需的最短時(shí)間記為T(S,t),則流水作業(yè)調(diào)度問題的最優(yōu)值即是
。流水作業(yè)調(diào)度T(N,0)M1M2a1b1M1M2aibit3.3流水作業(yè)調(diào)度111.流水作業(yè)調(diào)度問題具有最優(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)
),說明流水作業(yè)調(diào)度問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度132.遞歸計(jì)算最優(yōu)值由流水作業(yè)調(diào)度問題的最優(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):通過該式可給出流水調(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)要說明的問題如果作業(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)度原問題轉(zhuǎn)化為求滿足Johnson法則的調(diào)度問題,即找到的調(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í)間才能開始在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ū)е率S嗳蝿?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)度問題,必存在一個(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)化原理
多階段過程的最優(yōu)決策序列應(yīng)當(dāng)具有性質(zhì):
無論過程的初始狀態(tài)和初始決策是什么,其余的決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。流水作業(yè)調(diào)度3.3流水作業(yè)調(diào)度26最優(yōu)決策是否存在依賴于該問題是否有最優(yōu)子結(jié)構(gòu)性質(zhì):原問題的最優(yōu)解包含了其子問題的最優(yōu)解。流水作業(yè)調(diào)度
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024屆高考語文一輪復(fù)習(xí)第2章小說閱讀3第二節(jié)分析情節(jié)結(jié)構(gòu)-精構(gòu)情節(jié)講好故事課件
- 預(yù)防青少年犯罪法制教育課
- 16.2《登泰山記》課件 2024-2025學(xué)年統(tǒng)編版高中語文必修上冊(cè)
- 遼寧省葫蘆島市八中2025屆高三(最后沖刺)語文試卷含解析
- 江蘇省無錫市惠山六校聯(lián)考2025屆高三第一次調(diào)研測試語文試卷含解析
- 湖北省荊州市重點(diǎn)中學(xué)2025屆高三適應(yīng)性調(diào)研考試英語試題含解析
- 湖北省仙桃市漢江高級(jí)中學(xué)2025屆高三六校第一次聯(lián)考語文試卷含解析
- 現(xiàn)代學(xué)徒制課題:中國特色學(xué)徒制建設(shè)標(biāo)準(zhǔn)體系研究(附:研究思路模板、可修改技術(shù)路線圖)
- 內(nèi)蒙古阿拉善2025屆高考仿真卷英語試卷含解析
- 貴州省鳳岡縣第二中學(xué)2025屆高考語文考前最后一卷預(yù)測卷含解析
- 設(shè)備單機(jī)試運(yùn)轉(zhuǎn)記錄
- 2020年領(lǐng)導(dǎo)干部個(gè)人有關(guān)事項(xiàng)報(bào)告表
- 人教版小學(xué)數(shù)學(xué)三年級(jí)下冊(cè)《年 月 日》的認(rèn)識(shí)-文檔資料
- 一年級(jí)童謠誦讀計(jì)劃
- 全風(fēng)險(xiǎn)全流程外包概述
- 培養(yǎng)研究生的一點(diǎn)經(jīng)驗(yàn)和體會(huì).PPT
- 變電站電氣工程質(zhì)量監(jiān)理旁站點(diǎn)及旁站監(jiān)理記錄
- 消防產(chǎn)品入場核查清單
- 醫(yī)用護(hù)理墊備案
- 地球的地殼元素豐度列表
- 三月份德育工作講評(píng)2
評(píng)論
0/150
提交評(píng)論