知识卡片
贪心覆盖每次增益最大
集合覆盖的贪心法维护未覆盖元素U,每轮选取与U交集最大的子集,再从U删去新覆盖元素。
循环到U为空即可得到可行覆盖;单步最大新增覆盖数并不保证最终子集数最少。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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