知识卡片
贪心证明先替换再递归
证明贪心算法时,
- 可从任意最优解出发,用当前贪心选择替换其中一个选择,证明可行性和目标值不变;
- 再把剩余部分化为同类更小子问题,借最优子结构递归推进。
交换步骤不能只凭直觉声称安全。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第15章 贪心算法 · 查看原书依据
Typically, as in the case of Theorem 15.1, the proof examines a globally optimal solution to some subproblem. It then shows how to modify the solution to substitute the greedy choice for some other choice, resulting in one similar, but smaller, subproblem.
参考来源
- 位置:《算法导论(第4版)》第 15 章《贪心算法》(`OEBPS/chapter015.xhtml`,文本字符 [20000, 25000))。
- 结论依据:原文总结了先交换最优解中的选择、再缩小子问题的证明模式。
- 原始内容:Typically, as in the case of Theorem 15.1, the proof examines a globally optimal solution to some subproblem. It then shows how to modify the solution to substitute the greedy choice for some other choice, resulting in one similar, but smaller, subproblem.