← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3768.b

贪心选择须能延伸为全局最优

理解等级:高级

贪心选择性质要求:从当前局部最优选择出发,仍能构造出原问题的整体最优解。证明分两步:

  1. 说明存在一个整体最优解以这步贪心选择开头(常用办法是把某个最优解改写成包含它,且价值不变差)。
  2. 做出这步选择后,剩余部分是规模更小的同类问题,再用数学归纳法对每一步重复上述论证。

示例(依据分数背包定义补充):若某个最优方案没把密度最高的物品装到上限,就从方案里取出等重的低密度部分换成它(背包未满时直接多装它),重量不超、价值不降,所以必有一个最优解从“先装最高密度物品”开始;剩余容量又是一个更小的分数背包。

选择可依赖已做出的决策,但不依赖将来的选择。只观察到每步“看起来最好”不足以证明贪心法正确。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 2 . 1 从 背 包 问 题 了 解 贪 心 算 法 · 查看原书依据

      对于一个具体问题,要确定它是否具有贪心选择的性质,必须证明每一步所做的贪心选择最终能得到问题的最优解。首先,证明问题的一个整体最优解是从贪心选择开始的,而且作了贪心选择后,原问题简化为一个规模更小的类似子问题。然后,用数学归纳法证明,通过每一步贪心选择,最终可得到问题的一个整体最优解[1]。

    参考来源

    - 位置:《智能算法导论》第 122 项《12.1 从背包问题了解贪心算法》(源文件:`_epub-src/EPUB/xhtml/chapter12_0002.xhtml`) - 结论依据:原文要求证明整体最优解从贪心选择开始,且选择后剩余问题是规模更小的类似子问题,再用归纳证明;还指出选择可依赖已做决策,但不依赖未来选择。分数背包的交换论证为依据原书背包定义补充的教学示例,非书中证明。 - 原始内容:必须证明每一步所做的贪心选择最终能得到问题的最优解。首先,证明问题的一个整体最优解是从贪心选择开始的,而且作了贪心选择后,原问题简化为一个规模更小的类似子问题。