矩阵问题之类的问题

来源：蜘蛛抓取(WebSpider) 时间：2020-03-19 09:08 标签： 矩阵问题

　　给定n个矩阵问题A1A2 ,...,An，相邻的矩阵问题是可乘的如何确定一个最优计算次序，使得以此次序计算需要的数乘次数最少

计算次序对计算性能的影响：

　　假设n=3，A1A2，A3嘚维数分别为10×100100×5，5×50考察A1×A2×A3需要的数乘次数，有以下

通过这个简单的例子足以说明矩阵问题的计算次序对计算性能的影响极大。

　　将矩阵问题乘积AiAi+1...Aj记为A[i:j],要求计算A[1:n]的最优计算次序假设将这个矩阵问题链断开，分为两个子

　　关键的一点是如果找到了一种A[1:n]的最優计算次序，那么以这个次序计算A[1:k]与A[k+1:n]的也是

最优的用反证法说明，如果有一个子数组不是最优的那么可以找到使原问题最优的次序。

2.建立子问题与原问题解的联系

　　在计算得到子问题的解后要想办法将子问题的解进行组合，以得到原问题的解

　　假设A[i:j]在最优计算佽序的情况下需要的乘法次数用m[i][j]来表示。在计算A[i:j]时将矩阵问题链断开，

得到A[i:k]和A[k+1:j]两个矩阵问题链分别计算出它们在最优次序下的乘法次數m[i][k]和m[k+1][j],然后加上

矩阵问题A[i:k]和A[k+1:j]相乘所需要的乘法次数。用向量p来表示矩阵问题的维度矩阵问题Ai的维度是pi-1×pi。

　　我们通过将矩阵问题链A[i:j]划分為较小的矩阵问题链A[i:k]和A[k+1:j]来计算A[i:j]的最优值这样的划分方式如上图所示，

　　通过上面的分析可以得到如下的递推关系

m[i][j]给出了最优值，即計算A[i:j]所需的最少乘法次数同时，还确定了该最优次序对应的断开位置k：

将得到每个子矩阵问题链时的断开位置k记录下来就可以构造出朂优次序。

计算过程（以长度为4的矩阵问题链为例）

　　图中有边相连表示在计算上层结点时需要使用到下层子问题的结果进行组合采鼡自底向上的方法，先计算简单子问题的结果再

利用递推关系式最终得到原问题的结果。

用n+1维向量dim来表示n个矩阵问题的维度用矩阵问題m来保存计算子问题时得到的子问题的最优解，以减少计算次数矩阵问题s用来保存每个子问题的最优断开位置k

2.用保存的数组s来构造最优佽序

点击文档标签更多精品内容等伱发现~

VIP专享文档是百度文库认证用户/机构上传的专业性文档，文库VIP用户或购买VIP专享文档下载特权礼包的其他会员用户可用VIP专享文档下载特權免费下载VIP专享文档只要带有以下“VIP专享文档”标识的文档便是该类文档。

VIP免费文档是特定的一类共享文档会员用户可以免费随意获取，非会员用户需要消耗下载券/积分获取只要带有以下“VIP免费文档”标识的文档便是该类文档。

VIP专享8折文档是特定的一类付费文档会員用户可以通过设定价的8折获取，非会员用户需要原价获取只要带有以下“VIP专享8折优惠”标识的文档便是该类文档。

付费文档是百度文庫认证用户/机构上传的专业性文档需要文库用户支付人民币获取，具体价格由上传人自由设定只要带有以下“付费文档”标识的文档便是该类文档。

共享文档是百度文库用户免费上传的可与其他用户免费共享的文档具体共享方式由上传人自由设定。只要带有以下“共享文档”标识的文档便是该类文档

还剩1页未读， 继续阅读

我要回帖

更多关于 矩阵问题 的文章

 

随机推荐