遞歸、分治、動態(tài)規(guī)劃、回溯(1)(參考版)
2024-10-20 02:46本頁面
【正文】 另一方面 ，故又有 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) 。此時， 。 Size(i,j)=|MNS(i,j)|。 記 。 電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。導(dǎo)線 (i,π(i))稱為該電路板上的第 i條連線。根據(jù)電路設(shè)計，要求用導(dǎo)線 (i,π(i))將上端接線柱與下端接線柱相連，如圖所示。時，有 min{ac， ad， bc， bd}≤m≤max{ac， ad，bc， bd} ?換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。時，顯然有 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是對子鏈 p(i， s)的任意一種合并方式得到的值，而 a和 b分別是在所有可能的合并中得到的最小值和最大值。 最優(yōu)子結(jié)構(gòu)性質(zhì) ?在所給多邊形中，從頂點 i(1≤i≤n)開始，長度為 j(鏈中有 j個頂點 )的順時針鏈 p(i， j) 可表示為 v[i]， op[i+1]， … ， v[i+j1]。游戲的得分就是所剩頂點上的整數(shù)值。將由頂點 V1和 V2的整數(shù)值通過邊 E上的運算得到的結(jié)果賦予新頂點。 游戲第 1步，將一條邊刪除。每個頂點被賦予一個整數(shù)值，每條邊被賦予一個運算符“ +”或“ *”。由于在計算時還不知道 k的確切位置，而 k的所有可能位置只有 ji個，因此可以在這 ji個位置中選出使 t[i][j]值達到最小的位置。當(dāng) ji≥1時，凸子多邊形至少有 3個頂點。據(jù)此定義，要計算的凸 (n+1)邊形 P的最優(yōu)權(quán)值為 t[1][n]。 最優(yōu)三角剖分的遞歸結(jié)構(gòu) ?定義 t[i][j]， 1≤ij≤n為凸子多邊形 {vi1,vi,…,vj} 的最優(yōu)三角剖分所對應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。可以斷言，由 T所確定的這 2個子多邊形的三角剖分也是最優(yōu)的。 最優(yōu)子結(jié)構(gòu)性質(zhì) ?凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結(jié)構(gòu)性質(zhì)。 ?矩陣連乘積中的每個矩陣 Ai對應(yīng)于凸 (n+1)邊形中的一條邊vi1vi。 ?凸多邊形 {v0,v1,…v n1}的三角剖分也可以用語法樹表示。 三角剖分的結(jié)構(gòu)及其相關(guān)問題 ?一個表達式的完全加括號方式相應(yīng)于一棵完全二叉樹，稱為表達式的語法樹。 ?給定凸多邊形 P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù) w。弦將多邊形分割成 2個多邊形 {vi,vi+1,…,v j}和 {vj,vj+1,…v i}。 凸多邊形最優(yōu)三角剖分 ?用多邊形頂點的逆時針序列表示凸多邊形，即 P={v0,v1,…,v n1}表示具有 n條邊的凸多邊形。這種性質(zhì)稱為 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 分析最優(yōu)解的結(jié)構(gòu) ? 特征：計算 A[i:j]的最優(yōu)次序所包含的計算矩陣子鏈 A[i:k]和 A[k+1:j]的次序也是最優(yōu)的。因此算法的計算時間上界為 O(n3)。} } } } A1 A2 A3 A4 A5 A6 30?35 35?15 15?5 5?10 10?20 20?25 ??????????????????????????????1 1 3 7 520213504 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 02021352 5 0 00]5][3[]2][2[m i n]5][2[541531521pppmmpppmmpppmmm算法復(fù)雜度分析： 算法 matrixChain的主要計算量取決于算法中對 r，i和 k的 3重循環(huán)。 if (t m[i][j]) { m[i][j] = t。 k j。 s[i][j] = i。 i++) { int j=i+r1。 r++) for (int i = 1。 for (int
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1