文章基本信息

标题：Matrix-Chain Multiplication Using Greedy and Divide-Conquer approach
本地全文：下载
作者：Raghav Lakhotia ; Sanjeev Kumar ; Rishabh Sood 等
期刊名称：International Journal of Computer Trends and Technology
电子版ISSN：2231-2803
出版年度：2015
卷号：23
期号：2
页码：65-72
DOI：10.14445/22312803/IJCTT-V23P115
出版社：Seventh Sense Research Group
摘要：Matrix Chain Multiplication is a famous application of optimization problem and is used widely in signal processing and network industry for routing. The crux of the solution lies in minimizing the cost or minimizing the number of arithmetic operations required to multiply out the matrices. A topdown dynamic approach is a wellknown solution for this problem which helps to determine the minimal cost required to perform the required multiplication of the matrices. The dynamic solution bears time complexity of the order � .The authors in this paper present a greedy approach to find the optimal computation order of matrix chain multiplication. This approach provides the minimum cost required to compute the required result in a runtime of the order � as compared to the dynamic approach runtime of � . Although the end result i.e. the matrix obtained after the chain multiplication provided by theapproaches, the proposed approach and the dynamic approach is the same.
关键词：Matrix Chain Multiplication; Dynamic Approach; Greedy Approach.