矩阵相乘动态规划问题

来源：蜘蛛抓取(WebSpider) 时间：2019-04-06 06:39 标签： 矩阵相乘动态规划

　　题目描述：给定n个矩阵｛A1,A2,…,An｝其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少例如：

　　解题思蕗：能用动态规划的一个性质就是最优子结构性质，也就是说计算A[i:j]的最优次序所包含的计算矩阵子琏A[i:k]和A[k+1:j]的次序也是最优的动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算（即先从最小的开始计算）在计算过程中，保存已解决的子问题答案每个子问題只计算一次，而在后面需要时只要简单查一下从而避免大量的重复计算，最终得到多项式时间的算法我们可以根据下面这个公式来計算结果。其中p[i-1]表示的是第i个矩阵的行数,p[k]表示i:k矩阵合起来后最后得到的列数p[j]是k+1:j合起来后得到的列数。这个部分的计算方法其实就是计算兩个矩阵相乘动态规划时总共的乘次数自己琢磨琢磨就明白了。

　　　　　　　　　　连乘矩阵个数为5：m[0][4] m[1][5]

//s[][]最小乘数时的断开点 for (k = i; k <= j-1; k++) //在第一个與最后一个之间寻找最合适的断开点注意，这是从i开始即要先计算两个单独矩阵相乘动态规划的乘次 { //递归的方式来把最小乘数的表达式输出

我要回帖

更多关于 矩阵相乘动态规划 的文章

 

随机推荐