Dynamic Programming II Michael Tsai 2013/10/10

連串矩陣相乘問題 題目: 求 𝐴 1 𝐴 2 … 𝐴 𝑛 矩陣相乘之解. 𝐴 1 .cols= 𝐴 2 .rows 𝐴 1 𝐴 2 …… 題目: 求 𝐴 1 𝐴 2 … 𝐴 𝑛 矩陣相乘之解. 𝐴 1 .cols= 𝐴 2 .rows 𝐴 1 𝐴 2 …… 𝐴 3 𝐴 𝑛 𝐴 4 𝐴 1 and 𝐴 2 are compatible. Matrix multiplication is associative. (( A 1 𝐴 2 𝐴 3 )𝐴 4 ) ( A 1 𝐴 2 𝐴 3 )𝐴 4 A 1 𝐴 2 𝐴 3 𝐴 4 𝐴 1 ( 𝐴 2 𝐴 3 𝐴 4 ) 𝐴 1 𝐴 2 𝐴 3 𝐴 4 以上算出來答案都一樣

q r 連串矩陣相乘問題 p 𝐴 q 𝐵 Matrix-Multiply(A,B) if A.columns != B.rows error “incompatible dimensions” else let C be a new A.rows x B.cols matrix for i=1 to A.rows for j=1 to B.cols 𝑐 𝑖𝑗 =0 for k=1 to A.cols 𝑐 𝑖𝑗 = 𝑐 𝑖𝑗 + 𝑎 𝑖𝑘 ∙ 𝑏 𝑘𝑗 return C p r q 主要花費時間在這邊! 共花費pqr次乘法的時間

看一個例子 𝐴 1 𝐴 2 𝐴 3 花費之乘法數目=10×100×5+10×5×50=7500 𝐴 1 𝐴 2 𝐴 3 花費之乘法數目=10×100×5+10×5×50=7500 𝐴 1 𝐴 2 𝐴 3 花費之乘法數目=100×5×50+10×100×50=75000 差十倍!!

連串矩陣相乘問題-正式版 給一連串的矩陣 𝐴 1 , 𝐴 2 ,…, 𝐴 𝑛 , 其中矩陣 𝐴 𝑖 的大小為 𝑝 𝑖−1 × 𝑝 𝑖 (𝑖=1, 2,…,𝑛), 找出一種乘法可以使計算時的乘法數目最少 沒有真的要算結果, 而只是找出能最快算出結果的方法. 因為算”怎麼算比較快”多花的時間, 比”用爛方法直接算”多花的時間少很多 𝑝 4 𝑝 3 𝑝 1 𝑝 𝑛 𝑝 2 𝑝 𝑛−1 𝑝 1 …… 𝑝 0 𝐴 1 𝐴 2 𝑝 2 𝐴 3 𝐴 𝑛 𝑝 3 𝐴 4

暴力法有多暴力 全部到底有幾種算法呢? P(n): 代表n個矩陣相乘共有幾種算法 用遞迴定義: P(n)之解為Catalan numbers, Ω 4 𝑛 𝑛 3 2 , or is also Ω 2 𝑛 𝑃 𝑛 = 1 𝑘=1 𝑛−1 𝑃 𝑘 𝑃(𝑛−𝑘) if 𝑛=1, if 𝑛≥2. 假設先這樣分: 𝐴 1 𝐴 2 … 𝐴 𝑘 𝐴 𝑘+1 𝐴 𝑘+2 … 𝐴 𝑛

所以不耍暴力了. 使用dynamic programming 正規步驟: 找出最佳解的”結構” 使用遞迴來定義最佳解的花費 計算最佳解的花費 使用已經計算的資訊來構築最佳解

找出最佳解的”結構” 𝑖≤𝑗 在k切一刀 𝐴 𝑖 𝐴 𝑖+1 … 𝐴 𝑘 𝐴 𝑘+1 𝐴 𝑘+2 … 𝐴 𝑗 𝑖≤𝑘<𝑗 總花費= 𝐴 𝑖 .. 𝐴 𝑘 的花費+ 𝐴 𝑘+1 .. 𝐴 𝑗 的花費+把 𝐴 𝑖 .. 𝐴 𝑘 和 𝐴 𝑘+1 .. 𝐴 𝑗 乘起來的花費 最佳解的結構: 假設有 𝐴 𝑖 .. 𝐴 𝑗 的最佳解, 此一方法為在k切一刀. 則在此 𝐴 𝑖 .. 𝐴 𝑗 最佳解中, 𝐴 𝑖 .. 𝐴 𝑘 的相乘方法一定是 𝐴 𝑖 .. 𝐴 𝑘 的最佳相乘方法 假設 𝐴 𝑖 .. 𝐴 𝑘 不是最佳解, 則我們可以在 𝐴 𝑖 .. 𝐴 𝑗 中把 𝐴 𝑖 .. 𝐴 𝑘 換成更好的方法, 則可以找到一個更好的 𝐴 𝑖 .. 𝐴 𝑗 的相乘方法矛盾. 子問題的最佳解可以導出大問題的最佳解! 最後結論: 分成兩個子問題, 並嘗試所有可以切分的地方(k值)

使用遞迴來定義最佳解的花費 遞迴定義:使用子問題最佳解的cost來定義大問題最佳解的cost 定義: 𝑚[𝑖,𝑗]為 𝐴 𝑖 .. 𝐴 𝑗 所需花的最少乘法數 𝐴 𝑖..𝑘 𝐴 𝑘+1..𝑗 所花乘法數= 𝑝 𝑖−1 𝑝 𝑘 𝑝 𝑗 𝐴 𝑗 .cols= 𝑝 𝑗 𝐴 𝑘 .cols= 𝑝 𝑘 𝐴 𝑖 .rows= 𝑝 𝑖−1 𝐴 𝑖..𝑘 𝐴 𝑘+1..𝑗 𝐴 𝑘+1 .rows= 𝑝 𝑘

使用遞迴來定義最佳解的花費 𝑚 𝑖,𝑗 =𝑚 𝑖,𝑘 +𝑚 𝑘+1,𝑗 + 𝑝 𝑖−1 𝑝 𝑘 𝑝 𝑗 但是我們不知道最佳解中的k的值 𝑚 𝑖,𝑗 =𝑚 𝑖,𝑘 +𝑚 𝑘+1,𝑗 + 𝑝 𝑖−1 𝑝 𝑘 𝑝 𝑗 但是我們不知道最佳解中的k的值 因此我們必須找所有𝑘=𝑖,𝑖+1,…,𝑗−1 最後版本: 𝑚 𝑖,𝑗 = 0 min 𝑖≤𝑘<𝑗 {𝑚 𝑖,𝑘 +𝑚 𝑘+1,𝑗 + 𝑝 𝑖−1 𝑝 𝑘 𝑝 𝑗 } if 𝑖=𝑗, if 𝑖<𝑗.

計算最佳解的花費 純recursive解法: exponential time 使用前面教的Bottom-up填表方法: 每個不同的subprogram僅需解1次 有幾個不同的問題? 1≤𝑖≤𝑗≤𝑛, 幾個i和j的組合? 答案: 𝑛 2 +n=Θ 𝑛 2 𝑖≠𝑗 𝑖=𝑗

計算最佳解的花費 如何決定填表的順序呢? (這次有i,j兩個變數) 𝑚 𝑖,𝑗 = 0 min 𝑖≤𝑘<𝑗 {𝑚 𝑖,𝑘 +𝑚 𝑘+1,𝑗 + 𝑝 𝑖−1 𝑝 𝑘 𝑝 𝑗 } if 𝑖=𝑗, if 𝑖<𝑗. 𝑘−𝑖+1個矩陣相乘 𝑗−𝑘個矩陣相乘 都小於𝑗−𝑖+1個 我們可以把j-i+1(也就是要相乘的matrix個數) 當作problem size的定義

計算最佳解的花費 n=p.length-1 let m[1..n,1..n] and s[1..n-1,2..n] be new tables for i=1 to n m[i,i]=0 for l=2 to n for i=1 to n-l+1 j=i+l-1 m[i,j]=∞ for k=i to j-1 q=m[i,k]+m[k+1,j]+ p i−1 𝑝 𝑘 𝑝 𝑗 if q<m[i,j] m[i,j]=q s[i,j]=k return m and s 邊界條件先設好. 大problem的解只會用到小problem的解.因此慢慢往上長. 把同樣problem size的所有i,j組合都依序做過 使用遞迴式找出最佳切點k Θ( 𝑛 3 )

計算最佳解的花費 用一個例子來trace code比較快 Matrix Dimension 30 x 35 35 x 15 15 x 5

使用已經計算的資訊來構築最佳解 前面只印出了花費, 不是真正的解 怎麼乘才是最後的解 使用s陣列的資訊

使用已經計算的資訊來構築最佳解 Print-Optimal-Parens(s,i,j) if i==j print 𝐴 𝑖 else print “(“ Print-Optimal-Parens(s,i,s[i,j]) Print-Optimal-Parens(s,s[i,j]+1,j) print “)”

使用已經計算的資訊來構築最佳解 所以該怎麼括?

看了兩個例子以後… 問: 一個問題要有什麼要件才能使用dynamic programming? 答: Optimal substructure Overlapping Subproblems

什麼是Optimal substructure? Definition: A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. 怎麼尋找optimal substructure呢?

怎麼尋找optimal substructure呢? 要得到問題的解答有許多選擇(砍在哪邊, 切在哪邊), 而做這個選擇之後, 我們有一些subproblem要解決. 我們假設對於一個問題, 我們可以找到那個選擇 知道這個選擇以後, 我們找出哪個subproblem可以被拿來應用, 及剩下的問題(沒有對應到subproblem的)怎麼解決 證明大問題的最佳解中可以直接應用(剪下貼上)子問題的最佳解.

Optimal substructure越簡單越好 𝑟 𝑖 =? 𝑟 𝑛−𝑖 =? versus 這一段砍下來就不再砍成更小的了(拿去賣) 這一段是subproblem, 找遞迴朋友去解 𝑝 𝑖 𝑟 𝑖 =?

Optimal substructure越簡單越好 假設把問題定義成 𝐴 1 … 𝐴 𝑗 就好 (少一個變數) 1≤𝑗 在k切一刀 𝐴 1 𝐴 𝑖+1 … 𝐴 𝑘 𝐴 𝑘+1 𝐴 𝑘+2 … 𝐴 𝑗 1≤𝑘<𝑗 此不為一個子問題! 此為一個子問題 除非k一直都是j-1, 否則…

Optimal substructure的變化 原始問題的最佳解用了多少個子問題 大問題有多少選擇(選擇用不同的子問題們來獲得最佳解) 大略來說, 以上兩者決定dynamic programming algorithm的執行時間. (之前說的Subproblem graphs是另外一種算法) 多少個子問題 有多少選擇 執行時間 鐵條資源回收 Θ(𝑛) n 𝑂 𝑛 2 連串矩陣相乘 Θ( 𝑛 2 ) n-1 𝑂 𝑛 3

複習: Overlapping Subproblems 舉個例子: 連串矩陣問題的遞迴樹 1..3 1..1 2..3 1..2 3..3 2..2 3..3 1..1 2..2 橘色的是overlap的部分!

例子: 有沒有optimal substructure 給一個graph 𝐺= 𝑉,𝐸 . 𝑢,𝑣∈𝑉. Edge沒有weight. 問題1:找出𝑢→𝑣沒有loop最短路徑. 問題2:找出𝑢→𝑣沒有loop最長路徑. 問題1有沒有optimal substructure? 假設找到𝑢到𝑣的最短路徑p, 則我們可以將其分解為𝑢 𝑝 1 𝑤 𝑝 2 𝑣 (𝑤可以是𝑢或𝑣). 則其中 𝑝 1 一定是𝑢到𝑤的最短路徑. 不然的話, 我們可以找到一個 𝑝 1 ′比 𝑝 1 還短的𝑢到𝑤路徑, 那麼 𝑝 1 ′和 𝑝 2 組合起來就變成一條比p更短的𝑢到𝑣路徑 (矛盾)

例子: 有沒有optimal substructure 沒有! 來舉一個反例. 𝑞到𝑡的最長路徑: 𝑞→𝑟→𝑡 但是𝑞到𝑟的最長路徑為𝑞→𝑠→𝑡→𝑟 並不是𝑞到𝑡的最長路徑中間的一部分! 𝑟到𝑡的最長路徑為𝑟→𝑞→𝑠→𝑡 也不是q到𝑡的最長路徑中間的一部分! q r s t

例子: 有沒有optimal substructure 為什麼問題1和問題2相差這麼多? 問題2缺乏”獨立性”(subproblem的解互相之間不會影響) 𝑢 𝑝 1 𝑤 𝑝 2 𝑣出現在 𝑝 1 的vertex就不能出現在 𝑝 2 (否則就會有loop了) subproblem的解互相影響! 問題1有”獨立性” 在最短路徑𝑢 𝑝 1 𝑤 𝑝 2 𝑣中, 出現在 𝑝 1 的vertex本來就不可能出現在 𝑝 2 假設 𝑝 1 , 𝑝 2 中除了w以外出現了一個一樣的vertex x. 則可以將最短路徑拆解成𝑢 𝑝 𝑢𝑥 𝑥 𝑝 𝑥𝑤 𝑤 𝑝 𝑤𝑥 𝑥 𝑝 𝑥𝑣 𝑣. 因為x和w不同, 所以 |𝑝 𝑥𝑤 ≥1, |𝑝 𝑤𝑥 ≥1. 則 𝑝 𝑢𝑥 和 𝑝 𝑥𝑣 變成比原本更短的u到v的路徑 (矛盾)

DNA比對問題 DNA序列可表示為以{A,C,G,T}組合而成的 一字串 𝑆 1 =𝐴𝐶𝐶𝐺𝐺𝑇𝐶𝐺𝐴𝐺𝑇𝐺𝐶𝐺𝐶𝐺𝐺𝐴𝐴𝐺𝐶𝐶𝐺𝐺𝐶𝐶𝐺𝐴𝐴 𝑆 2 =𝐺𝑇𝐶𝐺𝑇𝑇𝐶𝐺𝐺𝐴𝐴𝑇𝐺𝐶𝐶𝐺𝑇𝑇𝐺𝐶𝑇𝐶𝑇𝐺𝑇𝐴𝐴𝐴 比較兩者有多相像?? 親屬關係? 你是我爸?!

DNA比對問題 多相像找出兩者中都出現的最長子序列看最長子序列有多長, 越長越相像 子序列: 簡單的例子: 順序相同 但不一定要連續. 簡單的例子: X=ABCBDAB, Y=BDCABA 子序列之一: BCA 最長共同子序列: BCBA 𝑆 1 =𝐴𝐶𝐶𝐺𝐺𝑇𝐶𝐺𝐴𝐺𝑇𝐺𝐶𝐺𝐶𝐺𝐺𝐴𝐴𝐺𝐶𝐶𝐺𝐺𝐶𝐶𝐺𝐴𝐴 𝑆 2 =𝐺𝑇𝐶𝐺𝑇𝑇𝐶𝐺𝐺𝐴𝐴𝑇𝐺𝐶𝐶𝐺𝑇𝑇𝐺𝐶𝑇𝐶𝑇𝐺𝑇𝐴𝐴𝐴 最長共同子序列=? 答案在課本p.391

DNA比對問題最長共同子序列 問題: 給兩字串𝑋= 𝑥 1 , 𝑥 2 ,…, 𝑥 𝑚 , 𝑌= 𝑦 1 , 𝑦 2 ,…, 𝑦 𝑛 , 找出最長共同子序列. 最長共同子序列=Longest Common Subsequence=LCS 問: 暴力法有多暴力?

暴力法有多暴力? 找出所有X之子序列, 與Y比較檢驗看看是不是Y的子序列. X有幾個子序列? 2 𝑚 個 Running time: Ω( 2 𝑚 )

Dynamic Programming出招 1. 找出Optimal Substructure 先來個小定義, 對𝑋= 𝑥 1 , 𝑥 2 ,…, 𝑥 𝑚 , 𝑋 𝑖 = 𝑥 1 , 𝑥 2 ,…, 𝑥 𝑖 , 0≤𝑖≤𝑚 先證明以下三個小定理. 給定兩字串𝑋= 𝑥 1 , 𝑥 2 ,…, 𝑥 𝑚 , 𝑌= 𝑦 1 , 𝑦 2 ,…, 𝑦 𝑛 , 及𝑍= 𝑧 1 , 𝑧 2 ,…, 𝑧 𝑘 為X和Y的LCS(之一) If 𝑥 𝑚 = 𝑦 𝑚 , then 𝑧 𝑘 = 𝑥 𝑚 = 𝑦 𝑛 and 𝑍 𝑘−1 是 𝑋 𝑚−1 及 𝑌 𝑛−1 的LCS之一 If 𝑥 𝑚 ≠ 𝑦 𝑛 , then 𝑧 𝑘 ≠ 𝑥 𝑚 表示𝑍是 𝑋 𝑚−1 及 𝑌 𝑛 的LCS之一 If 𝑥 𝑚 ≠ 𝑦 𝑛 , then 𝑧 𝑘 ≠ 𝑦 𝑛 表示𝑍是 𝑋 𝑚 及 𝑌 𝑛−1 的LCS之一

(1) Z最後一個字元一定是 𝑥 𝑚 (= 𝑦 𝑛 ), 否則可以把 𝑥 𝑚 加到Z的最後面成為比LCS更長的CS (矛盾) If 𝑥 𝑚 = 𝑦 𝑛 , then (1) 𝑧 𝑘 = 𝑥 𝑚 = 𝑦 𝑛 and (2) 𝑍 𝑘−1 是 𝑋 𝑚−1 及 𝑌 𝑛−1 的LCS之一 (1) Z最後一個字元一定是 𝑥 𝑚 (= 𝑦 𝑛 ), 否則可以把 𝑥 𝑚 加到Z的最後面成為比LCS更長的CS (矛盾) (2) 𝑍 𝑘−1 一定是 𝑋 𝑚−1 和 𝑌 𝑛−1 的LCS. 假設不是, 則可以找到一個長度>k-1的LCS, 但是加上 𝑥 𝑚 = 𝑦 𝑛 這一個字元, 表示可以找到一個 𝑋 𝑚 和 𝑌 𝑛 的LCS長度>k (矛盾) 𝑋 𝑚−1 𝑥 𝑚 𝑌 𝑛−1 𝑦 𝑛 𝑍 𝑘−1 𝑍 𝑘

If 𝑥 𝑚 ≠ 𝑦 𝑛 , then 𝑧 𝑘 ≠ 𝑥 𝑚 表示𝑍是 𝑋 𝑚−1 及 𝑌 𝑛 的LCS之一 假設Z不是 𝑋 𝑚−1 和 𝑌 𝑛 的LCS, 則有W為 𝑋 𝑚−1 和 𝑌 𝑛 的LCS, 長度>k, 則W亦為 𝑋 𝑚 和 𝑌 𝑛 的LCS, 長度>k (矛盾) If 𝑥 𝑚 ≠ 𝑦 𝑛 , then 𝑧 𝑘 ≠ 𝑦 𝑛 表示𝑍是 𝑋 𝑚 及 𝑌 𝑛−1 的LCS之一 證明類似上面2.的證明. 𝑋 𝑚−1 𝑥 𝑚 𝑌 𝑛 𝑍 𝑘−1 𝑍 𝑘

Optimal Substructure 給定兩字串𝑋= 𝑥 1 , 𝑥 2 ,…, 𝑥 𝑚 , 𝑌= 𝑦 1 , 𝑦 2 ,…, 𝑦 𝑛 , 及𝑍= 𝑧 1 , 𝑧 2 ,…, 𝑧 𝑚 為X和Y的LCS(之一) If 𝑥 𝑚 = 𝑦 𝑚 , then 𝑧 𝑘 = 𝑥 𝑚 = 𝑦 𝑛 and 𝑍 𝑘−1 是 𝑋 𝑚−1 及 𝑌 𝑛−1 的LCS之一 If 𝑥 𝑚 ≠ 𝑦 𝑛 , then 𝑧 𝑘 ≠ 𝑥 𝑚 表示𝑍是 𝑋 𝑚−1 及 𝑌 𝑛 的LCS之一 If 𝑥 𝑚 ≠ 𝑦 𝑛 , then 𝑧 𝑘 ≠ 𝑦 𝑛 表示𝑍是 𝑋 𝑚 及 𝑌 𝑛−1 的LCS之一 大問題的解裡面有小問題的解!

Overlapping subproblem 給定兩字串𝑋= 𝑥 1 , 𝑥 2 ,…, 𝑥 𝑚 , 𝑌= 𝑦 1 , 𝑦 2 ,…, 𝑦 𝑛 , 及𝑍= 𝑧 1 , 𝑧 2 ,…, 𝑧 𝑚 為X和Y的LCS(之一) If 𝑥 𝑚 = 𝑦 𝑛 , then 𝑧 𝑘 = 𝑥 𝑚 = 𝑦 𝑛 and 𝑍 𝑘−1 是 𝑋 𝑚−1 及 𝑌 𝑛−1 的LCS之一 If 𝑥 𝑚 ≠ 𝑦 𝑛 , then 𝑧 𝑘 ≠ 𝑥 𝑚 表示𝑍是 𝑋 𝑚−1 及 𝑌 𝑛 的LCS之一 If 𝑥 𝑚 ≠ 𝑦 𝑛 , then 𝑧 𝑘 ≠ 𝑦 𝑛 表示𝑍是 𝑋 𝑚 及 𝑌 𝑛−1 的LCS之一 不同問題需要同樣子問題的解! 𝑋 𝑚−1 和 𝑌 𝑛−1 的𝐿𝐶𝑆 𝑋 𝑚−1 和 𝑌 𝑛 的𝐿𝐶𝑆 𝑋 𝑚 和 𝑌 𝑛−1 的𝐿𝐶𝑆 𝑋 𝑚 和 𝑌 𝑛 的𝐿𝐶𝑆

Dynamic Programming出招 2. 列出遞迴式子 (表示花費) 條件不同, 使用的subproblem不同 if i=0 or j=0 𝑐 𝑖,𝑗 = 0 𝑐 𝑖−1,𝑗−1 +1 max⁡(𝑐 𝑖,𝑗−1 ,𝑐 𝑖−1,𝑗 ) if 𝑖,𝑗>0 and 𝑥 𝑖 = 𝑦 𝑗 if 𝑖,𝑗>0 and 𝑥 𝑖 ≠ 𝑦 𝑗 𝑋 𝑖 and Y j 𝐿𝐶𝑆的長度 兩種選擇

Dynamic Programming出招 3. 計算花費 使用dynamic programming填表 共有多少個entry? Θ(𝑚𝑛) j i 1 2 3 每一格只用到左、 左上、上三格的資訊 使用bottom-up方法 兩層迴圈依序填入即可

例題 B D C A 1 2 3 4 5 6 7 1 2 3 4 5 6 7 A B C D

c紀錄LCS長度, b紀錄選擇結果 邊界起始值 填表: 兩層迴圈 Θ(𝑚𝑛) LCS_Length(X,Y) m=X.length n=Y.length let b[1..m,1..n] and c[0..m,0..n] be new tables for i=1 to m c[i,0]=0 for j=0 to n c[0,j]=0 for j=1 to n if 𝑥 𝑖 == 𝑦 𝑗 c[i,j]=c[i-1,j-1]+1 b[i,j]=左上 elseif c[i-1,j]≥c[i,j-1] c[i,j]=c[i-1,j] b[i,j]=上 else c[i,j]=c[i,j-1] b[i,j]=左 return c and b c紀錄LCS長度, b紀錄選擇結果 邊界起始值 填表: 兩層迴圈 Θ(𝑚𝑛)

Dynamic Programming出招 4. 印出LCS結果 Print_LCS(b,X,i,j) if i==0 or j==0 return if b[i,j]==左上 Print_LCS(b,X,i-1,j-1) print 𝑥 𝑖 elseif b[i,j]==上 Print_LCS(b,X,i-1,j) else Print_LCS(b,X,i,j-1) O(𝑚+𝑛)