知识卡片

普通读书笔记卡 · 3624.a

贪心选择先做局部决定

理解等级:中级

贪心算法在每一步先选当前看来最好的方案,再继续解决剩余问题;局部最优不自动保证全局最优,必须证明这种选择能进入某个最优解。

与[[动态规划先解子题再选择]]先比较子问题结果再决定不同,贪心通常先决定。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第15章 贪心算法 · 查看原书依据

      A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice leads to a globally optimal solution.

    参考来源

    - 位置:《算法导论(第4版)》第 15 章《贪心算法》(`OEBPS/chapter015.xhtml`,文本字符 [0, 5000))。 - 结论依据:原文给出逐步局部选择的定义,并明确贪心并非总能产生最优解。 - 原始内容:A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice leads to a globally optimal solution.