如何寻找覆盖图中给定顶点子集的近似最小生成树？

两点场景的结论回顾 #

当仅需覆盖2个指定顶点时，确实可以简化为求解这两点间的最短路径，用A*、Dijkstra这类标准路径查找算法就能高效实现。

n个顶点的情况：Steiner树问题 #

你已经精准定位了问题——这就是Steiner树问题：在带权图中找到连接所有指定n个顶点（称为终端节点）的最小权值子树，允许引入额外的非终端节点（Steiner节点）来降低总权值。

这个问题属于NP完全问题，不存在多项式时间的精确解法（除非P=NP），因此只能寻求高效的近似解法：

1. 易实现的2-近似算法（基于最小生成树）

这是最常用的方案，步骤如下：

• 计算每对终端节点之间的最短路径，构建一个以终端节点为顶点的完全图，边权设为对应终端间的最短路径长度。
• 对这个完全图求最小生成树（MST）。
• 将MST中的每条边替换为原图中对应的最短路径，得到的子树就是覆盖所有终端的近似解，其总权值不超过最优解的2倍。
  该算法的时间复杂度主要取决于终端间最短路径的计算，适合绝大多数场景。

2. 更高精度的近似算法

针对无向图，目前已有能达到1.39倍近似比的算法，这类算法基于线性规划松弛和迭代随机化技术，但实现复杂度较高，仅适合对近似精度要求极高的场景。

3. 启发式算法

如果追求运算速度而非严格的近似比，可以选择贪心算法、模拟退火、遗传算法等启发式方法。这类算法能在短时间内得到质量较好的解，但无法保证解与最优解的比例关系，适合处理大规模图的场景。

补充：无Steiner节点的特殊情况 #

如果不允许引入额外的Steiner节点，问题就退化为终端节点的最小生成树问题，直接计算终端节点的MST即可，这是多项式时间可解的，但总权值通常会比Steiner树的最优解更大。

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