最小斯坦纳树（Steiner Tree）问题的精确解法（Dreyfus-Wagner 算法）
题目描述
给定一个无向带权连通图 \(G = (V, E)\)，其中每条边有非负权重，以及一个终端顶点集合 \(T \subseteq V\)（称为 Steiner points）。
目标：找到一个总权重最小的连通子图 \(S \subseteq G\)，使得 \(T\) 中的所有顶点都在 \(S\) 中连通。
这个子图 \(S\) 被称为最小斯坦纳树（Minimum Steiner Tree）。
允许使用 \(V \setminus T\) 中的顶点（称为 Steiner 顶点）来降低总权重。
解题过程
这是一个经典的NP-hard问题，但终端集合 \(|T| = k\) 较小时，可以用动态规划在 \(O(3^k n + 2^k n^2)\) 时间内精确求解，这就是 Dreyfus-Wagner 算法。
步骤 1：问题转换
斯坦纳树不一定是树，但最优解一定是树（否则可以删去环上一条边，总权重下降），所以我们只需找树。
设：
- \(n = |V|\)
- \(k = |T|\)，终端集合 \(T = \{t_1, t_2, \dots, t_k\}\)
- 顶点编号 \(1, 2, \dots, n\)
目标：找到连接 \(T\) 的最小权重树。
步骤 2：子问题定义
核心思路：以集合划分的方式合并部分解。
定义动态规划状态：
- \(dp[S][v]\)：
其中 \(S \subseteq T\) 是一个终端子集，\(v \in V\)。
含义：连接集合 \(S\) 中的所有终端，并且以顶点 \(v\) 为根的最小权重树的权重。
注意：这棵树必须包含 \(v\)，且 \(v\) 不一定在 \(S\) 中，但 \(S\) 中所有顶点必须连通到 \(v\)。
最终答案：
\[\min_{v \in V} dp[T][v] \]
因为以任意顶点为根都可以，最后取最小值。
步骤 3：状态转移
转移 1：合并两棵子树
对于状态 \(dp[S][v]\) 且 \(|S| \ge 2\)，可以将 \(S\) 划分成两个非空子集 \(S_1\) 和 \(S_2\)，分别用两棵子树连接它们，然后在 \(v\) 处汇合：
\[dp[S][v] = \min_{\substack{\emptyset \neq S_1 \subset S \\ S_2 = S \setminus S_1}} \left( dp[S_1][v] + dp[S_2][v] \right) \]
这个式子表示：分别构建连接 \(S_1\) 和 \(S_2\) 的树，两棵树都以 \(v\) 为根，合起来就是连接 \(S\) 的树（两棵树在 \(v\) 处合并）。
转移 2：通过另一顶点中转
对于 \(dp[S][v]\)，可以考虑先用一棵树连接 \(S\) 到某个其他顶点 \(u\)（\(u\) 可能作为 Steiner 顶点），然后再用 \(v\) 到 \(u\) 的最短路径连接 \(v\) 和这棵树：
\[dp[S][v] = \min_{u \in V} \left( dp[S][u] + dist(u, v) \right) \]
其中 \(dist(u, v)\) 是图中 \(u\) 到 \(v\) 的最短路径长度。
步骤 4：动态规划顺序
我们需要先计算所有顶点对之间的最短路径 \(dist(u, v)\)（用 Floyd-Warshall 或 \(k\) 次 Dijkstra，因为 \(n\) 可能不大）。
然后按 \(|S|\) 从小到大的顺序计算 \(dp[S][v]\)：
- 初始化：
当 \(S = \{t\}\) 是单元素集合时，只需连接到 \(v\) 的最小权重就是 \(dist(t, v)\)：
\[ dp[\{t\}][v] = dist(t, v) \]
- 对于 \(|S| \ge 2\)：
- 先用转移 1 的合并方式计算一个初始值（枚举 \(S\) 的所有非平凡划分）。
- 再用转移 2 的中转方式优化：对每个 \(v\)，尝试所有 \(u\) 看是否可以通过 \(u\) 得到更小的权重。
注意：转移 2 类似最短路的松弛，可以迭代直到不再更新。
步骤 5：算法伪代码
1. 计算全源最短路径 dist[1..n][1..n]（O(n^3) 或 O(n^2 log n) 等）。
2. 初始化 dp[S][v] = ∞ 对所有 S ⊆ T, v ∈ V。
3. 对每个终端 t ∈ T 和每个 v ∈ V：
dp[{t}][v] = dist[t][v]。
4. 对大小 |S| 从 2 到 k：
对于每个 S ⊆ T 且 |S| = s：
// 步骤 A：合并
对于每个非空真子集 S1 ⊂ S：
S2 = S - S1
对于每个 v ∈ V：
dp[S][v] = min(dp[S][v], dp[S1][v] + dp[S2][v])
// 步骤 B：中转松弛（类似最短路）
重复 n 次（或直到收敛）：
对于每个 v ∈ V：
对于每个 u ∈ V：
dp[S][v] = min(dp[S][v], dp[S][u] + dist[u][v])
5. 答案 = min_{v ∈ V} dp[T][v]。
步骤 6：时间与空间复杂度
- 状态数：\(2^k n\)（每个 S ⊆ T 和每个 v ∈ V）。
- 转移：
- 合并转移：对每个 S，枚举子集 S1 有 \(2^{|S|}\) 种，但可以在所有大小上平摊到 \(3^k\) 种划分（因为每个元素在 S1、S2 或不在 S 中）。
- 中转转移：对每个 S 做 n 轮松弛，每轮 O(n^2)（但实际常一次松弛即可收敛）。
- 总复杂度：\(O(3^k n + 2^k n^2)\)。
- 空间：\(O(2^k n)\)。
步骤 7：举例说明
假设图有 4 个顶点：\(V=\{1,2,3,4\}\)，边权如图，终端 \(T = \{1,2,3\}\)。
- 先算全源最短路 dist。
- 初始化：
- \(dp[\{1\}][1]=0, dp[\{1\}][2]=dist(1,2), \dots\)
- 计算 \(S=\{1,2\}\)：
- 合并：\(dp[\{1\}][v] + dp[\{2\}][v]\) 取最小。
- 中转：尝试用顶点 4 中转看是否更优。
- 最终 \(dp[\{1,2,3\}][v]\) 的最小值就是答案。
小结
Dreyfus-Wagner 算法的核心是集合划分动态规划，利用终端集合较小（k ≤ 20 左右）时可行，是精确求解小规模斯坦纳树问题的标准方法。