知识卡片
贪心选择先做局部决定
贪心算法在每一步先选当前看来最好的方案,再继续解决剩余问题;局部最优不自动保证全局最优,必须证明这种选择能进入某个最优解。
与[[动态规划先解子题再选择]]先比较子问题结果再决定不同,贪心通常先决定。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.