节点加权图的Minimum spanning tree变体问题：游戏场景近似求解需求

问题本质 #

这是无向图斯坦纳树问题的典型变种：

• 给定包含关键节点（必填、无权重）和可选节点（带权重）的无向图，边无权重（选中两端节点即可免费使用）
• 目标：选中一个节点子集，连通所有关键节点，且可选节点的总权重最小

示例说明：红色标记关键节点，绿色标记的是满足要求的近似最优解节点。

适合游戏场景的快速近似解法 #

针对游戏对性能和实现复杂度的要求，推荐以下几种简单高效的方案：

1. 最小生成树近似法（2倍近似比） #

• 操作步骤：
  1. 预计算所有关键节点对之间的最短路径（边无权重，即节点数最少的路径），路径权重为途经可选节点的总权重
  2. 以所有关键节点为顶点，上述路径权重为边权，构建完全图
  3. 对该完全图求最小生成树（MST）
  4. 将MST中每条边对应的原路径上的可选节点全部选中，加上所有关键节点，即为近似解
• 优势：实现简单，计算速度快，理论上近似比不超过最优解的2倍，完全适配游戏实时性需求

2. 贪心增量法 #

• 操作步骤：
  1. 初始选中所有关键节点，此时图中可能存在多个连通分量
  2. 每次找出能连接两个不同连通分量的可选节点中权重最小的那个，将其加入选中集合，合并对应连通分量
  3. 重复步骤2，直到所有关键节点处于同一连通分量
• 优势：逻辑直观，每一步计算量极小，适合游戏中关键节点动态变化的场景

3. 启发式剪枝枚举（小规模关键节点场景） #

如果关键节点数量较少（比如≤5个），可以用这种方法获得更优的近似解：

• 操作步骤：
  1. 先筛选出权重较低的可选节点（例如只保留总权重前30%的节点）
  2. 尝试将这些节点与关键节点组合，检查是否能连通所有关键节点，记录总权重最小的有效组合
• 优势：在关键节点数量少的场景下，解的质量接近最优，计算量也在可控范围内

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