知识卡片
局部最优需要整体条件
贪心法每一步按当前标准作最佳选择,并不同时枚举所有未来结果。局部选择能否组成整体最优,依赖问题结构,不能由“每步都选最好”直接推出。
霍夫曼树例反复取根频率最小的两棵树,合成频率为两者之和的新树,再放回候选集合。这个具体选择能服务相应编码目标,不意味着所有问题都可按同样局部标准解决;本节介绍过程,尚未证明其最优性。
116提供明确反例:12技能例贪心选四个,三个即可覆盖。局部最大新增覆盖是近似选择,不能从每步局部最好推出总数量最少。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 局部最优需要整体条件
- · Set示例:集合覆盖
原书出处 · 2 处
- · 查看原书依据
当前的最优解长远来看却未必是最优的。因此,贪心法并不会一直产生最优结果。然而,在某些方面来说,贪心法确是最佳选择。一个采用贪心法的例子是霍夫曼编码(见第14章),这是一个数据压缩算法。 霍夫曼编码中最重要的部分是构建一棵霍夫曼树[1]。为了构建一棵霍夫曼树,从它的叶子节点自底向上处理。将每个要压缩的
- · 查看原书依据
近似算法(见第1章)。它并不总是获得最优解,但肯定能够达到对数级的复杂度。该算法的工作原理是:不断从P中选出一个集合,使其能够覆盖S中最多的成员数量。换句话说,该算法每次都尝试尽可能早覆盖S中更多的成员,因此该算法采用了贪心法(见第1章)的思路。由于每个集合都是从P中选出的,如果P被移除,则它的成员
参考来源
- 位置:《算法精解:C语言描述》第1章《算法设计的一般方法》(spine1180;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1148.html;u016-ch01-008)。
- 结论依据:16贪心段明确局部选择未必整体最优,并给频率最小两树合并的霍夫曼步骤;卡片不把示例当一般最优证明。
- 原始内容:当前的最优解长远来看却未必是最优的。因此,贪心法并不会一直产生最优结果。然而,在某些方面来说,贪心法确是最佳选择。一个采用贪心法的例子是霍夫曼编码(见第14章),这是一个数据压缩算法。 霍夫曼编码中最重要的部分是构建一棵霍夫曼树[1]。为了构建一棵霍夫曼树,从它的叶子节点自底向上处理。将每个要压缩的
- 位置:《算法精解:C语言描述》第7章《Set示例:集合覆盖》(spine1263;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1230.html;u116-ch01-008)。
- 结论依据:116提供明确反例:12技能例贪心选四个,三个即可覆盖。局部最大新增覆盖是近似选择,不能从每步局部最好推出总数量最少。
- 原始内容:近似算法(见第1章)。它并不总是获得最优解,但肯定能够达到对数级的复杂度。该算法的工作原理是:不断从P中选出一个集合,使其能够覆盖S中最多的成员数量。换句话说,该算法每次都尝试尽可能早覆盖S中更多的成员,因此该算法采用了贪心法(见第1章)的思路。由于每个集合都是从P中选出的,如果P被移除,则它的成员