動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)ppt課件(參考版)
2025-05-09 12:09本頁(yè)面
【正文】 由最優(yōu)二叉搜索樹問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可建立計(jì)算 pij的遞歸式如下 記 wi,jpi,j為 m(i,j)，則 m(1,n)=w1,np1,n=p1,n為所求的最優(yōu)值。在這種情況下，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為 O(min{nc,2n})。由此可見，算法計(jì)算跳躍點(diǎn)集 p[i]所花費(fèi)的計(jì)算時(shí)間為 從而，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為 O(2n)。從跳躍點(diǎn)集 p[i]的定義可以看出， p[i]中的跳躍點(diǎn)相應(yīng)于 xi,…,x n的 0/1賦值。由于 q[i+1]=p[i+1]?(wi， vi)，故計(jì)算q[i+1]需要 O(|p[i+1]|)計(jì)算時(shí)間。將受控跳躍點(diǎn) (5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)} q[4]=p[4]?(6， 5)={(6， 5)， (10， 11)} p[3]={(0， 0)， (4， 6)， (9， 10)， (10， 11)} q[3]=p[3]?(2， 3)={(2， 3)， (6， 9)} p[2]={(0， 0)， (2， 3)， (4， 6)， (6， 9)， (9， 10)， (10， 11)} q[2]=p[2]?(2， 6)={(2， 6)， (4， 9)， (6， 12)， (8， 15)} p[1]={(0， 0)， (2， 6)， (4， 9)， (6， 12)， (8， 15)} p[1]的最后的那個(gè)跳躍點(diǎn) (8,15)給出所求的最優(yōu)值為 m(1,c)=15。 q[5]=p[5]?(w4,v4)={(5,4),(9,10)}。因此，q[6]=p[6]?(w5,v5)={(4,6)}。 算法改進(jìn) 44 一個(gè)例子 n=5， c=10， w={2， 2， 6， 5， 4}， v={6， 3， 5， 4， 6}。除受控跳躍點(diǎn)外， p[i+1]?q[i+1]中的其它跳躍點(diǎn)均為 p[i]中的跳躍點(diǎn)。易知， (s,t)?q[i+1]當(dāng)且僅當(dāng) wi?s?c且 (swi,tvi)?p[i+1]。 x (0,0) m(4,x) x (2,1) m(4,x2)+1 x (0,0) (2,1) m(3,x) (3,2) x m(3,x3)+2 (5,3) x (0,0) (2,1) m(2,x) (3,2) (5,3) x m(2,x4)+5 (4,5) (6,6) (7,7) (9,8) x (0, 0) (2, 1) m(1,x) (3,2) (5,3) (4,5) (6,6) (7,7) (9,8) x (0,0) (2,1) m(3,x) x (0,0) (2,1) m(2,x) (3,2) (5,3) 43 ?函數(shù) m(i,j)是由函數(shù) m(i+1,j)與函數(shù) m(i+1,jwi)+vi作 max運(yùn)算得到的。表 p[i]可依計(jì)算 m(i， j)的遞歸式遞歸地由表 p[i+1]計(jì)算，初始時(shí) p[n+1]={(0， 0)}。如圖所示。跳躍點(diǎn)是這一類函數(shù)的描述特征。例如，當(dāng) c2n時(shí)，算法需要 Ω(n2n)計(jì)算時(shí)間。 iiiiwjwjjimvwjimjimjim????????????0),1(}),1(),1(m a x {),(nnnwjwjvjnm???????00),(算法復(fù)雜度分析： 從 m(i， j)的遞歸式容易看出，算法需要 O(nc)計(jì)算時(shí)間。 ??niii xv1m ax???????????nixCxwiniii1},1,0{140 01背包問(wèn)題 設(shè)所給 01背包問(wèn)題的子問(wèn)題 ??nikkk xvm ax???????????nkixjxwknikkk},1,0{的最優(yōu)值為 m(i， j)，即 m(i， j)是背包容量為 j，可選擇物品為 i，i+1， … ， n時(shí) 01背包問(wèn)題的最優(yōu)值。物品 i的重量是 wi，其價(jià)值為 vi，背包的容量為 C。所需的空間為 O(n)。|{},|{ 21 iiii baiNbaiN ????算法復(fù)雜度分析： 算法的主要計(jì)算時(shí)間花在對(duì)作業(yè)集的排序。 },m a x { jjjiijijji abaataabbt ???????},m a x { iijiijijij abaataabbt ???????},m a x {},m a x {},m a x {},m a x {},m a x {},m a x {},m a x {},m a x {jjjiiijijjjiiijiijjijijiijjiabaatabaatabaaabaaabaaabaaabab????????????????????????},m i n {},m i n { )()()()( ijji abab ???? ?38 算法描述 流水作業(yè)調(diào)度問(wèn)題的 Johnson算法 (1)令 (2)將 N1中作業(yè)依 ai的非減序排序；將 N2中作業(yè)依 bi的非增序排序； (3)N1中作業(yè)接 N2中作業(yè)構(gòu)成滿足 Johnson法則的最優(yōu)調(diào)度。對(duì)于流水作業(yè)調(diào)度問(wèn)題，必存在最優(yōu)調(diào)度 ? ，使得作業(yè) ?(i)和 ?(i+1)滿足 Johnson不等式。則由動(dòng)態(tài)規(guī)劃遞歸式可得 : T(S,t)=ai+T(S{i},bi+max{tai,0})=ai+aj+T(S{i,j},tij) 其中， },m a x {}0,m a x {}},0,m a x { m ax {}0,}0,m a x {m a x {iijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaatbbt????????????????????????如果作業(yè) i和 j滿足 min{bi,aj}≥ min{bj,ai}，則稱作業(yè) i和 j滿足 Johnson不等式 。 設(shè) ?是作業(yè)集 S在機(jī)器 M2的等待時(shí)間為 t時(shí)的任一最優(yōu)調(diào)度。這就證明了流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。故 T’?T(S,b?(1))。則 ?(1)， ?’(2)， … ， ?’(n)是 N的一個(gè)調(diào)度，且該調(diào)度所需的時(shí)間為 a?(1)+T(S,b?(1))a?(1)+T’。 證明： 事實(shí)上，由 T的定義知 T’?T(S,b?(1))。其中 T’是在機(jī)器 M2的等待時(shí)間為 b?(1)時(shí)，安排作業(yè)?(2)， … ， ?(n)所需的時(shí)間。流水作業(yè)調(diào)度問(wèn)題的最優(yōu)值為 T(N,0)。在一般情況下，機(jī)器 M1開始加工 S中作業(yè)時(shí)，機(jī)器 M2還在加工其它作業(yè)，要等時(shí)間 t后才可利用。 ?設(shè)全部作業(yè)的集合為 N={1， 2， … ， n}。 分析： ?直觀上，一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器 M1沒(méi)有空閑時(shí)間，且機(jī)器M2的空閑時(shí)間最少。 M1和 M2加工作業(yè) i所需的時(shí)間分別為 ai和 bi。 電路布線 })(,))(,(|{),( jtitN e t stttjiN ???? ??????????)1() ) }1(,1{()1(),1(),1(???jjjNjM N S),())(,( jiNii ??),())(,( jiNii ??),1(),( jiNjiM N S ??),(),1( jiNjiM N S ??(1)當(dāng) i=1時(shí) (2)當(dāng) i1時(shí) ??????)1(1)1(0),1(??jjjS iz e)()(}1)1)(,1(),1(m a x {),1(),(ijijiiS i zejiS i zejiS i zejiS i ze??? ???????????34 流水作業(yè)調(diào)度 n個(gè)作業(yè) {1， 2， … ， n}要在由 2臺(tái)機(jī)器 M1和 M2組成的流水線上完成加工。因此， Size(i,j)≤Size(i1,j)。 若 ，則對(duì)任意 (t,π(t)) ∈ MNS(i,j)有 ti。 則對(duì)任意 (t,π(t)) ∈ MNS(i,j)有ti且 π(t)π(i)。故在這種情況下，N(i,j)=N
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1