为什么贪心匹配算法能保证顶点覆盖问题的 2-近似？
该算法选择了一组不相交的边 M。最优覆盖必须为 M 中的每条边包含至少一个顶点，因此最优成本 >= |M|。贪心算法为 M 中的每条边添加 2 个顶点，因此贪心成本 = 2|M|。因此，贪心成本 <= 2 * 最优成本。
适用条件
- 算法选择任意边并添加两个端点，直到没有边剩余
理解与推导
- 识别算法选择的不相交边集 M。
- 认识到任何有效的顶点覆盖必须为 M 中的每条边包含至少一个端点。
- 得出最优覆盖大小 C* 至少是 M 中边数的结论。
- 注意贪心算法为 M 中的每条边添加了两个端点，导致恰好 2|M| 个顶点。
- 结合这些事实证明算法的成本最多是最优成本的两倍。
例子
旁白详细介绍了四个步骤：“第一步……选择一组完全断开、不相交的边……第二步……最优完美解 C 星必须为每一条边选择至少一个顶点……第三步……添加了两个端点……第四步……将它们结合起来。”
容易误解的地方
- 认为算法总是找到精确的最小顶点覆盖。
- 假设 2-近似界限是任意的，没有经过数学证明。
观看对应讲解
相关概念
继续追问
相关问题
答案依据视频资料生成并经过独立核验。若有疑问，请核对原视频或联系原作者。