知识卡片

普通读书笔记卡 · 3623.a

仅求最优值可省重建

理解等级:中级

动态规划先刻画最优解结构、定义最优值递推、计算最优值,再根据决策记录重建方案。

若问题只要求最优值,可省最后一步;若要具体方案,应在求值时保存决策,避免事后重新搜索。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 14 章 14.1 节(`OEBPS/chapter014.xhtml`,文本字符 [0, 5000))。 - 结论依据:第14章开头列出刻画结构、递推求值、计算与重建四步,并明确只需最优值可省第四步;若要重建,第三步宜保存选择。 - 原始内容:If you need only the value of an optimal solution, and not the solution itself, then you can omit step 4.