【正文】 規(guī)劃算法的基本要素 一、最優(yōu)子結構 ?矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。 ?在分析問題的最優(yōu)子結構性質(zhì)時，所用的方法具有普遍性：首先假設由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的，然后再設法說明在這個假設下可構造出比原問題最優(yōu)解更好的解，從而導致矛盾。最優(yōu)子結構是問題能用動態(tài)規(guī)劃算法求解的前提。 這種性質(zhì)稱為 子問題的重疊性質(zhì) 。 ?通常不同的子問題個數(shù)隨問題的大小呈多項式增長。 18 動態(tài)規(guī)劃算法的基本要素 三、備忘錄方法 ?備忘錄方法的控制結構與直接遞歸方法的控制結構相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復求解。 if (i == j) return 0。 s[i][j] = i。 k j。 if (t u) { u = t。} } m[i][j] = u。 } 19 最長公共子序列 ?若給定序列 X={x1,x2,…,x m}，則另一序列Z={z1,z2,…,z k}，是 X的子序列是指存在一個嚴格遞增下標序列 {i1,i2,…,i k}使得對于所有 j=1,2,…,k 有： zj=xij。 ?給定 2個序列 X和 Y，當另一序列 Z既是 X的子序列又是Y的子序列時，稱 Z是序列 X和 Y的 公共子序列 。 20 最長公共子序列的結構 設序列 X={x1,x2,…,x m}和 Y={y1,y2,…,y n}的最長公共子序列為Z={z1,z2,…,z k} ，則 (1)若 xm=yn，則 zk=xm=yn，且 zk1是 xm1和 yn1的最長公共子序列。 (3)若 xm≠yn且 zk≠yn，則 Z是 X和 yn1的最長公共子序列。因此，最長公共子序列問題具有 最優(yōu)子結構性質(zhì) 。用 c[i][j]記錄序列和的最長公共子序列的長度。當 i=0或 j=0時，空序列是 Xi和 Yj的最長公共子序列。其它情況下，由最優(yōu)子結構性質(zhì)可建立遞歸關系如下： ?????????????????jijiyxjiyxjijijicjicjicjic。0,0,0]}][1[],1][[m ax {1]1][1[0]][[22 計算最優(yōu)值 由于在所考慮的子問題空間中，總共有 θ(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。 for (i = 1。 i++) c[i][0] = 0。 i = n。 for (i = 1。 i++) for (j = 1。 j++) { if (x[i]==y[j]) { c[i][j]=c[i1][j1]+1。} else if (c[i1][j]=c[i][j1]) { c[i][j]=c[i1][j]。} else { c[i][j]=c[i][j1]。 } } } 構造最長公共子序列 void LCS(int i， int j， char *x， int **b) { if (i ==0 || j==0) return。 coutx[i]。 else LCS(i， j1， x， b)。事實上，數(shù)組元素 c[i][j]的值僅由 c[i1][j1]， c[i1][j]和c[i][j1]這 3個數(shù)組元素的值所確定。 ?如果只需要計算最長公共子序列的長度，則算法的空間需求可大大減少。因此，用 2行的數(shù)組空間就可以計算出最長公共子序列的長度。 24 凸多邊形最優(yōu)三角剖分 ?用多邊形頂點的逆時針序列表示凸多邊形，即 P={v0,v1,…,v n1}表示具有 n條邊的凸多邊形。弦將多邊形分割成 2個多邊形 {vi,vi+1,…,v j}和 {vj,vj+1,…v i}。 ?給定凸多邊形 P，以及定義在由多邊形的邊和弦組成的三角形上的權函數(shù) w。 25 三角剖分的結構及其相關問題 ?一個表達式的完全加括號方式相應于一棵完全二叉樹，稱為表達式的語法樹。 ?凸多邊形 {v0,v1,…v n1}的三角剖分也可以用語法樹表示。 ?矩陣連乘積中的每個矩陣 Ai對應于凸 (n+1)邊形中的一條邊vi1vi。 26 最優(yōu)子結構性質(zhì) ?凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結構性質(zhì)?？梢詳嘌?，由 T所確定的這 2個子多邊形的三角剖分也是最優(yōu)的。 27 最優(yōu)三角剖分的遞歸結構 ?定義 t[i][j]， 1≤ij≤n為凸子多邊形 {vi1,vi,…,v j}的最優(yōu)三角剖分所對應的權函數(shù)值，即其最優(yōu)值。據(jù)此定義，要計算的凸 (n+1)邊形 P的最優(yōu)權值為 t[1][n]。當 ji≥1時，凸子多邊形至少有 3個頂點。由于在計算時還不知道 k的確切位置，而 k的所有可能位置只有 ji個，因此可以在這 ji個位置中選出使 t[i][j]值達到最小的位置。每個頂點被賦予一個整數(shù)值，每條邊被賦予一個運算符“ +”或“ *”。 游戲第 1步，將一條邊刪除。將由頂點 V1和 V2的整數(shù)值通過邊 E上的運算得到的結果賦予新頂點。游戲的得分就是所剩頂點上的整數(shù)值。 29 最優(yōu)子結構性質(zhì) ?在所給多邊形中，從頂點 i(1≤i≤n)開始，長度為 j(鏈中有 j個頂點 )的順時針鏈 p(i， j) 可表示為 v[i]， op[i+1]， … ， v[i+j1]。 ?設 m1是對子鏈 p(i， s)的任意一種合并方式得到的值，而 a和 b分別是在所有可能的合并中得到的最小值和最大值。依此定義有 a≤m1≤b， c≤m2≤d (1)當 op[i+s]=39。時，顯然有 a+c≤m≤b+d (2)當 op[i+s]=39。時，有 min{ac， ad， bc， bd}≤m≤max{ac， ad，bc， bd} ?換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。第 i個象素段 Si中 (1≤i≤m)，有 l[i]個象素 ,且該段中每個象素都只用 b[i]位表示。因此需要用 3位表示 b[i],如果限制 1?l[i]?255，則需要用 8位表示 l[i]。按此格式存儲象素序列{p1,p2,…,pn} ，需要 位的存儲空間。每個分段的長度不超過256位。顯而易見， l[1]，b[1]是 {p1,…,p l[1]}的最優(yōu)分段，且 l[i]， b[i] (2≤i≤ m ) ，是 {pl[1]+1,…,p n}的最優(yōu)分段。 設 s[i]， 1≤i≤n，是象素序列 {p1,…,pn} 的最優(yōu)分段所需的存儲位數(shù)。因此整個算法所需的計算時間為 O(n)。根據(jù)電路設計，要求用導線 (i,π(i))將上端接線柱與下端接線柱相連，如圖所示。導線 (i,π(i))稱為該電路板上的第 i條連線。 電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。 33 記 。 Size(i,j)=|MNS(i,j)|。此時， 。 j≥π(i)， (i,π(i))∈ MNS(i,j) 。在這種情況下 MNS(i,j){(i,π(i))}是 N(i1,π(i)1)的最大不相交子集。從而 。 另一方面 ，故又有 Size(i,j)≥Size(i1,j)， 從而 Size(i,j)=Size(i1,j)。每個作業(yè)加工的順序都是先在 M1上加工，然后在M2上加工。 流水作業(yè)調(diào)度問題要求確定這 n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機器 M1上開始加工，到最后一個作業(yè)在機器 M2上加工完成所需的時間最少。在一般情況下，機器 M2上會有機器空閑和作業(yè)積壓 2種情況。 S?N是 N的作業(yè)子集。將這種情況下完成S中作業(yè)所需的最短時間記為 T(S,t)。 35 流水作業(yè)調(diào)度