知识卡片
贪心选择性质须单独证明
- 贪心选择性质要求当前局部最优选择能够嵌入某个全局最优解;
- 最优子结构则要求选完后,剩余问题的最优解可与已选项组合为原问题最优解。
两者一起支持连续选择,只证明子结构不足以推出贪心正确。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第15章 贪心算法 · 查看原书依据
The first key ingredient is the greedy-choice property: you can assemble a globally optimal solution by making locally optimal (greedy) choices.
参考来源
- 位置:《算法导论(第4版)》第 15 章《贪心算法》(`OEBPS/chapter015.xhtml`,文本字符 [20000, 25000))。
- 结论依据:原文将贪心选择性质与最优子结构列为两个关键条件,并分别说明其作用。
- 原始内容:The first key ingredient is the greedy-choice property : you can assemble a globally optimal solution by making locally optimal (greedy) choices.