【正文】 圖像的變位壓縮存儲(chǔ)格式將所給的象素點(diǎn)序列{p1,p2,…,pn},0≤pi≤255 分割成 m個(gè)連續(xù)段 S1,S2,…,Sm 。第 i個(gè)象素段 Si中 (1≤i≤m)，有 l[i]個(gè)象素 ,且該段中每個(gè)象素都只用b[i]位表示。設(shè) 則第 i個(gè)象素段 Si為 設(shè) ，則 hi?b[i]?8。因此需要用 3位表示 b[i],如果限制 1?l[i]?255，則需要用 8位表示 l[i]。因此，第 i個(gè)象素段所需的存儲(chǔ)空間為 l[i]*b[i]+11位。按此格式存儲(chǔ)象素序列{p1,p2,…,pn} ，需要 位的存儲(chǔ)空間。 圖像壓縮問(wèn)題要求確定象素序列 {p1,p2,… ,pn}的最優(yōu)分段，使得依此分段所需的存儲(chǔ)空間最少。每個(gè)分段的長(zhǎng)度不超過(guò)256位。 ???? 11][][ ikklit?????? ?????? ?? ???? 1m a xlo g ][][1][ kilitkiti phmibilmi11][*][1???圖像壓縮 設(shè) l[i]， b[i]，是 {p1,p2,…,pn} 的最優(yōu)分段。顯而易見， l[1]， b[1]是 {p1,…,p l[1]}的最優(yōu)分段，且 l[i]， b[i]，是 {pl[1]+1,…,p n}的最優(yōu)分段。即圖像壓縮問(wèn)題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。 設(shè) s[i]， 1≤i≤n，是象素序列 {p1,…,pn} 的最優(yōu)分段所需的存儲(chǔ)位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)易知： 其中 11)},1m a x(b*][{m i n][ }256,m i n {1 ?????? ?? ikikkisis ik?????? ?????? ?? ?? 1}{m a xl o g),b m a x ( kjki pji算法復(fù)雜度分析： 由于算法 press中對(duì) k的循環(huán)次數(shù)不超這 256，故對(duì)每一個(gè)確定的 i，可在時(shí)間 O(1)內(nèi)完成的計(jì)算。因此整個(gè)算法所需的計(jì)算時(shí)間為 O(n)。 電路布線 在一塊電路板的上、下 2端分別有 n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線 (i,π(i))將上端接線柱與下端接線柱相連，如圖所示。其中 π(i)是 {1,2,…,n} 的一個(gè)排列。導(dǎo)線 (i,π(i))稱為該電路板上的第 i條連線。對(duì)于任何 1≤ij≤n，第 i條連線和第 j條連線相交的充分且必要的條件是 π(i)π(j)。 電路布線問(wèn)題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說(shuō)，該問(wèn)題要求確定導(dǎo)線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。 記 。 N(i,j)的最大不相交子集為 MNS(i,j)。 Size(i,j)=|MNS(i,j)|。 (1)當(dāng) i=1時(shí)， (2)當(dāng) i1時(shí)， jπ(i)。此時(shí)， 。故在這種情況下，N(i,j)=N(i1,j)，從而 Size(i,j)=Size(i1,j)。 j≥π(i)， (i,π(i))∈ MNS(i,j) 。 則對(duì)任意 (t,π(t)) ∈ MNS(i,j)有ti且 π(t)π(i)。在這種情況下 MNS(i,j){(i,π(i))}是 N(i1,π(i)1)的最大不相交子集。 若 ，則對(duì)任意 (t,π(t)) ∈ MNS(i,j)有 ti。從而 。因此， Size(i,j)≤Size(i1,j)。 另一方面 ，故又有 Size(i,j)≥Size(i1,j)， 從而 Size(i,j)=Size(i1,j)。 電路布線 })(,))(,(|{),( 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(??jjjSi z e)()(}1)1)(,1(),1(m a x {),1(),(ijijiiSi z ejiSi z ejiSi z ejiSi z e??? ???????????流水作業(yè)調(diào)度 n個(gè)作業(yè) {1， 2， … ， n}要在由 2臺(tái)機(jī)器 M1和 M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在 M1上加工，然后在M2上加工。 M1和 M2加工作業(yè) i所需的時(shí)間分別為 ai和 bi。 流水作業(yè)調(diào)度問(wèn)題要求確定這 n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在機(jī)器 M1上開始加工，到最后一個(gè)作業(yè)在機(jī)器 M2上加工完成所需的時(shí)間最少。 分析： ?直觀上，一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器 M1沒有空閑時(shí)間，且機(jī)器M2的空閑時(shí)間最少。在一般情況下，機(jī)器 M2上會(huì)有機(jī)器空閑和作業(yè)積壓 2種情況。 ?設(shè)全部作業(yè)的集合為 N={1， 2， … ， n}。 S?N是 N的作業(yè)子集。在一般情況下，機(jī)器 M1開始加工 S中作業(yè)時(shí)，機(jī)器 M2還在加工其他作業(yè)，要等時(shí)間 t后才可利用。將這種情況下完成S中作業(yè)所需的最短時(shí)間記為 T(S,t)。流水作業(yè)調(diào)度問(wèn)題的最優(yōu)值為 T(N,0)。 流水作業(yè)調(diào)度 設(shè) ?是所給 n個(gè)流水作業(yè)的一個(gè)最優(yōu)調(diào)度，它所需的加工時(shí)間為 a?(1)+T’。其中 T’是在機(jī)器 M2的等待時(shí)間為 b?(1)時(shí)，安排作業(yè)?(2)， … ， ?(n)所需的時(shí)間。 記 S=N{?(1)}，則有 T’=T(S,b?(1))。 證明： 事實(shí)上，由 T的定義知 T’?T(S,b?(1))。若 T’T(S,b?(1))，設(shè) ?’ 是作業(yè)集 S在機(jī)器 M2的等待時(shí)間為 b?(1)情況下的一個(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的最優(yōu)調(diào)度矛盾。故 T’?T(S,b?(1))。從而 T’=T(S,b?(1))。這就證明了流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。 由流水作業(yè)調(diào)度問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知， )}},{({mi n)0,( 1 iini biNTaNT ??? ??} ) }0,ma x {},{({mi n),( iiiSi atbiSTatST ????? ?Johnson不等式 對(duì)遞歸式的深入分析表明，算法可進(jìn)一步得到簡(jiǎn)化。 設(shè) ?是作業(yè)集 S在機(jī)器 M2的等待時(shí)間為 t時(shí)的任一最優(yōu)調(diào)度。若?(1)=i, ?(2)=j。則由動(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 a x {}0,}0,m a x {m a x {iijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaatbbt????????????????????????如果作業(yè) i和 j滿足 min{bi,aj}≥ min{bj,ai}，則稱作業(yè) i和 j滿足 Johnson不等式 。 流水作業(yè)調(diào)度的 Johnson法則 交換作業(yè) i和作業(yè) j的加工順序，得到作業(yè)集 S的另一調(diào)度，它所需的加工時(shí)間為 T’(S,t)=ai+aj+T(S{i,j},tji) 其中， 當(dāng)作業(yè) i和 j滿足 Johnson不等式時(shí)，有 由此可見當(dāng)作業(yè) i和作業(yè) j不滿足 Johnson不等式時(shí)，交換它們的加工順序后，不增加加工時(shí)間。對(duì)于流水作業(yè)調(diào)度問(wèn)題，必存在最優(yōu)調(diào)度 ? ，使得作業(yè) ?(i)和 ?(i+1)滿足 Johnson不等式。進(jìn)一步還可以證明，調(diào)度滿足 Johnson法則當(dāng)且僅當(dāng)對(duì)任意 ij有 由此可知， 所有滿足 Johnson法則的調(diào)度均為最優(yōu)調(diào)度。 },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 ???? ?算法描述 流水作業(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)度。 }。|{},|{ 21 iiii baiNbaiN ????算法復(fù)雜度分析： 算法的主要計(jì)算時(shí)間花在對(duì)作業(yè)集的排序。因此，在最壞情況下算法所需的計(jì)算時(shí)間為 O(nlogn)。所需的空間為 O(n)。 01背包問(wèn)題 ??niii xv1m a x???????????nixCxwiniii1},1,0{1給定 n種物品和一背包。物品 i的重量是 wi，其價(jià)值為 vi，背包的容量為 C。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大 ? 01背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。 01背包問(wèn)題 設(shè)所給 01背包問(wèn)題的子問(wèn)題 ??nikkk xvm a x???????????nkixjxwknikkk},1,0{的最優(yōu)值為 m(i， j)，即 m(i， j)是背包容量為 j，可選擇物品為 i，i+1， … ， n時(shí) 01背包問(wèn)題的最優(yōu)值。由 01背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算 m(i， j)的遞歸式如下。 iiiiwjwjjimvwjimjimjim????????????0),1(}),1(),1(m a x{),(nnnwjwjvjnm???????00),(算法復(fù)雜度分析： 從 m(i， j)的遞歸式容易看出，算法需要 O(nc)計(jì)算時(shí)間。當(dāng)背包容量 c很大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng) c2n時(shí)，算法需要 Ω(n2n)計(jì)算時(shí)間。