用Catalan数计算矩阵链变异

Question

我研究了矩阵链乘法问题，了解了算法的工作原理。最近，我遇到了加泰罗尼亚数字，这些数字在求解括号问题时很方便。这个问题在我看来非常类似于矩阵链乘法。事实上，在CLRS中，他们提到了矩阵链乘法章中的Catalan数。

我很好奇，你能用加泰罗尼亚数算法解矩阵链乘法吗？我的想法是:不，你不能解决，因为加泰罗尼亚数字描述了括号矩阵的数目，而最初的矩阵链问题提出了一种不同的特定问题的方法来排列括号，这会给出最小的代价。

我的想法正确吗？

Answer 1

矩阵链乘法和仿真度问题是彼此等价的形式。一个可以还原成另一个。

链矩阵乘法问题

给出了n矩阵A1, A2, ... An的序列及其维数p0, p1, p2, ..., pn，其中i = 1, 2, ..., n矩阵Ai有维数pi − 1 × pi，确定了使标量乘法次数最小化的乘法阶数。

等价形式:泛素化问题

给定n矩阵，A1, A2, ... An，其中对于1 ≤ i ≤ n，Ai是一个pi − 1 × pi，矩阵，插入乘积A1, A2, ... An以使总成本最小化，假设使用朴素算法将pi − 1× pi矩阵乘以pi × pi + 1矩阵的代价是pi − 1× pi × pi + 1。

当你试图写出上述问题的循环关系时，结果与加泰罗尼亚数的关系相同。因此，加泰罗尼亚数可以用来求解矩阵链乘法问题。

矩阵链乘法问题