知识卡片

普通读书笔记卡 · 3725.b.1.q · 生成模型:未记录

贪心覆盖只计算新增成员

理解等级:中级

本例贪心法维护尚未覆盖的成员,每轮选择与它们交集最大的候选子集,将该子集加入解,并移除本轮刚覆盖的成员。评价的是新增覆盖数,不是候选子集原本的总大小;否则已覆盖部分会被反复计功。

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,