知识卡片

普通读书笔记卡 · 3623.b.2

最优子结构可用替换法验证

理解等级:高级

先假设全局最优解做了某个选择,再检查其产生的子问题:若所用子解还有更优版本,用更优版本替换便改进全局解,形成矛盾。这个论证要确认替换不改变别的约束或选择,否则不能据此宣称动态规划适用。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 14 章 14.2–14.3 节(`OEBPS/chapter014.xhtml`,文本字符 [45000, 50000))。 - 结论依据:14.3 节以 cut-and-paste 论证子解最优:假设子解非最优,替换成更优子解会改进整体并导致矛盾;适用前提是替换后仍为合法整体解。 - 原始内容:by “cutting out” the nonoptimal solution to each subproblem and “pasting in” the optimal one