串列矩阵相乘.ppt

Dynamic Programming Dynamic Programming Dynamic Programming 串列矩陣相乘 (定義) 串列矩陣相乘(例) Catalan Number 乘法樹 串列矩陣相乘(設計1) 串列矩陣相乘 (設計2) 串列矩陣相乘 (實例) 串列矩陣相乘 (找解) 串列矩陣相乘 (分析) 發展一 DP 演算法的步驟 Elements of Dynamic Programming Longest Common Subsequence (定義) Longest Common Subsequence (設計1) Longest Common Subsequence (設計2) Longest Common Subsequence (例+分析) Optimal Polygon Triangulation Optimal Polygon Triangulation (設計1) Optimal Polygon Triangulation (設計2) 以上為利用此遞迴公式，計算一個有六個矩陣的序列的計算過程。 請注意計算的方式為 j ? i 的值從 1 到 n = 6的方向計算 m[i, j]，因為這個方向為子問題由小到大的方向進行，我們稱這樣的計算方式為由下往上（bottom-up）的方式。 計算完成以後，我們所要求的最佳解的計算量會在 m[1, 6] 的位置，在此例，其值為 348。 根據遞迴公式只能算出最佳解的值（即最少計算量），要求出最佳解的作法，仍須進一步的計算，不過實際上最佳解已隱藏在之前的計算中。 要找到最佳解，我們利用到另一陣列 s[i, j] 。我們讓 s[i, j] = k，其中 k為計算 m[i, j] 時，得到最小值所代入的參數值。 有了 s[i, j]，我們就可以由上往下的方式（top-down）找出最佳的乘法樹（如動畫所示）。 左下方的圖形是以另一種方式來看 LCS 這個問題，將輸入的兩個序列一上一下放好，想辦法在上下兩序列間畫一些線段，越多越好，但這些線段需滿足以下兩個要求： 1. 線段兩端必須是相同的字母 2. 兩線段不可以相交也不可以有相同端點。 本張投影片論證 LCS 問題具 optimal substructure 的特性。 * * * 與 divide-and-conquer 法類似, 是依遞迴方式設計的演算法. 與 divide-and-conquer的最大差別在於子問題間不是獨立的, 而是重疊的. P(n) P(m1) P(m2) …. P(mk) S1 S2 …. Sk S 給一串列的矩陣 ?A1, A2, … , An?, 其中矩陣 Ai 的大小為 pi?1? pi, 找一計算 A1A2…An 乘積的方式, 使得所用 scalar 乘法的計算量為最少. 例： A1 ? A2 ? A3 ? A4 pi :13 5 89 3 34 (A1(A2(A3A4))), (A1((A2A3)A4)), ((A1A2 )( A3A4)), ((A1(A2 A3))A4), ((( A1A2)A3)A4). 總共有 5 種方式來計算這 4 個矩陣的乘積 : (A1(A2(A3A4))), costs = 26418 (A1((A2A3)A4)), costs = 4055 ((A1A2 )( A3A4)), costs = 54201 ((A1(A2 A3))A4), costs = 2856 ((( A1A2)A3)A4), costs = 10582 A1 ? A2 ? A3 ? A4 13 5 89 3 34 (A1(A2(A3A4)))? A1?(A2A3A4) ? A2?(A3A4) ? A3?A4 cost = 13*5*34 + 5*89*34 + 89*3*34 = 2210 + 15130 + 9078 = 26418 For any n, # ways to fully parenthesize the product of a chain of n+1 matrices = # binary trees with n nodes. = # permutations generated from 1 2 … n through a stack. = # n pairs of fully matched parentheses. = n-th Catalan Number = C(2n, n)/(n +1) = ?(4n/