第3章動(dòng)態(tài)規(guī)劃-文庫(kù)吧資料
2024-10-08 19:17本頁(yè)面
【正文】 {?(1)}，則有 T’=T(S,b?(1))。 34 流水作業(yè)調(diào)度 設(shè) ?是所給 n個(gè)流水作業(yè)的一個(gè)最優(yōu)調(diào)度，它所需的加工時(shí)間為 a?(1)+T’。將這種情況下完成S中作業(yè)所需的最短時(shí)間記為 T(S,t)。 S?N是 N的作業(yè)子集。在一般情況下，機(jī)器 M2上會(huì)有機(jī)器空閑和作業(yè)積壓 2種情況。 流水作業(yè)調(diào)度問(wèn)題要求確定這 n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在機(jī)器 M1上開(kāi)始加工，到最后一個(gè)作業(yè)在機(jī)器 M2上加工完成所需的時(shí)間最少。每個(gè)作業(yè)加工的順序都是先在 M1上加工，然后在M2上加工。 另一方面 ，故又有 Size(i,j)≥Size(i1,j)， 從而 Size(i,j)=Size(i1,j)。從而 。在這種情況下 MNS(i,j){(i,π(i))}是 N(i1,π(i)1)的最大不相交子集。 j≥π(i)， (i,π(i))∈ MNS(i,j) 。此時(shí)， 。 Size(i,j)=|MNS(i,j)|。 32 記 。 電路布線問(wèn)題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。導(dǎo)線 (i,π(i))稱為該電路板上的第 i條連線。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線 (i,π(i))將上端接線柱與下端接線柱相連，如圖所示。因此整個(gè)算法所需的計(jì)算時(shí)間為 O(n)。 設(shè) s[i]， 1≤i≤n，是象素序列 {p1,…,pn} 的最優(yōu)分段所需的存儲(chǔ)位數(shù)。顯而易見(jiàn)， l[1]， b[1]是 {p1,…,p l[1]}的最優(yōu)分段，且 l[i]， b[i]，是 {pl[1]+1,…,p n}的最優(yōu)分段。每個(gè)分段的長(zhǎng)度不超過(guò)256位。按此格式存儲(chǔ)象素序列{p1,p2,…,pn} ，需要 位的存儲(chǔ)空間。因此需要用 3位表示 b[i],如果限制 1?l[i]?255，則需要用 8位表示 l[i]。第 i個(gè)象素段 Si中 (1≤i≤m)，有 l[i]個(gè)象素 ,且該段中每個(gè)象素都只用b[i]位表示。時(shí)，有 min{ac， ad， bc， bd}≤m≤max{ac， ad，bc， bd} ?換句話說(shuō)，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。時(shí)，顯然有 a+c≤m≤b+d (2)當(dāng) op[i+s]=39。依此定義有 a≤m1≤b，c≤m2≤d (1)當(dāng) op[i+s]=39。 ?設(shè) m1是對(duì)子鏈 p(i， s)的任意一種合并方式得到的值，而 a和 b分別是在所有可能的合并中得到的最小值和最大值。 28 最優(yōu)子結(jié)構(gòu)性質(zhì) ?在所給多邊形中，從頂點(diǎn) i(1≤i≤n)開(kāi)始，長(zhǎng)度為 j(鏈中有 j個(gè)頂點(diǎn) )的順時(shí)針鏈 p(i， j) 可表示為 v[i]， op[i+1]， … ， v[i+j1]。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。將由頂點(diǎn) V1和 V2的整數(shù)值通過(guò)邊 E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。 游戲第 1步，將一條邊刪除。每個(gè)頂點(diǎn)被賦予一個(gè)整數(shù)值，每條邊被賦予一個(gè)運(yùn)算符“ +”或“ *”。由于在計(jì)算時(shí)還不知道 k的確切位置，而 k的所有可能位置只有 ji個(gè)，因此可以在這 ji個(gè)位置中選出使 t[i][j]值達(dá)到最小的位置。當(dāng) ji≥1時(shí)，凸子多邊形至少有 3個(gè)頂點(diǎn)。據(jù)此定義，要計(jì)算的凸 (n+1)邊形 P的最優(yōu)權(quán)值為 t[1][n]。 26 最優(yōu)三角剖分的遞歸結(jié)構(gòu) ?定義 t[i][j]， 1≤ij≤n為凸子多邊形 {vi1,vi,…,vj} 的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值?？梢詳嘌?，由 T所確定的這 2個(gè)子多邊形的三角剖分也是最優(yōu)的。 25 最優(yōu)子結(jié)構(gòu)性質(zhì) ?凸多邊形的最優(yōu)三角剖分問(wèn)題有最優(yōu)子結(jié)構(gòu)性質(zhì)。 ?矩陣連乘積中的每個(gè)矩陣 Ai對(duì)應(yīng)于凸 (n+1)邊形中的一條邊vi1vi。 ?凸多邊形 {v0,v1,…v n1}的三角剖分也可以用語(yǔ)法樹(shù)表示。 24 三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題 ?一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹(shù)，稱為表達(dá)式的語(yǔ)法樹(shù)。 ?給定凸多邊形 P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù) w。弦將多邊形分割成 2個(gè)多邊形 {vi,vi+1,…,v j}和 {vj,vj+1,…v i}。 23 凸多邊形最優(yōu)三角剖分 ?用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即 P={v0,v1,…,v n1}表示具有 n條邊的凸多邊形。因此，用 2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。 ?如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上，數(shù)組元素 c[i][j]的值僅由 c[i1][j1]， c[i1][j]和c[i][j1]這 3個(gè)數(shù)組元素的值所確定。 else lcs(i,j1,x,b)。 (x[i])。 構(gòu)造最長(zhǎng)公共子序列 Algorithm lcs(int i,int j,char [] x,int [][] b) { if (i ==0 || j==0) return。 12: else 13: c[i][j]=c[i][j1]。 9: else if (c[i1][j]=c[i][j1]) 10: c[i][j]=c[i1][j]。 j++) 6: if (x[i]==y[j]) 7: c[i][j]=c[i1][j1]+1。 i++) 5: for (int j = 1。 4: for (int i = 1。 3: c[i][0]=0。 Algorithm lcsLength(x,y,b) 1: m?。0,。故此時(shí) C[i][j]=0。其中， Xi={x1,x2,…,x i}； Yj={y1,y2,…,y j}。 20 子問(wèn)題的遞歸結(jié)構(gòu) 由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。 由此可見(jiàn)， 2個(gè)序列的最長(zhǎng)公共子序列包含了這 2個(gè)序列的前綴的最長(zhǎng)公共子序列。 (2)若 xm≠yn且 zk≠xm，則 Z是 xm1和 Y的最長(zhǎng)公共子序列。 ? 給定 2個(gè)序列 X={x1,x2,… ,xm}和 Y={y1,y2,… ,yn}，找出 X和 Y的最長(zhǎng)公共子序列。例如，序列 Z={B， C，D， B}是序列 X={A， B， C， B， D， A， B}的子序列，相應(yīng)的遞增下標(biāo)序列為 {2， 3， 5， 7}。 return u。 s[i][j] = k。 k++) { int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i1]*p[k]*p[j]。 for (int k = i+1。 int u = lookupChain(i+1,j) + p[i1]*p[i]*p[j]。 m?0 private static int lookupChain(int i, int j) { if (m[i][j] 0) return m[i][j]。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。 ?動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。 注意：同一個(gè)問(wèn)題可以有多種 方式刻劃 它 的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問(wèn)題的維度低） 16 二、重疊子問(wèn)題 ?遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。 ?利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。這種性質(zhì)稱為 最優(yōu)子結(jié)構(gòu)性質(zhì) 。算法所占用的空間顯然為 O(n2)。循環(huán)體內(nèi)的計(jì)算量為 O(1)，而 3重循環(huán)的總次數(shù)為 O(n3)。 s[i][j] = k。 k++) { int t =
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1