如何获取最好的矩阵链相乘方法？

Nen 2022-03-28 13:53

- 程序员

该问题实际上并不是执行乘法，而只是决定以哪个顺序执行乘法。由于矩阵乘法是关联的，所以我们有很多选择来进行矩阵链的乘法运算。换句话说，无论我们采用哪种方法来执行乘法，结果将是一样的。例如，如果我们有四个矩阵A、B、C和D，可以有如下几种执行乘法的方法：（ABC）D=（AB）（CD）=A（BCD）=…虽然这些方法的计算结果相同。但是，不同的方法需要执行乘法的次数是不相同的，因此效率也是不相同的。例如，假设A是10×30矩阵，B是30×5矩阵，C是5×60矩阵。那么，（AB）C的执行乘法运算的次数为（10×30×5）+（10×5×60）=1500+3000=4500次。

A（BC）的执行乘法运算的次数为（30×5×60）+（10×30×60）=9000+18000=27000次。显然，第一种方法需要执行更少的乘法运算，因此效率更高。对于本题中示例而言，执行乘法运算的次数最少的方法如下：（A（BC））D的执行乘法运算的次数为20×30×10+40×20×10+40×10×30。

方法一：递归法

最简单的方法就是在所有可能的位置放置括号，计算每个放置的成本并返回最小值。在大小为n的矩阵链中，我们可以以n-1种方式放置第一组括号。例如，如果给定的链是四个矩阵。（A）（BCD）、（AB）（CD）和（ABC）（D）中，有三种方式放置第一组括号。每个括号内的矩阵链可以被看作较小的子问题。因此，可以使用递归方便地求解。

如何获取最好的矩阵链相乘方法？

轩辕小不懂的其他提问

类似问题

如何获取最好的矩阵链相乘方法？

轩辕小不懂 的其他提问

类似问题

轩辕小不懂的其他提问