第3章動(dòng)態(tài)規(guī)劃-預(yù)覽頁(yè)
【正文】 == 2) lcs(i1,j,x,b)。對(duì)于給定的數(shù)組元素 c[i][j]，可以不借助于數(shù)組 b而僅借助于 c本身在時(shí)間內(nèi)確定 c[i][j]的值是由 c[i1][j1]， c[i1][j]和 c[i][j1]中哪一個(gè)值所確定的。進(jìn)一步的分析還可將空間需求減至 O(min(m,n))。 ?多邊形的三角剖分 是將多邊形分割成互不相交的三角形的弦的集合 T。例如，完全加括號(hào)的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應(yīng)的語(yǔ)法樹(shù)如圖 (a)所示。三角剖分中的一條弦 vivj， ij，對(duì)應(yīng)于矩陣連乘積A[i+1:j]。因?yàn)槿粲?{v0,v1,…,v k}或{vk,vk+1,…,v n}的更小權(quán)的三角剖分將導(dǎo)致 T不是最優(yōu)三角剖分的矛盾。 ?t[i][j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。由此， t[i][j]可遞歸地定義為： ??????????? ??? jijivvvwjktkitjit jkijki)}(]][1[]][[{m i n0]][[127 多邊形游戲 多邊形游戲是一個(gè)單人玩的游戲，開(kāi)始時(shí)有一個(gè)由 n個(gè)頂點(diǎn)構(gòu)成的多邊形。 隨后 n1步按以下方式操作： (1)選擇一條邊 E以及由 E連接著的 2個(gè)頂點(diǎn) V1和 V2； (2)用一個(gè)新的頂點(diǎn)取代邊 E以及由 E連接著的 2個(gè)頂點(diǎn) V1和 V2。 問(wèn)題 :對(duì)于給定的多邊形，計(jì)算最高得分。 m2是p(i+s， js)的任意一種合并方式得到的值，而 c和 d分別是在所有可能的合并中得到的最小值和最大值。*39。設(shè) 則第 i個(gè)象素段 Si為 設(shè) ，則 hi?b[i]?8。 圖像壓縮問(wèn)題要求確定象素序列 {p1,p2,… ,pn}的最優(yōu)分段，使得依此分段所需的存儲(chǔ)空間最少。即圖像壓縮問(wèn)題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。 31 電路布線 在一塊電路板的上、下 2端分別有 n個(gè)接線柱。對(duì)于任何 1≤ij≤n，第 i條連線和第 j條連線相交的充分且必要的條件是 π(i)π(j)。 N(i,j)的最大不相交子集為 MNS(i,j)。故在這種情況下，N(i,j)=N(i1,j)，從而 Size(i,j)=Size(i1,j)。 若 ，則對(duì)任意 (t,π(t)) ∈ MNS(i,j)有 ti。 電路布線 })(,))(,(|{),( 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??? ???????????33 流水作業(yè)調(diào)度 n個(gè)作業(yè) {1， 2， … ， n}要在由 2臺(tái)機(jī)器 M1和 M2組成的流水線上完成加工。 分析： ?直觀上，一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器 M1沒(méi)有空閑時(shí)間，且機(jī)器M2的空閑時(shí)間最少。在一般情況下，機(jī)器 M1開(kāi)始加工 S中作業(yè)時(shí)，機(jī)器 M2還在加工其他作業(yè)，要等時(shí)間 t后才可利用。其中 T’是在機(jī)器 M2的等待時(shí)間為 b?(1)時(shí)，安排作業(yè)?(2)， … ， ?(n)所需的時(shí)間。則 ?(1)， ?’(2)， … ， ?’(n)是 N的一個(gè)調(diào)度，且該調(diào)度所需的時(shí)間為 a?(1)+T(S,b?(1))a?(1)+T’。這就證明了流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。則由動(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不等式 。 },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 ???? ?37 算法描述 流水作業(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)度。所需的空間為 O(n)。 39 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)值。例如，當(dāng) c2n時(shí)，算法需要 Ω(n2n)計(jì)算時(shí)間。如圖所示。 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) 42 算法改進(jìn) ?函數(shù) m(i,j)是由函數(shù) m(i+1,j)與函數(shù) m(i+1,jwi)+vi作 max運(yùn)算得到的。除受控跳躍點(diǎn)外， p[i+1]?q[i+1]中的其他跳躍點(diǎn)均為 p[i]中的跳躍點(diǎn)。因此，q[6]=p[6]?(w5,v5)={(4,6)}。將受控跳躍點(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。從跳躍點(diǎn)集 p[i]的定義可以看出， p[i]中的跳躍點(diǎn)相應(yīng)于 xi,…,x n的 0/1賦值。在這種情況下，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為 O(min{nc,2n}
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1