java - 什么是链矩阵乘法？

Question

我试图了解什么是链矩阵乘法以及它与常规乘法有何不同。我已经检查了几个来源，但似乎都非常学术性地解释给我理解。

我想这是一种动态规划算法，以优化的方式实现操作，但我没有更进一步。

谢谢

Answer 1

链式乘法只是一系列乘法。A B C D 。最初它与编程和动态编程无关。但是有很好的规则（结合律）A * (B * C) = (A * B) * C，但是这些表达式的计算成本是不同的。所以有一个优化括号分布的任务。这是介绍。现在阅读维基。

Answer 2

矩阵链乘法是一个可以通过动态规划方法解决的问题，它需要适当的带括号的矩阵，以便以最少的乘法次数将给定矩阵相乘。例子

M1 = 12 x 20
M2 = 20 x 15
M3 = 15 x 30

有两种方法可以解决这个问题，取决于你从哪里开始乘以你的矩阵。

1). ((M1 x M2) x M3)
2). (M1 x (M2 x M3))

第一个只需要 3,600 + 5,400 = 9,000 次乘法。
第二个解决方案需要 9,000 + 7,200 = 16,200 次乘法。
在这里，我们将选择 first 而不是 second，因为它需要的乘法次数更少。
您的程序必须能够告诉用户如何给矩阵加上括号，以便最小化乘法（优化问题）