贪心算法在最小顶点覆盖问题中失效的示例及原理问询

一、失效示例 #

构造如下无向图：

• 中心节点A，连接节点B、C、D
• 节点B连接叶子节点B1、B2；节点C连接C1、C2；节点D连接D1、D2

各节点初始度数：

• A、B、C、D度数均为3（当前最大值）
• 所有叶子节点度数为1

贪心算法执行过程 #

1. 假设贪心选择度数最大的A加入顶点覆盖，移除A及关联边AB、AC、AD
2. 剩余边为B-B1、B-B2、C-C1、C-C2、D-D1、D-D2，此时B、C、D度数为2（当前最大值），依次将它们加入集合
3. 最终顶点覆盖集合为{A,B,C,D}，共4个节点

最优解 #

选择{B,C,D}即可覆盖所有边：

• B覆盖AB、B-B1、B-B2
• C覆盖AC、C-C1、C-C2
• D覆盖AD、D-D1、D-D2
  仅需3个节点，比贪心结果少1个。

二、失效原理 #

贪心算法的逻辑是每一步取局部最优（当前度数最大的节点），但顶点覆盖的全局最优需要考虑“节点覆盖边的综合效率”，两者存在冲突：

• 度数大的节点可能覆盖的是「可被其他节点更高效覆盖」的边：比如示例中的A，仅能覆盖3条与子节点的连接边；而B、C、D中的每个节点，既能覆盖与A的连接边，还能覆盖两条叶子边，单节点覆盖效率更高。
• 贪心算法无法预判后续选择成本：选A后，剩余的叶子边必须额外选择B、C、D来覆盖；而直接选B、C、D，可以一次性覆盖所有边，无需额外节点。

内容的提问来源于stack exchange，提问作者NITHIN SABU