作者mqazz1 (无法显示)
站内Prob_Solve
标题[请益] matrix-chain multiplication和Catalan numbers
时间Sat May 29 23:00:59 2010
我在读Cormen的演算法(二版)
有一个地方不是很了解(在书上的333页)
=====================================
解决 n 个矩阵的乘法
所有的括号是 P(n)
P(n) = 1 if n = 1
sum(k=1 to n-1) P(k)P(n-k) if n >= 2
如果是 4 个矩阵相乘
P(4)带入这个递回式的结果是5
=> 四个矩阵有5种方法相乘
(A1(A2(A3A4)))
(A1((A2A3)A4))
((A1A2)(A3A4))
((A1(A2A3))A4)
(((A1A2)A3)A4)
然後Catalan number的公式 (2n)! / (n+1)!n!
这边用n=4带入会得到14
n=3会得到5
所以是要求n个矩阵相乘，在Catalan number要代n-1，在P(n)要代n吗?
谢谢
=====================================
这是Catalan number 维基百科的介绍
http://zh.wikipedia.org/zh-tw/Catalan_number
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.30.220
1F：→ tkcn:我的看法和你的结论相同 05/30 00:02
2F：推 FTT:n个矩阵连乘的组合 可由排n-1组括号进去来表达 05/30 21:23
3F：→ FTT:所以算Catalan number才会代n-1进去呀 05/30 21:23