首页 > 其他 > 详细

算法导论 之 动态规划 - 矩阵链相乘

时间:2014-05-08 17:26:41      阅读:492      评论:0      收藏:0      [点我收藏+]

1 引言


   在大学期间,我们学过高等数学中的线性规划,其中有关于矩阵相乘的章节:只有当矩阵A的列数与矩阵B的行数相等时,A×B才有意义。一个m×n的矩阵A(m,n)左乘一个n×p的矩阵B(n,p),会得到一个m×p的矩阵C(m,p)。矩阵乘法满足结合律,但不满足交换律。

    假设现要计算A×B×C×D的值,因矩阵乘法满足结合律,不满足交换律,即:A、B、C、D相邻成员的相乘顺序不会影响到最终的计算结果,比如: A×(B×(C×D))、A×((B×C)×D)、(A×B)×(C×D)、A×(B×C)×D、((A×B)×C)×D,虽然组合方式不一样,但是最终的计算结果是一致的,但改变任何成员的位置将影响到最终的计算结果。

    需要注意的是:虽然矩阵链相乘时,结合方式不同所得结果一致,但获得最终结果的所花费的时间是不一样的。假如:现有矩阵A(10,100)、B(100,5)、C(5,50),则不同结合方式的运算次数如下:

    运算次数N1[(A×B)×C] = 10*100*5+10*5*50 = 5000 + 2500 =7500

    运算次数N2[A×(B×C)] = 100*5*50 + 10*100*50 = 25000 + 50000 =75000

    N1:N2 = 7500 : 75000 = 1:10,经过对比可以发现不同的结合方式在性能方面的表现相差十分明显。而《动态规划 之 矩阵链相乘》就是针对此种问题的存在,从中选择最佳的矩阵结合方式,提高此类问题的求解效率。


2 处理思路


    那么针对矩阵链相乘的问题,怎样才能选出最佳的结合方式呢?那么以下将针对此问题,给出处理思路。假设现有矩阵A1(50,30)、A2(30,20)、A3(20,100)、A4(100,10)、A5(10,5),要求以最快的方式计算出它们相乘的结果。

bubuko.com,布布扣

图1 初始状态

Step1:计算相邻矩阵相乘的计算次数

    N[A1×A2] = 50*30*20  = 30000

    N[A2×A3] = 30*20*100 = 60000

    N[A3×A4] = 20*100*10 = 20000

    N[A4×A5] = 100*10*5  = 5000    - 最小

    由以上的计算结果可知N[A4*A4]的值最小,因此首先结合矩阵A4(100,10)和A5(10,5),得到矩阵B(100, 5)。此时所剩矩阵为:A1(50,30)、A2(30,20)、A3(20,100)、B(100,5)。

bubuko.com,布布扣

图2 矩阵A4与A5结合


Step2:计算相邻矩阵相乘的运算次数

    N[A1×A2] = 50*30*20  = 30000     - 不变

    N[A2×A3] = 30*20*100 = 60000     - 不变

    N[A3×B]  = 20*100*5  = 10000     - 最小

    同理,结合矩阵A3和A45,得到矩阵C(20, 5)。此时所剩矩阵为:A1(50,30)、A2(30,20)、C(20,5)。

bubuko.com,布布扣

图3 矩阵A3与B结合

Step3:计算相邻矩阵相乘的运算次数

    N[A1×A2] = 50*30*20 = 30000         - 不变

    N[A2×C]  = 30*20*5 = 3000           - 最小

    同理,结合矩阵A2和C,得到矩阵D(30, 5)。此时所剩矩阵为:A1(50,30)、D(30,5)。

bubuko.com,布布扣

图4 矩阵A2与C结合

Step4:最终计算顺序

    由以上3步的统计结果可知最佳的计算方式为:A1×(A2×(A3×(A4×A5))),用树来表示计算顺序的话,其结构如下图所示:

bubuko.com,布布扣

图5 最佳计算顺序


    如果需要以最快的方式计算A1*A2*A3*A4*A5的结果的话,则只需要遍历图5中的二叉树,便能找到最快的计算顺序。当然如果矩阵A1、A2、A3、A4、A5有其他的行列数时,最佳计算顺序可能为A1×((A2×A3)×(A4×A5)),则用二叉树表示为:

bubuko.com,布布扣

图6 其他可能最佳顺序

在此就暂不使用代码实现,有思路就行。


作者:邹祁峰 

 2014年05月08日




算法导论 之 动态规划 - 矩阵链相乘,布布扣,bubuko.com

算法导论 之 动态规划 - 矩阵链相乘

原文:http://blog.csdn.net/qifengzou/article/details/25183669

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!