【正文】 加工時間。 由流水作業(yè)調(diào)度問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知， )}},{({m in)0,( 1 iini biNTaNT ??? ??} ) }0,m a x {},{({m i n),( iiiSi atbiSTatST ????? ?35 Johnson不等式 對遞歸式的深入分析表明，算法可進(jìn)一步得到簡化。這與 ?是 N的最優(yōu)調(diào)度矛盾。 記 S=N{?(1)}，則有 T’=T(S,b?(1))。將這種情況下完成S中作業(yè)所需的最短時間記為 T(S,t)。在一般情況下，機器 M2上會有機器空閑和作業(yè)積壓 2種情況。每個作業(yè)加工的順序都是先在 M1上加工，然后在M2上加工。從而 。 j≥π(i)， (i,π(i))∈ MNS(i,j) 。 Size(i,j)=|MNS(i,j)|。 電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。根據(jù)電路設(shè)計，要求用導(dǎo)線 (i,π(i))將上端接線柱與下端接線柱相連，如圖所示。 設(shè) s[i]， 1≤i≤n，是象素序列 {p1,…,pn} 的最優(yōu)分段所需的存儲位數(shù)。每個分段的長度不超過256位。因此需要用 3位表示 b[i],如果限制 1?l[i]?255，則需要用 8位表示 l[i]。時，有 min{ac， ad， bc， bd}≤m≤max{ac， ad，bc， bd} ?換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。依此定義有 a≤m1≤b，c≤m2≤d (1)當(dāng) op[i+s]=39。 28 最優(yōu)子結(jié)構(gòu)性質(zhì) ?在所給多邊形中，從頂點 i(1≤i≤n)開始，長度為 j(鏈中有 j個頂點 )的順時針鏈 p(i， j) 可表示為 v[i]， op[i+1]， … ， v[i+j1]。將由頂點 V1和 V2的整數(shù)值通過邊 E上的運算得到的結(jié)果賦予新頂點。每個頂點被賦予一個整數(shù)值，每條邊被賦予一個運算符“ +”或“ *”。當(dāng) ji≥1時，凸子多邊形至少有 3個頂點。 26 最優(yōu)三角剖分的遞歸結(jié)構(gòu) ?定義 t[i][j]， 1≤ij≤n為凸子多邊形 {vi1,vi,…,vj} 的最優(yōu)三角剖分所對應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。 25 最優(yōu)子結(jié)構(gòu)性質(zhì) ?凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結(jié)構(gòu)性質(zhì)。 ?凸多邊形 {v0,v1,…v n1}的三角剖分也可以用語法樹表示。 ?給定凸多邊形 P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù) w。 23 凸多邊形最優(yōu)三角剖分 ?用多邊形頂點的逆時針序列表示凸多邊形，即 P={v0,v1,…,v n1}表示具有 n條邊的凸多邊形。 ?如果只需要計算最長公共子序列的長度，則算法的空間需求可大大減少。 else lcs(i,j1,x,b)。 構(gòu)造最長公共子序列 Algorithm lcs(int i,int j,char [] x,int [][] b) { if (i ==0 || j==0) return。 9: else if (c[i1][j]=c[i][j1]) 10: c[i][j]=c[i1][j]。 i++) 5: for (int j = 1。 3: c[i][0]=0。0,。其中， Xi={x1,x2,…,x i}； Yj={y1,y2,…,y j}。 由此可見， 2個序列的最長公共子序列包含了這 2個序列的前綴的最長公共子序列。 ? 給定 2個序列 X={x1,x2,… ,xm}和 Y={y1,y2,… ,yn}，找出 X和 Y的最長公共子序列。 return u。 k++) { int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i1]*p[k]*p[j]。 int u = lookupChain(i+1,j) + p[i1]*p[i]*p[j]。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效率。 注意：同一個問題可以有多種 方式刻劃 它 的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問題的維度低） 16 二、重疊子問題 ?遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。這種性質(zhì)稱為 最優(yōu)子結(jié)構(gòu)性質(zhì) 。循環(huán)體內(nèi)的計算量為 O(1)，而 3重循環(huán)的總次數(shù)為 O(n3)。 k++) { int t = m[i][k] + m[k+1][j] + p[i1]*p[k]*p[j]。 m[i][j] = m[i+1][j]+ p[i1]*p[i]*p[j]。 r = n。 for (int i = 1。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。這種性質(zhì)稱為 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 算法復(fù)雜度分析： 對于 n個矩陣的連乘積，設(shè)其不同的計算次序為 P(n)。這種計算次序可以用加括號的方式來確定。 ? 以自底向上的方式計算出最優(yōu)值。在用分治法求解時，有些子問題被重復(fù)計算了許多次。不同子問題的數(shù)目常常只有多項式量級。 ? 遞歸地定義最優(yōu)值?？疾爝@ n個矩陣的連乘積 ? 由于矩陣乘法滿足結(jié)合律，所以計算矩陣的連乘可以有許多不同的計算次序。 ?窮舉法 ：列舉出所有可能的計算次序，并計算出每一種計算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。 ? 矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。因此，不同子問題的個數(shù)最多只有 ? 由此可見，在遞歸計算時， 許多子問題被重復(fù)計算多次 。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復(fù)計算，最終得到多項式時間的算法 )(2 2nnn ???????????14 用動態(tài)規(guī)劃法求最優(yōu)解 public static void matrixChain(int [] p, int [][] m, int [][] s) { int n=。 for (int r = 2。 i++) { int j=i+r1。 k j。} } } } A1 A2 A3 A4 A5 A6 30?35 35?15 15?5 5?10 10?20 20?25 ??????????????????????????????1 1 3 7 520223504 3 7 5]5][5[]4][2[7 1 2 5205351 0 0 02 6 2 5]5][4[]3][2[1 3 0 0 02022352 5 0 00]5][3[]2][2[m i n]5][2[541531521pppmmpppmmpppmmm算法復(fù)雜度分析： 算法 matrixChain的主要計算量取決于算法中對 r，i和 k的 3重循環(huán)。 15 動態(tài)規(guī)劃算法的基本要素 一、最優(yōu)子結(jié)構(gòu) ?矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提。 ?通常不同的子問題個數(shù)隨問題的大小呈多項式增長。 if (i == j) return 0。 k j。} } m[i][j] = u。 ? 給定 2個序列 X和 Y，當(dāng)另一序列 Z既是 X的子序列又是 Y的子序列時，稱 Z是序列 X和 Y的 公共子序列 。 (3)若 xm≠yn且 zk≠yn，則 Z是 X和 yn1的最長公共子序列。用 c[i][j]記錄序列和的最長公共子序列的長度。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下： ?????????????????jijiyxjiyxjijijicjicjicjic。 2: n?。 i = m。 8: b[i][j]=1。 14: b[i][j]=3。 } else if (b[i][j]