我正在阅读有关贪婪问题的两个属性的信息，并且我试图了解以下两者之间的区别:-
- 最优子结构性质:最优全局解包含其所有子问题的最优解。
- 贪婪选择性质:通过贪婪地选择局部最优选择，可以获得全局最优解。
这两者不是等价的吗？两者似乎是一回事；你能给我一个满足最优子结构但不满足贪心选择的例子吗？以及满足贪婪选择但不满足最优子结构的示例？
最佳答案
它们不等价:
假设我们想要在一棵树中找到最小的顶点覆盖，其中每个节点都有一个成本(覆盖的成本是该覆盖中所有节点成本的总和)。这里可以使用动态规划:f(v, taken) 是覆盖以 v 为根的子树的最小成本，使得 v在封面中，f(v, not taken) 是覆盖此子树而不取 v 的最小成本。最优子结构性质成立，因为我们可以最优地解决子问题(即为每个子树找到一个最优解)，然后将它们组合起来找到全局最优解。然而，贪婪选择属性在这里并不成立:在所有边都被覆盖之前选择具有最小成本的顶点并不总是产生最佳结果。
如果不可能定义什么是子问题，贪婪选择属性可能成立，但最优子结构属性不成立。比如哈夫曼编码构造算法总是合并两个最小的子树(并产生一个最优解)，所以它是一个贪心算法，但是并不清楚什么是子问题，所以说第一个意义不大完全没有属性(property)。
关于algorithm - 最优子结构和贪心选择，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26439973/