course6動(dòng)態(tài)規(guī)劃dynamicprogramming(編輯修改稿)
2024-11-29 17:53 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 1 22 ▓ 連鎖矩陣相乘 (Chained Matrix Multiplication) ?假設(shè)我們要將一個(gè) 2 3 的矩陣乘上一個(gè) 3 4 的矩陣： ? 所產(chǎn)生的結(jié)果為一個(gè) 2 4的矩陣 ? 結(jié)果矩陣中的每一個(gè)元素都必須經(jīng)過 3次乘法的運(yùn)算 ? 因?yàn)榻Y(jié)果矩陣中有 2 4 = 8個(gè)元素，因此總共需要的乘法次數(shù)為： ?一般來(lái)說(shuō)，一個(gè) i j matrix 乘上一個(gè) j k matrix ，總共需要的乘法次數(shù)為： 23 ? Note: n個(gè) matrix相乘有 種可能的配對(duì)組合 (括號(hào)方式 ) ? Ex: 以下有四個(gè)矩陣相乘 : 由 Note得知共有五種不同的相乘順序，不同的順序需要不同的乘法次數(shù)： 其中，以第三組是最佳的矩陣相乘順序。 nnnC n ???????? ???? 1 )1(2124 ? Chained Matrix Multiplication: ? Def: 給一 Matrix Chain: A1, A2, …, An，求此 Chain所需之 乘法次數(shù)為 最少 之括號(hào)方式 (即 : 最佳的矩陣乘法組合方式 )。 ?若 Ai, Ai+1, …, Aj 在某組合方式所需的乘法次數(shù)為最小 (最佳 )，則必存在一個(gè) k，使得 Ai, Ai+1, …, Ak 和 Ak+1, Ak+2, …, Aj皆為最佳。 ((Ai Ai+1 … Ak )(Ak+1 Ak+2 …, Aj)) 最佳組合 最佳子組合 最佳子組合 25 ? Matrix Chain的遞迴式 ?此遞迴式涵蓋以下兩個(gè)規(guī)則： ? M[i][j] = 矩陣 Ai乘到 Aj所需的最少乘法數(shù) (其中 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 問題的演算法需有兩個(gè)表格和一個(gè)主要變數(shù) : ? M[i, j] ? 記錄多個(gè)矩陣相乘 (., Ai ? … ? Aj)時(shí)，所需的 “最少” 乘法次數(shù) ? P[i, j] ? 記錄多個(gè)矩陣相乘 (., Ai ? … ? Aj) 所需最少乘法次數(shù)之 “最佳乘法順序” 是由哪一個(gè)矩陣開始分割 ? diagonal ? 主要指出在 Matrix Chain中，每一次 有多少個(gè)矩陣要相乘 ? diagonal = 1 ? 只有 1個(gè)矩陣， ∴ 不會(huì)執(zhí)行乘法動(dòng)作 ? diagonal = 2 ? 每一次有 2個(gè)矩陣要相乘 ? diagonal = 3 ? 每一次有 3個(gè)矩陣要相乘 ? diagonal = 4 ? 每一次有 4個(gè)矩陣要相乘 ? … 27 28 ?六個(gè)矩陣相乘的最佳乘法順序可以分解成以下的其中一種型式： ?第 k個(gè)分解型式所需的乘法總數(shù)，為前後兩部份 (一為 A1, A2, …, Ak 和 Ak+1, …, A6) 各自所需乘法數(shù)目的最小值相加，再加上相乘這前後兩部份矩陣所需的乘法數(shù)目。 29 ? Matrix Chain的遞迴式 ? Example: A13?3, A23?7, A37?2, A42?9, A59?4, 求此五矩陣的最小乘法次數(shù)。 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個(gè)矩陣，∴ 不會(huì)執(zhí)行乘法動(dòng)作 ? 陣列 M的中間對(duì)角線為 0，陣列 P則不填任何數(shù)值 Case ? (When diagonal 1) ? diagonal = 2， 有 2個(gè)矩陣相乘 ? 當(dāng) i = 1及 j = 2，為 A1及 A2矩陣相乘，此時(shí) : M[1, 2] = M[1,1]+M[2,2]+3?3?7 = 63， 其中 A1 及 A2 的分割點(diǎn) 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 分割點(diǎn) k = 1 31 Case ? (When diagonal 1) ? diagonal = 3， 有 3個(gè)矩陣相乘 ? 當(dāng) i = 2及 j = i+diagnal1 = 2+31=4，為 A2至 A4間的所有矩陣相乘，此時(shí) : 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 ]分割點(diǎn)分割點(diǎn)diagonal = 3 32 Case ? (When diagonal 1) ? diagonal = 4， 有 4個(gè)矩陣 ? 當(dāng) i = 1及 j = 4，為 A1至 A4間的所有矩陣相乘，此時(shí) : 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 ]分割點(diǎn)分割點(diǎn)分割點(diǎn)diagonal = 4 33 Case ? (When diagonal 1) ? diagonal = 5， 有 5個(gè)矩陣 ? 當(dāng) i =
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1