知识卡片
贪心覆盖只计算新增成员
本例贪心法维护尚未覆盖的成员,每轮选择与它们交集最大的候选子集,将该子集加入解,并移除本轮刚覆盖的成员。评价的是新增覆盖数,不是候选子集原本的总大小;否则已覆盖部分会被反复计功。
02797与正文的12技能例子中,贪心依次选A6、A2、A1、A3,共4个;A1、A2、A3三个就足以覆盖全部,因此局部最大新增覆盖不保证全局最少子集。图中各轮新增量为6、3、2、1。
“没有候选集合再与剩余成员相交”时,只有剩余成员已为空才是成功;剩余不为空意味着不可能完全覆盖。实际代码用严格大于更新最佳候选,交集同样大时保留遍历中先遇到的那个,具体结果也受平局处理影响。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
每次都尝试尽可能早覆盖S中更多的成员,因此该算法采用了贪心法(见第1章)的思路。由于每个集合都是从P中选出的,如果P被移除,则它的成员也将从S中移除。当P中剩下的成员中没有任何集合能够覆盖S中的成员时,此时覆盖集合C就完成了。 让我们看看对于12种技能的集合S={a,b,c,d,e,f,g,h,i,
参考来源
- 位置:《算法精解:C语言描述》第7章《Set示例:集合覆盖》(spine1263;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1230.html;u116-ch07-018)。
- 结论依据:116全文、02797完整四步图及02799–02800所有最大交集选择代码实读;原例贪心/最优选择与每步剩余区域相互核对,未运行。
- 原始内容:每次都尝试尽可能早覆盖S中更多的成员,因此该算法采用了贪心法(见第1章)的思路。由于每个集合都是从P中选出的,如果P被移除,则它的成员也将从S中移除。当P中剩下的成员中没有任何集合能够覆盖S中的成员时,此时覆盖集合C就完成了。 让我们看看对于12种技能的集合S={a,b,c,d,e,f,g,h,i,