社交网络分析：寻找覆盖全体人员的最小权重子集

首先必须肯定你的建模思路完全没问题！你把人员映射为带权无向图的顶点、直接相识关系映射为无向边的方式，完美匹配问题的核心需求——我们要找的就是图中的带权最小支配集（Weighted Minimum Dominating Set），这是图论里的经典问题。

为什么之前的方法行不通？ #

你尝试的Chu-Liu/Edmond's算法是用于求解有向最小生成树的，而生成树的目标是用最少的边（或最小边权）连通所有节点，和“选最少权值的节点覆盖所有节点（自身或邻居）”的支配集需求完全不相关，所以得不到最优解是必然的。贪心递归如果没有针对性的剪枝或状态设计，也很难覆盖所有最优情况。

适合的算法方案 #

带权最小支配集是NP-hard问题，所以需要根据你的图规模和结构选择不同的解法：

1. 精确算法（适合小规模图，比如你例子中的链状图）

• 树结构专用：动态规划（DP）
  如果你的社交网络是树（无环连通图，比如你例子里的John-Adam-Viktor-Bob链），这是最高效的精确解法。每个节点定义三种状态：
  • 状态0：该节点被选中（支配自身和所有邻居）
  • 状态1：该节点未被选中，但被至少一个子节点支配
  • 状态2：该节点未被选中，被父节点支配
    从叶子节点向上递归计算每个子树的最小权值，合并状态即可得到全局最优解。针对你的例子，用这个DP可以轻松算出最优解{John,Bob}（权重9）。
• 整数线性规划（ILP）
  把问题建模为ILP：
  • 变量：$x_v \in {0,1}$，表示是否选取节点$v$
  • 约束：对每个节点$v$，$x_v + \sum_{u \in N(v)} x_u \geq 1$（$N(v)$是$v$的邻居集合）
  • 目标：$\min \sum_{v \in V} w_v x_v$
    用ILP求解器（如CPLEX、Gurobi）可以解决中等规模的问题。
• 回溯/分支限界
  枚举所有可能的节点子集，通过剪枝（比如当前已选权值超过已知最优解时直接终止分支）找到最优解，适合极小规模的图。

2. 近似/启发式算法（适合大规模图，无法求精确解时）

• 贪心算法
  每次选择“单位权值能覆盖最多未被支配节点”的节点加入集合$D$，重复直到所有节点被支配。实现简单，理论近似比为$O(\log n)$，虽然不一定得到最优解，但能快速得到可行解。
• 线性规划松弛+随机化/阈值近似
  将ILP的整数约束放松为$x_v \in [0,1]$，求解线性规划后，要么取$x_v \geq 0.5$的节点加入$D$，要么用随机化方法（按$x_v$的概率选择节点），这类方法有严格的近似保证。
• 启发式算法
  比如模拟退火、遗传算法，通过迭代优化的方式在大规模复杂图中找到较优的近似解，适合对精度要求不是极高但图规模很大的场景。

总结 #

你的建模完全正确，问题本质是带权最小支配集。如果你的社交网络是树结构，优先用树DP；小规模一般图用ILP或回溯；大规模图则选择近似或启发式算法。

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