course6动态规划dynamicprogramming

course6动态规划dynamicprogramming内容摘要：

1 22 ▓ 連鎖矩陣相乘 (Chained Matrix Multiplication) 假設我們要將一個 2 3 的矩陣乘上一個 3 4 的矩陣：  所產生的結果為一個 2 4的矩陣  結果矩陣中的每一個元素都必須經過 3次乘法的運算  因為結果矩陣中有 2 4 = 8個元素，因此總共需要的乘法次數為： 一般來說，一個 i j matrix 乘上一個 j k matrix ，總共需要的乘法次數為： 23  Note: n個 matrix相乘有 種可能的配對組合 (括號方式 )  Ex: 以下有四個矩陣相乘 : 由 Note得知共有五種不同的相乘順序，不同的順序需要不同的乘法次數： 其中，以第三組是最佳的矩陣相乘順序。 nnnC n   1 )1(2124  Chained Matrix Multiplication:  Def: 給一 Matrix Chain: A1, A2, …, An，求此 Chain所需之 乘法次數為 最少 之括號方式 (即 : 最佳的矩陣乘法組合方式 )。 若 Ai, Ai+1, …, Aj 在某組合方式所需的乘法次數為最小 (最佳 )，則必存在一個 k，使得 Ai, Ai+1, …, Ak 和 Ak+1, Ak+2, …, Aj皆為最佳。 ((Ai Ai+1 … Ak )(Ak+1 Ak+2 …, Aj)) 最佳組合 最佳子組合 最佳子組合 25  Matrix Chain的遞迴式 此遞迴式涵蓋以下兩個規則：  M[i][j] = 矩陣 Ai乘到 Aj所需的最少乘法數 (其中 i j)  M[i][i] = 0  ji if }dddj]1,M [ kk]{ M [ i ,m i nji if 0 j]M [ i ,jk1i1jki26  Chained Matrix Multiplication 問題的演算法需有兩個表格和一個主要變數 :  M[i, j]  記錄多個矩陣相乘 (., Ai  …  Aj)時，所需的 “最少” 乘法次數  P[i, j]  記錄多個矩陣相乘 (., Ai  …  Aj) 所需最少乘法次數之 “最佳乘法順序” 是由哪一個矩陣開始分割  diagonal  主要指出在 Matrix Chain中，每一次 有多少個矩陣要相乘  diagonal = 1  只有 1個矩陣， ∴ 不會執行乘法動作  diagonal = 2  每一次有 2個矩陣要相乘  diagonal = 3  每一次有 3個矩陣要相乘  diagonal = 4  每一次有 4個矩陣要相乘  … 27 28 六個矩陣相乘的最佳乘法順序可以分解成以下的其中一種型式： 第 k個分解型式所需的乘法總數，為前後兩部份 (一為 A1, A2, …, Ak 和 Ak+1, …, A6) 各自所需乘法數目的最小值相加，再加上相乘這前後兩部份矩陣所需的乘法數目。 29  Matrix Chain的遞迴式  Example: A133, A237, A372, A429, A594, 求此五矩陣的最小乘法次數。 Sol: 建立兩陣列 M[1…5, 1…5]及 P[1…4, 2…5]  ji if }dddj]1,M [ kk]{ M [ i ,m i nji if 0 j]M [ i ,jk1i1jkiM 1 2 3 4 5 1 2 3 4 5 P 2 3 4 5 1 2 3 4 30 Case  (When diagonal = 1)  diagonal = 1， ∵ 只有 1個矩陣，∴ 不會執行乘法動作  陣列 M的中間對角線為 0，陣列 P則不填任何數值 Case  (When diagonal 1)  diagonal = 2， 有 2個矩陣相乘  當 i = 1及 j = 2，為 A1及 A2矩陣相乘，此時 : M[1, 2] = M[1,1]+M[2,2]+337 = 63， 其中 A1 及 A2 的分割點 k 如下 : A1A2 M 1 2 3 4 5 1 0 2 0 3 0 4 0 5 0 P 2 3 4 5 1 2 3 4 diagonal = 1 M 1 2 3 4 5 1 0 63 2 0 42 3 0 126 4 0 72 5 0 P 2 3 4 5 1 1 2 2 3 3 4 4 diagonal = 2 分割點 k = 1 31 Case  (When diagonal 1)  diagonal = 3， 有 3個矩陣相乘  當 i = 2及 j = i+diagnal1 = 2+31=4，為 A2至 A4間的所有矩陣相乘，此時 : M 1 2 3 4 5 1 0 63 60 2 0 42 96 3 0 126 128 4 0 72 5 0 P 2 3 4 5 1 1 1 2 2 3 3 3 3 4 4 3k 96,923M [ 4 , 4 ]M [ 2 , 3 ]2k 3 1 5 ,973M [ 3 , 4 ]M [ 2 , 2 ]m i nM [ 2 , 4 ]分割點分割點diagonal = 3 32 Case  (When diagonal 1)  diagonal = 4， 有 4個矩陣  當 i = 1及 j = 4，為 A1至 A4間的所有矩陣相乘，此時 : M 1 2 3 4 5 1 0 63 60 114 2 0 42 96 138 3 0 126 128 4 0 72 5 0 P 2 3 4 5 1 1 1 3 2 2 3 3 3 3 3 4 4 3k 1 1 4 ,923M [ 4 , 4 ]M [ 1 , 3 ]2k 3 7 8 ,973M [ 3 , 4 ]M [ 1 , 2 ]1k 1 7 7 ,933M [ 2 , 4 ]M [ 1 , 1 ]m i nM [ 1 , 4 ]分割點分割點分割點diagonal = 4 33 Case  (When diagonal 1)  diagonal = 5， 有 5個矩陣  當 i =。