動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)ppt課件(編輯修改稿)
2025-06-02 12:09 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 剖分的結(jié)構(gòu)及其相關(guān)問題 ?一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹，稱為表達(dá)式的語(yǔ)法樹。例如，完全加括號(hào)的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應(yīng)的語(yǔ)法樹如圖 (a)所示。 ?凸多邊形 {v0,v1,…v n1}的三角剖分也可以用語(yǔ)法樹表示。例如，圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語(yǔ)法樹表示。 ?矩陣連乘積中的每個(gè)矩陣 Ai對(duì)應(yīng)于凸 (n+1)邊形中的一條邊vi1vi。三角剖分中的一條弦 vivj， ij，對(duì)應(yīng)于矩陣連乘積A[i+1:j]。 26 最優(yōu)子結(jié)構(gòu)性質(zhì) ?凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結(jié)構(gòu)性質(zhì)。 ?事實(shí)上，若凸 (n+1)邊形 P={v0,v1,…,v n1}的最優(yōu)三角剖分 T包含三角形 v0vkvn， 1≤k≤n1，則 T的權(quán)為 3個(gè)部分權(quán)的和：三角形 v0vkvn的權(quán)，子多邊形 {v0,v1,…,v k}和 {vk,vk+1,…,v n}的權(quán)之和。可以斷言，由 T所確定的這 2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲?{v0,v1,…,v k}或{vk,vk+1,…,v n}的更小權(quán)的三角剖分將導(dǎo)致 T不是最優(yōu)三角剖分的矛盾。 27 最優(yōu)三角剖分的遞歸結(jié)構(gòu) ?定義 t[i][j]， 1≤ij≤n為凸子多邊形 {vi1,vi,…,v j}的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。為方便起見，設(shè)退化的多邊形{vi1,vi}具有權(quán)值 0。據(jù)此定義，要計(jì)算的凸 (n+1)邊形 P的最優(yōu)權(quán)值為 t[1][n]。 ?t[i][j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。當(dāng) ji≥1時(shí)，凸子多邊形至少有 3個(gè)頂點(diǎn)。由最優(yōu)子結(jié)構(gòu)性質(zhì)， t[i][j]的值應(yīng)為t[i][k]的值加上 t[k+1][j]的值，再加上三角形 vi1vkvj的權(quán)值，其中i≤k≤j1。由于在計(jì)算時(shí)還不知道 k的確切位置，而 k的所有可能位置只有 ji個(gè)，因此可以在這 ji個(gè)位置中選出使 t[i][j]值達(dá)到最小的位置。由此， t[i][j]可遞歸地定義為： ??????????? ??? jijivvvwjktkitjit jkijki)}(]][1[]][[{m i n0]][[128 多邊形游戲 多邊形游戲是一個(gè)單人玩的游戲，開始時(shí)有一個(gè)由 n個(gè)頂點(diǎn)構(gòu)成的多邊形。每個(gè)頂點(diǎn)被賦予一個(gè)整數(shù)值，每條邊被賦予一個(gè)運(yùn)算符“ +”或“ *”。所有邊依次用整數(shù)從 1到 n編號(hào)。 游戲第 1步，將一條邊刪除。 隨后 n1步按以下方式操作： (1)選擇一條邊 E以及由 E連接著的 2個(gè)頂點(diǎn) V1和 V2； (2)用一個(gè)新的頂點(diǎn)取代邊 E以及由 E連接著的 2個(gè)頂點(diǎn) V1和 V2。將由頂點(diǎn) V1和 V2的整數(shù)值通過邊 E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。 最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。 問題 :對(duì)于給定的多邊形，計(jì)算最高得分。 29 最優(yōu)子結(jié)構(gòu)性質(zhì) ?在所給多邊形中，從頂點(diǎn) i(1≤i≤n)開始，長(zhǎng)度為 j(鏈中有 j個(gè)頂點(diǎn) )的順時(shí)針鏈 p(i， j) 可表示為 v[i]， op[i+1]， … ， v[i+j1]。 ?如果這條鏈的最后一次合并運(yùn)算在 op[i+s]處發(fā)生 (1≤s≤j1)，則可在 op[i+s]處將鏈分割為 2個(gè)子鏈 p(i， s)和 p(i+s， js)。 ?設(shè) m1是對(duì)子鏈 p(i， s)的任意一種合并方式得到的值，而 a和 b分別是在所有可能的合并中得到的最小值和最大值。 m2是 p(i+s，js)的任意一種合并方式得到的值，而 c和 d分別是在所有可能的合并中得到的最小值和最大值。依此定義有 a≤m1≤b， c≤m2≤d (1)當(dāng) op[i+s]=39。+39。時(shí)，顯然有 a+c≤m≤b+d (2)當(dāng) op[i+s]=39。*39。時(shí)，有 min{ac， ad， bc， bd}≤m≤max{ac， ad，bc， bd} ?換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。 30 圖像壓縮 圖象的變位壓縮存儲(chǔ)格式將所給的象素點(diǎn)序列{p1,p2,…,p n},0≤pi≤255分割成 m個(gè)連續(xù)段 S1,S2,…,S m。第 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ǔ)空間。 圖象壓縮問題要求確定象素序列 {p1,p2,… ,pn}的最優(yōu)分段，使得依此分段所需的存儲(chǔ)空間最少。每個(gè)分段的長(zhǎng)度不超過256位。 ???? 11][][ ikklit },{ ][][1][ ilititi ppS ??? ??????? ?????? ?? ???? 1m a xlo g ][][1][ kilitkiti phmibilmi11][*][1???31 圖像壓縮 設(shè) 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)子結(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][ }2 5 6,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)。 32 電路布線 在一塊電路板的上、下 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)。 電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導(dǎo)線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。 33 記 。 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 ???
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1