计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (17): 39-40.DOI: 10.3778/j.issn.1002-8331.2010.17.011

• 研究、探讨 • 上一篇    下一篇

一种改进的小矩阵连乘算法

和 力,吴丽贤   

  1. 韩山师范学院 数学与信息技术系,广东 潮州 521041
  • 收稿日期:2008-12-18 修回日期:2009-03-05 出版日期:2010-06-11 发布日期:2010-06-11
  • 通讯作者: 和 力

Improved serial multiplication algorithm for small matrixes

HE Li,WU Li-xian   

  1. Department of Mathematics and Information Technology,Hanshan Teachers’ College,Chaozhou,Guangdong 521041,China
  • Received:2008-12-18 Revised:2009-03-05 Online:2010-06-11 Published:2010-06-11
  • Contact: HE Li

摘要: 首先引入了矩阵的连乘优先因子,接着采用连乘优先因子最小的贪心选择策略,提出了最小连乘因子优先算法。它确定125的连乘次序不一定是最优次序,但在确定连乘次序方面比动态规划法花费的时间和空间少。最后通过实例对比测试,表明该算法在计算小矩阵连乘时,总体效率优于动态规划法。

关键词: 矩阵连乘, 最小连乘因子优先算法, 动态规划法, 贪心算法

Abstract: Priority factor of serial matrix multiplication is presented in the first part of the paper.Then adopting greedy selection strategy based on minimum priority factor of serial matrix multiplication,minimum serial multiplication factor first algorithm is put forward.Computation sequence obtained from this algorithm is not always optimal,but it spends less time and space than dynamic programming.Finally,the experiment result indicates that the proposed algorithm is more effective than dynamic programming for small matrixes on the whole.

Key words: serial matrix multiplication, minimum serial multiplication factor first algorithm, dynamic programming, greedy algorithm

中图分类号: