最优子结构和贪心选择

Question

我正在阅读关于贪心问题的两个属性，并尝试理解以下两者之间的区别：-

- 最优子结构性质: 最优全局解包含所有子问题的最优解。 - 贪心选择性质: 可以通过贪心地选择局部最优选择来获得全局最优解。

这两个属性不是等价的吗？它们似乎是相同的东西；你能给我一个满足最优子结构但贪心选择不满足的例子吗？还有一个满足贪心选择但最优子结构不满足的例子吗？

- user277465

Answer 1

它们并不相等：

假设我们想在一棵树中找到最小的顶点覆盖，其中每个节点都有一个成本（覆盖的成本是此覆盖中所有节点成本的总和）。可以使用动态规划：$f(v, taken)$ 是以 $v$ 为根的子树的最小覆盖成本，使得 $v$ 在覆盖中，$f(v, not taken)$ 是覆盖此子树而不取 $v$ 的最小成本。最优子结构性质成立，因为我们可以最优地解决子问题（即，为每个子树找到最佳解），然后将它们组合以找到全局最优解。但是，贪心选择性质在这里并不成立：仅通过选择具有最小成本的顶点直到覆盖所有边不总是产生最佳结果。

如果无法定义子问题，则可能贪心选择性质成立，但最优子结构性质不成立。例如，霍夫曼编码构造算法总是合并两个最小的子树（并产生最优解），因此它是一种贪心算法，但不清楚什么是子问题，所以根本没有讨论第一性质的意义。

- kraskevich

---

我会这样定义子问题：子问题是一个新的问题实例，其中最小频率的两个子树已合并为一个子树。因此，它比原始问题严格更小。 - Einar

我几乎在任何地方都看到贪心算法需要最优子结构属性和贪心选择属性才能保证最优解。我从中得出的结论是，这不是真的，只需要贪心选择属性就可以了。这个理解正确吗？ - Stefan Wullems

Answer 2

对于未熟悉顶点覆盖和动态规划的未来读者，这些定义的措辞确实使其听起来相似。我认为重新表述“贪心选择”的一种有用方式是，最优解始终包含贪心算法选择的第一个选择，尽管它不一定是所述最优解中的第一个选择 **-> 这就是它们之间的区别，因为尽管某些东西可能是最优的并显示出贪心选择属性，但您并没有证明在每个步骤中都做出了当前最优解。在加权图上考虑Prim's MST：您可以从任何顶点开始，但这意味着算法可以在这两个解决方案的每个步骤中选择不同的边，但它们总是选择具有最低权重的边，因此它们具有贪心选择属性。但您并没有证明每个步骤中整个解决方案都是绝对最优的，只是选择最贪婪的选项。

这就是它们不同的原因，尽管贪心选择可以导致最优子结构，但这并不能证明它具有最优子结构。通常用于证明最优子结构的常见论据是“交换论证”和“领先保持论证”，它们建立在算法展示贪心选择属性的基础上。

- zstoebs