我研究了矩阵链乘法问题，并且理解了算法的作用。最近，我遇到了加泰罗尼亚数字，它在解决括号问题时派上了用场。在我看来，这个问题与矩阵链乘法非常相似。事实上，在 CLRS 中，他们在矩阵链乘法一章中提到了加泰罗尼亚数字。
我很好奇你能用加泰罗尼亚数字算法解决矩阵链乘法吗？我的想法是：不，你不能解决，因为加泰罗尼亚数字描述了用括号括起来的方法的数量，而原始矩阵链问题提出了一个不同的问题——具体的安排括号的方法会产生最小的成本。
我的想法正确吗？
问问题
1203 次
1 回答
0
矩阵链乘法和括号问题是彼此的等价形式。一个可以简化为另一个。
链矩阵乘法问题
给定一系列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 + 1pi − 1× pi × pi + 1
当你尝试写出上述问题的循环关系时，它与加泰罗尼亚数字的循环关系相同。因此加泰罗尼亚数可以用来解决矩阵链乘法问题。
于 2016-08-28T05:42:46.343 回答