基于动态规划的矩阵连乘最优方法 |
您所在的位置:网站首页 › 动态规划算法计算最优值的公式 › 基于动态规划的矩阵连乘最优方法 |
问题描述: 在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵,B是一个q×r的矩阵,则其乘积C=AB是一个p×r的矩阵。其标准计算公式为: ![]() 由该公式知计算C=AB总共需要pqr次的数乘。 为了说明在计算矩阵连乘积时加括号方式对整个计算量的影响,我们来看一个计算3个矩阵{A1,A2,A3}的连乘积的例子。设这3个矩阵的维数分别为10×100,100×5和5×50。若按第一种加括号方式((A1A2)A3)来计算,总共需要10×100×5+10×5×50=7500次的数乘。若按第二种加括号方式(A1(A2A3))来计算,则需要的数乘次数为100×5×50+10×100×50=75000。第二种加括号方式的计算量是第一种加括号方式的计算量的10倍。由此可见,在计算矩阵连乘积时,加括号方式,即计算次序对计算量有很大影响。 所以,对于给定的相继n个矩阵{A1,A2,…,An}(其中Ai的维数为pi-1×pi ,i=1,2,…,n),如何确定计算矩阵连乘积A1A2…An的一个计算次序(完全加括号方式),使得依此次序计算矩阵连乘积需要的数乘次数最少,即所谓的矩阵连乘积的最优计算次序问题。 思路: 采用动态规划:动态规划算法的基本思想是将待求解问题分成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,动态规划法经分解得到的子问题往往不是相互独立的,前一子问题的解为后一子问题的解提供有用的信息,可以用一个表来记录所有已解决的子问题的答案,不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。 设a[n][m]为第n个矩阵到第m个矩阵连乘的最小乘法数(n, m >= 1),如果n=m,则a[n][m]这段中就一个矩阵,需要计算的次数为0。b[i-1], b[i]分别为第i个矩阵的行数和列数(i >=1),那么: 1. a[n][n + 1]易求,为相邻两个矩阵相乘的乘法数,即b[n-1] * b[n] * b[n + 1]; 2. An ~ Am可以任意拆分为An ~ Ai及Ai+1 ~ Am两部分相乘(n |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |