什么是直觉behing的最优子？

Question

这个问题是从CLRS PG 362

整体最佳的解决方案结合了两个相关的子问题的最佳解决方案相关的动态规划和具体杆切削的问题。

整体最佳解决方案是通过寻找最佳的解决方案，以个别子问题，然后以某种方式俱乐部他们。我无法理解直觉和概念。任何链接，例子？

感谢

Answer 1

您可以比较动态规划和贪婪的方法。

最优子意味着，最优解可以通过寻找最佳解决方案，以子问题被发现。如果不是这种情况下，除子问题的最优解的总和并没有给我们最佳的全球性解决方案。

例如，考虑Dijkstra算法。如果我们知道从节点A到节点C比，我们可以利用这些信息来找到最短路径到另一个节点，以及最短路径。

如果不是这种情况，就不能构成最优解子问题，并得到全局最优解，不是我们可以用贪婪的方法。例如，看看change making problem。贪婪算法做出局部最优决策并找到一些解决方案，但这种解决方案不能保证是最优的。