知识卡片

普通读书笔记卡 · 3723.b.1

贪心覆盖每次增益最大

理解等级:中级

集合覆盖的贪心法维护未覆盖元素U,每轮选取与U交集最大的子集,再从U删去新覆盖元素。

循环到U为空即可得到可行覆盖;单步最大新增覆盖数并不保证最终子集数最少。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第35章 近似算法 · 查看原书依据

      The greedy method in the procedure GREEDY-SET-COVER on the facing page works by picking, at each stage, the set S that covers the greatest number of remaining elements that are uncovered. In the example of Figure 35.3, GREEDY-SET-COVER adds to C, in order, the sets S1, S4, and S5, followed by either S3 or S6. Figure 35.3 An

    参考来源

    - 位置:《算法导论(第4版)》第35章《近似算法》(OEBPS/chapter035.xhtml,文本字符[25000,30000))。 - 结论依据:第35章无三角约束旅行商、集合覆盖与随机近似、线性松弛的原文论证;图35.3已核对。 - 原始内容:The greedy method in the procedure G REEDY -S ET -C OVER on the facing page works by picking, at each stage, the set S that covers the greatest number of remaining elements that are uncovered. In the example of Figure 35.3 , G REEDY -S ET -C OVER adds to C , in order, the sets S 1 , S 4 , and S 5 , followed by either S 3 or S 6 . Figure 35.3 An