algorithm - 矩阵链乘法可以有多个答案吗？

Question

我正在为算法考试学习，我的问题之一是为以下内容找到最佳矩阵链乘法:

A1:5x7

A2:7x10

A3: 10x7

A4:7x5

我最终得到了解决方案 ((A1*A2)A3)A4)，总计 875 次操作。正确答案标记为 (A1(A2(A3*A4))，其总和也是 875。这两个答案都正确吗，还是我遗漏了其他一些东西？

Answer 1

从您的示例中可以看出，可以有多个最佳答案。您还可以考虑具有相同维度(每个序列具有相同成本)的一组矩阵的简单情况。

您可能需要注意示例中的维度序列是回文的，两个可能的最佳解决方案也是如此。

如果不查看矩阵的值来进一步优化，就没有其他标准可以使用。使用矩阵的值，人们可能会想到可以进行的改进，以最大限度地减少获得最终结果的时间(例如，使用最快到达 0 矩阵的顺序)。