※ 引述《sky810675 (KKMAN)》之銘言：
: 不好意思!想請問說以下有4個矩陣!A3*5,B5*2,C2*4,D4*6
: 其中:
: A(BC)=(5*2*4)+(3*5*4)=40+60=100
: (AB)C=(3*5*2)+(3*2*4)=30+24=54
: 想知道為什麼A(BC)與(AB)C會得到這樣的分解運算呢?
: 不好意思><因為已經想很久一直找不出規律性!謝謝
: http://140.113.149.29/blog/?p=8666
: 雖然有連結!但前面那個還是不太懂
其實你可以看看在求BC的過程中,要用到幾次乘法:
B: 5 X 2
C: 2 X 4
你如果下去試,應該可以知道得到 (BC) (矩陣BC的第j行) , 1<=j<=4
j
需要做 5X2 次乘法
Ex: [ 1 1]
[ 1 1] [1 1 1 1]
B = [ 1 1] , C = [1 1 1 1]
[ 1 1]
[ 1 1]
[1*1+1*1] =>2次
=> (BC) = [1*1+1*1] =>2次
1 [1*1+1*1] =>2次 => 共10次
[1*1+1*1] =>2次
[1*1+1*1] =>2次
得到BC,要求出 (BC) (BC) (BC) (BC) ,每個都要做10次乘法
1, 2, 3, 4
則要10*4=40次乘法,其實就是 5*2*4,並得到一個 大小為 5 X 4的矩陣
如果你理解這個特性的話, 你可以想見 A(BC) 需要 3 X 5 X 4 = 60次乘法
故以上對法的運算量共 40 + 60 = 100
---------------------------------------------------------------------
另一方面,如果是 先算AB,再乘以C呢?
A: 3 X 5
B: 5 X 2
5
(AB) = Σ a b => 每求一個元素要做5次
ij k=1 ik kj
你可以想見 AB的大小是 3 X 2 = 6
所以需要 5 X 6 = 30 = 3 X 5 X 2 次乘法
AB : 3 X 2
C : 2 X 4
如果你現在有一點勇氣,應該可以馬上回答: (AB)C要做 3 X 2 X 4 = 24乘法
Rule: 左矩陣的Row size X 兩矩陣共同的 size X 右矩陣的 Column Size
(因為矩陣可乘的條件是:左矩陣的 Column Size = 右矩陣的 Row Size,
又必須在求每一個元素的過程中,走過"兩矩陣共同的 size"次,才能做完,
所以會多中間那一項)
--------------------------------------------------------------------
Note: 這其實是出自演算法的章節: dynamic programming(動態規劃),
它的觀點是: 我們做矩陣連乘時,如果總是從左邊算到右邊,不見得會比從中間某
段算,來的有效率(計算次數未必較少),所以我們希望找出一個演算法,使得
作矩陣連乘的運算次數能夠最少(這裡是著重在做乘法的部分)
那我們發現到矩陣乘法具有結合律,這表示我們不一定要按照順序算過來
要達到這一點必須要:
(1) 找出衡量矩陣運算次數的衡量標準(像這裡是對乘法),
同時要達到最小的規則是什麼
你問的問題,就是在做這件事
(2) 既然我們找到法則了, 那我們要在運算過程中記住這些資訊,
並且不斷的更新(如果找到更好得方法的話),最後應該可以得到
最佳解
=> dynamic progamming的精隨
你可以參考一些演算法課本,像:
(1) Introduction to Algorithms, Third Edition by Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest and Clifford Stein
一般學校都會用這一本,內容很多,但對初學者來說,不算很容易,不過裡面都會先講
演算法的觀點,再去做一些演算法的分析和證明,他的習題必須要你對裡面的內容很
了解,才做得出來
(2) Foundations of Algorithms, Fourth Edition by Richard Neapolitan and
Kumarss Naimipour
有在書局看過一次,覺得也不差
(3) Introduction to the Design and Analysis of Algorithms (2nd Edition) by
Anany Levitin (有中文版)
這一本好像是最好讀的,不過好像不著重分析,但會告訴你演算法的直覺,
另外,會有習題提示,但就不知有沒有幫助了
此外,要了解演算法的思維,必須要有一定的程式經驗,否則你可能會覺得: 雖然
裡面的運算操作很簡單,為什麼還要提出這些演算法? 或者你可能認為,直接作很簡單.
衛門麼要搞得那麼複雜?
以上是我個人的意見,如果有覺得不對,不認同或是要補充的,歡迎盡量提出來
(不過那個網站很多都寫得比我好~~)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.243.175.119
※ 編輯: yueayase 來自: 111.243.175.119 (03/08 00:42)
※ 編輯: yueayase 來自: 111.243.175.119 (03/08 00:49)