(Greedy Method) 各个击破(Divide-and-Conquer).PPT

連鎖矩陣相乘 連鎖矩陣相乘 因為結合律成立，故 n 個矩陣相乘，最多有 種乘法方式。例如：4 個矩陣相乘 A, B, C, D 會有 5 種乘法方式 A (B (C D)) (A B) (C D) A ((B C) D) ((A B) C) D (A (B C)) D 每種方式所需乘法計算的次數並不相同，如何才能有最少的相乘次數？ 連鎖矩陣相乘 若用暴力法 (Brute-force) 解，時間複雜度為 Ω(4n/n3/2) 若Ai, Ai+1, …, Aj 在某組合方式所需的乘法次數為最小 (最佳)，則必存在一個k，使得Ai, Ai+1, …, Ak 和Ak+1, Ak+2, …, Aj皆為最佳。 ((Ai Ai+1 … Ak )(Ak+1 Ak+2 …, Aj)) 最佳組合 最佳子組合 最佳子組合 連鎖矩陣相乘 * Matrix Chain的遞迴式 此遞迴式涵蓋以下兩個規則： Ni, j = 矩陣 Ai 乘到 Aj 所需的最少乘法數 (其中 i j) Ni,i = 0 di 表示矩陣之維度(列或行) 第1個矩陣維度應為 d0 × d1，第2個矩陣維度應為 d1 × d2 ，最後一個矩陣維度應為dn-1 × dn 連鎖矩陣相乘 i j 1 2 3 4 1 0 1200 1200 1232 2 0 720 912 3 0 2880 4 0 A1 A2 A3 A4 A1 A2 A2A3 A3A4 A1 A2A3 A2A3A4 A1 A2A3A4 本例中矩陣編號由 A1 開始，所以矩陣維度也從 d1 × d2 開始 連鎖矩陣相乘 矩陣相乘路徑可以另外設定一個陣列 Pi,j 記錄每次選擇的分割點，即 k 值，再由最佳解反推回去即可。 i j 1 2 3 4 1 0 1200 1200 1232 2 0 720 912 3 0 2880 4 0 i j 1 2 3 4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 Ni,j Pi,j Algorithm MatrixChain(d0, … , dn) Input: Sequence d0, … , dn of integers. Output: for i, j = 0, … , n-1, the minimum number of multiplications Ni, j need to compute the product Ai × Ai+1 × … × Aj, where Ak is a dk × dk+1 matrix for i ? 0 to n-1 do Ni, i ? 0 for b ? 1 to n-1 do for i ? 0 to n-b-1 do j ? i+b Ni, j ? +∞ for k ? i to j-1 do Ni, j ? min { Ni, j , Ni, k + Nk+1, j + di dk+1 dj+1} 0/1 Knapsack Problem 有 N 種物品，每種都只有1個。其中第 i 種物品(i=1..N)，價值為 c[i]，重量為 w[i]。今有一個背包，可以負重 W，問如何可以得到最大價值 V？ 假設有一個背包可以負重 10 公斤，有5個物品，價值分別為 10, 20, 30, 40, 50，重量分別為 2, 4, 3, 1, 5，問可以取到的最大價值為何？ 0/1 Knapsack Problem P[i, j] 有 i 種物品，背包可負重 j，所獲得最大價值。 初始值 P[0, 0] = 0 初始值 P[0, 1] = … = P[0,10] = -1 恰好裝滿 P[0, 1] = … = P[0, 10] = 0 不一定要裝滿 0/1 Knapsack Problem P[i, j] = Max{ P[i-1, j] , P[i-1, j-w[i] ] + c[i] } 對 i 項物品 不取 此時背包最大價值為 P[i-1, j] i 2公斤 5 P[i, 10] = P[i-1, 10] 取 P[i-1, j-w[i] ] + c[i] i 2公斤 5 P[i, 10] = P[i-1, 8] + 5 0/1 Knapsack Problem for (int i=0; i 物品的數量; i++) for (int j=背包負重; j0; j--) P[i, j] = Max{ P[i-1, j] , P[i-1, j-w[i]