【文章內容簡介】 剖分的結構及其相關問題 ?一個表達式的完全加括號方式相應于一棵完全二叉樹，稱為表達式的語法樹。例如，完全加括號的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應的語法樹如圖 (a)所示。 ?凸多邊形 {v0,v1,…v n1}的三角剖分也可以用語法樹表示。例如，圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語法樹表示。 ?矩陣連乘積中的每個矩陣 Ai對應于凸 (n+1)邊形中的一條邊vi1vi。三角剖分中的一條弦 vivj， ij，對應于矩陣連乘積A[i+1:j]。 26 最優(yōu)子結構性質 ?凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結構性質。 ?事實上，若凸 (n+1)邊形 P={v0,v1,…,v n1}的最優(yōu)三角剖分 T包含三角形 v0vkvn， 1≤k≤n1，則 T的權為 3個部分權的和：三角形 v0vkvn的權，子多邊形 {v0,v1,…,v k}和 {vk,vk+1,…,v n}的權之和?？梢詳嘌裕?T所確定的這 2個子多邊形的三角剖分也是最優(yōu)的。因為若有 {v0,v1,…,v k}或{vk,vk+1,…,v n}的更小權的三角剖分將導致 T不是最優(yōu)三角剖分的矛盾。 27 最優(yōu)三角剖分的遞歸結構 ?定義 t[i][j]， 1≤ij≤n為凸子多邊形 {vi1,vi,…,v j}的最優(yōu)三角剖分所對應的權函數值，即其最優(yōu)值。為方便起見，設退化的多邊形{vi1,vi}具有權值 0。據此定義，要計算的凸 (n+1)邊形 P的最優(yōu)權值為 t[1][n]。 ?t[i][j]的值可以利用最優(yōu)子結構性質遞歸地計算。當 ji≥1時，凸子多邊形至少有 3個頂點。由最優(yōu)子結構性質， t[i][j]的值應為t[i][k]的值加上 t[k+1][j]的值，再加上三角形 vi1vkvj的權值，其中i≤k≤j1。由于在計算時還不知道 k的確切位置，而 k的所有可能位置只有 ji個，因此可以在這 ji個位置中選出使 t[i][j]值達到最小的位置。由此， t[i][j]可遞歸地定義為： ??????????? ??? jijivvvwjktkitjit jkijki)}(]][1[]][[{m i n0]][[128 多邊形游戲 多邊形游戲是一個單人玩的游戲，開始時有一個由 n個頂點構成的多邊形。每個頂點被賦予一個整數值，每條邊被賦予一個運算符“ +”或“ *”。所有邊依次用整數從 1到 n編號。 游戲第 1步，將一條邊刪除。 隨后 n1步按以下方式操作： (1)選擇一條邊 E以及由 E連接著的 2個頂點 V1和 V2； (2)用一個新的頂點取代邊 E以及由 E連接著的 2個頂點 V1和 V2。將由頂點 V1和 V2的整數值通過邊 E上的運算得到的結果賦予新頂點。 最后，所有邊都被刪除，游戲結束。游戲的得分就是所剩頂點上的整數值。 問題 :對于給定的多邊形，計算最高得分。 29 最優(yōu)子結構性質 ?在所給多邊形中，從頂點 i(1≤i≤n)開始，長度為 j(鏈中有 j個頂點 )的順時針鏈 p(i， j) 可表示為 v[i]， op[i+1]， … ， v[i+j1]。 ?如果這條鏈的最后一次合并運算在 op[i+s]處發(fā)生 (1≤s≤j1)，則可在 op[i+s]處將鏈分割為 2個子鏈 p(i， s)和 p(i+s， js)。 ?設 m1是對子鏈 p(i， s)的任意一種合并方式得到的值，而 a和 b分別是在所有可能的合并中得到的最小值和最大值。 m2是 p(i+s，js)的任意一種合并方式得到的值，而 c和 d分別是在所有可能的合并中得到的最小值和最大值。依此定義有 a≤m1≤b， c≤m2≤d (1)當 op[i+s]=39。+39。時，顯然有 a+c≤m≤b+d (2)當 op[i+s]=39。*39。時，有 min{ac， ad， bc， bd}≤m≤max{ac， ad，bc， bd} ?換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。 30 圖像壓縮 圖象的變位壓縮存儲格式將所給的象素點序列{p1,p2,…,p n},0≤pi≤255分割成 m個連續(xù)段 S1,S2,…,S m。第 i個象素段 Si中 (1≤i≤m)，有 l[i]個象素 ,且該段中每個象素都只用 b[i]位表示。設 則第 i個象素段 Si為 設 ，則 hi?b[i]?8。因此需要用 3位表示 b[i],如果限制 1?l[i]?255，則需要用 8位表示 l[i]。因此，第 i個象素段所需的存儲空間為 l[i]*b[i]+11位。按此格式存儲象素序列{p1,p2,…,pn} ，需要 位的存儲空間。 圖象壓縮問題要求確定象素序列 {p1,p2,… ,pn}的最優(yōu)分段，使得依此分段所需的存儲空間最少。每個分段的長度不超過256位。 ???? 11][][ ikklit },{ ][][1][ ilititi ppS ??? ??????? ?????? ?? ???? 1m a xlo g ][][1][ kilitkiti phmibilmi11][*][1???31 圖像壓縮 設 l[i]， b[i] (1≤i≤ m )，是 {p1,p2,…,pn} 的最優(yōu)分段。顯而易見， l[1]，b[1]是 {p1,…,p l[1]}的最優(yōu)分段，且 l[i]， b[i] (2≤i≤ m ) ，是 {pl[1]+1,…,p n}的最優(yōu)分段。即圖象壓縮問題滿足最優(yōu)子結構性質。 設 s[i]， 1≤i≤n，是象素序列 {p1,…,pn} 的最優(yōu)分段所需的存儲位數。由最優(yōu)子結構性質易知： 其中 11)},1m a x (b*][{m i n][ }2 5 6,m i n {1 ?????? ?? ikikkisis ik?????? ?????? ?? ?? 1}{m a xl o g),b m a x ( kjki pji算法復雜度分析： 由于算法 press中對 k的循環(huán)次數不超這 256，故對每一個確定的 i，可在時間 O(1)內完成的計算。因此整個算法所需的計算時間為 O(n)。 32 電路布線 在一塊電路板的上、下 2端分別有 n個接線柱。根據電路設計，要求用導線 (i,π(i))將上端接線柱與下端接線柱相連，如圖所示。其中 π(i)是 {1,2,…,n} 的一個排列。導線 (i,π(i))稱為該電路板上的第 i條連線。對于任何 1≤ij≤n，第 i條連線和第 j條連線相交的充分且必要的條件是 π(i)π(j)。 電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。 33 記 。 N(i,j)的最大不相交子集為 MNS(i,j)。 Size(i,j)=|MNS(i,j)|。 (1)當 i=1時， (2)當 i1時， jπ(i)。此時， 。故在這種情況下，N(i,j)=N(i1,j)，從而 Size(i,j)=Size(i1,j)。 j≥π(i)， (i,π(i))∈ MNS(i,j) 。 則對任意 (t,π(t)) ∈ MNS(i,j)有ti且 π(t)π(i)。在這種情況下 MNS(i,j){(i,π(i))}是 N(i1,π(i)1)的最大不相交子集。 若 ，則對任意 (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 ???