我正在自己阅读 CLRS，我发现但很难理解一些概念。
与贪婪相比，在动态规划中，我们在全局范围内做出选择并最终得到最优解。我通过 Multi Graph 中的最短路径示例以及背包问题 (Knapsack Problem) 很好地理解了这些概念。
我无法理解我们如何在 Matrix Chain 中动态做出选择。我已经理解了递归关系，但我无法对动态决策进行标准化。（我知道它具有最佳的子结构特性）
如果用贪心法求解矩阵链算法将如何工作？
谢谢 ！
问问题
2965 次
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 回答