0

我正在自己阅读 CLRS，我发现但很难理解一些概念。

与贪婪相比，在动态规划中，我们在全局范围内做出选择并最终得到最优解。我通过 Multi Graph 中的最短路径示例以及背包问题 (Knapsack Problem) 很好地理解了这些概念。

  1. 我无法理解我们如何在 Matrix Chain 中动态做出选择。我已经理解了递归关系，但我无法对动态决策进行标准化。（我知道它具有最佳的子结构特性）

  2. 如果用贪心法求解矩阵链算法将如何工作？

谢谢 ！

4

1 回答 1

1

这个问题不能用贪心的方法解决。

例如，矩阵链 [3x2]•[2x3] •[3x4]。

结果将是 (([3x2]•[2x3]) •[3x4]) 使用贪婪方法，但最佳答案是 ([3x2]•([2x3] •[3x4]))。

更多详情：https ://www.cs.washington.edu/education/courses/421/04su/slides/matrixchain.pdf

于 2013-07-17T09:27:35.867 回答