动态规划求解最小斯坦纳树（证了一天两夜）

最小斯坦纳树

给定点的“最小生成树”问题。

背景

给定无向连通图 $G=(V,E)$，给出包含 $k$ 个结点的点集 $S$，包含点集 $S$ 的连通图被称作 斯坦纳树。但我们关注的是如何求出包含点集 $S$ 的最小连通图 $G^{\prime }=(V^{\prime },E^{\prime })$ 即 最小斯坦纳树。其中$S\subseteq V^{\prime },E^{\prime }\subseteq E$。

此处的最小可以指最小的点权和、边权和等。

求解最小斯坦纳树是一个 $NP-Hard$ 问题，所以只会有近似解，并且数据范围不会太大即 $k\le 10$。

目前的最好算法的算法时间复杂度为：$O(3^{K}N+2^{K}MlogM)$。其中 $N=|V|,M=|E|$。

动态规划+状态压缩

笔者对着题解思考了这个方法近 $1$ 天半，并网上查阅了很多资料，再加上自己的一些证明，终于能够彻底搞懂这个算法的精髓。下文将着重论述笔者当时卡住的地方。

我们先假设求的是包含点集 $S$ 的边权和最小的连通块。设权重函数 $W:E\to N$。

【起源】

【性质 $1$】 包含点集 $S$ 的边权和最小的子图 $G^{\prime }=(V^{\prime },E^{\prime })$ 一定是一棵树。

【证明】若 $G^{\prime }$ 中包含环，那么将环中边权最大的边删去后，$G^{\prime }$ 仍连通且边权和变得更小，与前面假设的边权和最小矛盾，故 $G^{\prime }$ 不含环，证毕。

根据性质 $1$，我们不难得到一个暴力算法：枚举 $G$ 的所有子图 ，对子图进行最小生成树算法。虽然这样一定能够求出包含 $S$ 的斯坦纳树，但时间复杂度是 $O(2^{V}ElogV)$，这是因为有许多子图是没必要枚举的，且每次枚举后还要进行生成树算法，不如我们干脆就从包含 $S$ 的树开始转移。

设 $dp[i][S]$ 表示以 $i$ 为根结点且包含 $S$ 的树的最小边权和，因为 $S$ 是一个集合，且集合内的元素不超过 $10$，所以我们考虑用二进制来表示这个集合。

到这里，几乎所有的题解/博客都是直接给出转移方程，然后再贴个代码。但里面的内容却不细讲，可能是觉得大家都学到斯坦纳树了，没必要再写太过详尽。但是却苦了我这个菜鸟。

为了理解透彻我们先从初始化开始讲。

【初始化】

设 S = { t e r m i n a l [ 1 ] , t e r m i n a l [ 2 ] , ⋯ , t e r m i n a l [ k ] } S=\{terminal[1],terminal[2],\cdots,terminal[k]\} S={terminal[1],terminal[2],⋯,terminal[k]} 。（最初定义斯坦纳树的论文中，管 $S$ 中的点叫做终端（$terminal$）点，斯坦纳树中的不属于终端点的其他点叫做斯坦纳点。）那么则有初始化：

for i in (1,2,...,k) :dp[terminal[i]][1<<(i-1)] = 0;

$dp[terminal[i]][1<<(i-1)]$ 中，根是终端点本身，包含的集合也是终端点本身。因为算的是子树的最小边权和，而只有一个点的树显然没有边，所以赋值为 $0$。

数组第二维的 $(i-1)$ 是为了和集合 $S$ 的二进制表示所对齐，因为 $S$ 的二进制表示是 $\underset{k个1}{\underbrace{1\cdots 1}}$，即 $(1<<k)-1$，而$1<<(i-1)$ 正好是 $S$ 的二进制中第 $i$ 个 $1$。

初始化了解完了之后，我们需要了解答案是怎么产生的。

【答案产生】

{ d p [ i ] [ S ] ; ∀ i ∈ S } \{dp[i][S];\forall i\in S\} {dp[i][S];∀i∈S} 显然都是正确答案，因为 $dp[i][S]$ 表示以 $i$ 为根结点且包含 $S$ 的树的最小边权和，而最小斯坦纳树显然包括 $S$，所以 $S$ 中的任意一点为根都可以作为答案。

因为最终答案的 $S$ 的二进制表示中有 $k$ 个 $1$，但初始化时只有一个 $1$，所以 $dp$ 的转移过程中必然需要子集合的合并。

比如说 $dp[i][00\cdots 10]$ 和 $dp[i][00\cdots 01]$ 可以合并为 $dp[i][00\cdots 11]$（$dp$ 的第二维是集合的二进制表示）。

看到这里可能会感到好奇，因为初始化时 $dp$ 数组中根和集合都是终端点本身，即一个点对应一个集合，但上文的 $dp[i][00\cdots 10]$ 和 $dp[i][00\cdots 01]$ 却是一个点对应两个集合。这是怎么从初始态转移而来的？

我们定义 $d(i,j)$ 为原图中 $i⇝j$ 的最短路径长度。我们强行让 $j$ 结点和 一棵以 $terminal[i]$ 为根，包含集合 $1<<(i-1)$ 的子树连通，那么连通后就有了一棵新树。以 $j$ 为根，包含集合 $1<<(i-1)$ 的子树的最小边权和是：
$$dp[j][1<<(i-1)]=dp[terminal[i]][1<<(i-1)]+d(terminal[i],j)\text{\hspace{1em}(1)}$$
也就是在原来的基础上加上了 $terminal[i]$ 到 $j$ 的最短路。这个式子的正确性是显然的。

接下来我们将演示在一个简单图上的 $dp$ 过程。

请看下图演示

S = { 1 , 3 } S=\{1,3\} S={1,3}

初始化

$dp[1][01]=0,dp[3][10]=0$（$dp$ 的第二维是集合的二进制表示，$01$ 表示 结点 $1$ 是第一个终端点，$10$ 表示结点 $3$ 是第二个终端点。）。

强行连通

$2,3,4$ 与 $dp[1][01]$ 代表的子树连通：

$dp[2][01]=3,dp[3][01]=1,dp[4][01]=3$。

$1,2,4$ 与 $dp[3][10]$ 代表的子树连通：

$dp[1][10]=1,dp[2][10]=2,dp[4][10]=4$。

现在所有结点都连通了包含 $terminal[i]$ 的子树，且包含的集合大小为 $1$ 。

合并子树

接下来对于每个结点 $v$ ，我们将两棵以 $v$ 为根，包含大小为 $1$ 的集合的子树，合并为一棵 以 $v$ 为根，包含大小为 $2$ 的集合的树。
$$dp[v][11]=dp[v][10]+dp[v][01]\text{\hspace{1em}(2)}$$
在这个例子中，$S$ 集合大小为 $2$，所以此时已经做完了。不妨更普遍一些，$|S|>2$ 显然我们要遍历所有的子集合，设 $S$ 的子集合为 $S^{\prime }$，则有：
$$dp[v][S]=\underset{\forall S^{\prime }\subseteq S}{\min }(dp[v][S],dp[v][S^{\prime }]+dp[v][S-S^{\prime }])\text{\hspace{1em}(2’)}$$
那么我们可以将 $(1)$ 式的强行连通也写的更具有普遍性（这样可以求出真正的 $dp[v][S]$）：
d p [ v ] [ S ] = m i n ∀ u ∈ V { d p [ u ] [ S ] + d ( u , v ) } (1’) dp[v][S]=\underset{\forall u\in V}{min}\{dp[u][S]+d(u,v)\}\tag{1'} dp[v][S]=∀u∈Vmin​{dp[u][S]+d(u,v)}(1’)
所以，$dp$ 过程就是不断的进行三个操作：“强行连通”，“合并子树“，“强行连通”。

稍等…为什么合并子树之后还需要进行强行连通？

举个简单的例子：$S=2$，对于任意一个结点 $v$ 而言，合并子树只是令 $dp[v][11]=dp[v][01]+dp[v][10]$。但不代表合并之后 $dp[v][01]+dp[v][10]$ 就是真正的一棵以 $v$ 为根且包含 $S$ 的最小边权和子树。

假设 $v=1$， S = { 3 , 4 } S=\{3,4\} S={3,4}，此时经过一次强行连通之后 $dp[1][01]=a+c,dp[1][10]=a+b$，合并后 $dp[1][11]=2a+b+c$。但实际上 $dp[1][11]=dp[2][11]+d(1,2)=a+b+c$。这也就是我们需要再进行一次强行连通的目的。因为进行完了一次强行连通，我们会对所有的包含集合大小相同的以 $v$ 为根的树求出其真正的最小边权和。

这就是为什么我们要在合并子树之后再进行一次强行连通。

但其实，如果我们循环进行两次操作：“合并子树” ，“强行连通” 也是没问题的。因为合并子树的目的是 “扩大集合”，前提是子树所代表的最小边权和准确。因为初始时只有 $dp[terminal[i]][1<<(i-1)]$，如果此时我们进行合并子树的话，是不会有任何反应的，因为没有进行连通，所以一个点只对应一个集合。然后再进行强行连通操作。所以每次只要执行两次操作就行了，更省事。

即 $dp$ 过程就是不断的进行两个操作：“合并子树”，“强行连通”。

到这里，我们可以用一个基础版的代码求出给定点集 $S$ 的最小斯坦纳树。基础版的时间复杂度是 $O(3^{k}N+N^{2}logM+2^k{N}^2)$。因为我们需要用到最短路，所以考虑用 $n$ 次 $dijkstra$ 求解出任意两点之间的最短路（当且仅当不含负权边，且 $N$ 数量级较小时用）。

合并子树：遍历 $S$ 的子集 $mask$ + 遍历每个点 + 枚举 $mask$ 的子集 = $O(3^{k}N)$。

强行连通：遍历 $S$ 的子集 $mask$ + 遍历最终根结点 $u$ 和中转根结点 $v$ = $O(2^k{N}^2)$。

预处理最短路： $n$ 遍 $Dijkstra$ = $O(N^{2}logM)$。

for (int mask = 1; mask < (1 << k); mask ++) {for (int submask = mask; submask; submask = (submask - 1) & mask)for (int u = 0; u < N; u ++)dp[mask][u] = min(dp[mask][u], dp[submask][u] + dp[mask ^ submask][u]);for (int u = 0; u < N; u ++) {for (int v = 0; v < N; v ++)dp[mask][v] = min(dp[mask][v], dp[mask][u] + d[u][v]);}

【至臻版本】

代码来自 $Jiangly$（进行了一些个人习惯上的修改）。

for (int s = 0; s < (1 << (K - 1)); s++) {for (int t = s; t != 0; t = (t - 1) & s) for (int i = 0; i < N; i++) dp[s][i] = min(dp[s][i], dp[t][i] + dp[s ^ t][i]);priority_queue<PII, vector<PII>, greater<PII>> pq;vector<bool> vis(N, false);for (int i = 0; i < N; i++) if (dp[s][i] != inf) pq.push({dp[s][i], i});while (!pq.empty()) {auto [d, x] = pq.top();pq.pop();if (vis[x]) continue;vis[x] = true;for (auto [y, w] : adj[x]) {if (dp[s][y] > dp[s][x] + w) {dp[s][y] = dp[s][x] + w;pq.push({dp[s][y], y});}}}}

至臻版本和普通版本的区别就是，至臻版本没有提前预处理出任意两结点之间的最短路。而是在需要用到最短路的时候调用 $Dijkstra$。

我们将有效值统统插入最小优先队列中，然后进行 $Dijkstra$，$dp[S][i]$ 会在 $Dijkstra$ 中松弛为最小值。

【问题】

for (int i = 0; i < N; i++) if (dp[s][i] != inf) pq.push({dp[s][i], i});

这段代码为啥和普通的 $Dijkstra$ 不一样？正常的 $Dijkstra$ 是令起点为 $0$，并且只有一个起点。

这段代码的意思是什么？

往最小堆中插入多个值，其中最小的会在第一次被拿出来。此时最小的值对应的根节点可以看作起点。假设这个点为 $u$，然后用这个起点的值 $dp[s][u]$，去更新起点周围的点，设为 $v$。此时如果 $dp[s][v]$ 大于 $dp[s][u]+w(u,v)$，那么说明 $v$ 从 $u$ 转移过来更优（强行连通操作之前， $v$ 的合并只会从 $v$ 的子树中转移，详细见合并操作）。那么 $v$ 就会被松弛成功。更新完 $u$ 周围的点，我们重新从最小堆中拿出最小的点作为起点去松弛周围的点。

为什么这样做是对的？

【性质 $2$】每次从最小堆中取出来的值，设其对应根结点是 $u$，显然 $u$ 一定从最优的点转移过来的。

【证明】因为进行 $Dijkstra$ 的元素一定是同集合大小的，假设 $dp[s][u]$ 是第一个被取出来的最小值，若它不是最优解，假设 $u$ 真正的最优解是 $\rho (s,u)$，且设它是由 $v$ 转移而来的，显然有 $\rho (s,u)=dp[s][v]+d(u,v)\le dp[s][u]$。也就是说存在 $dp[s][v]<dp[s][u]$，所以 $dp[s][u]$ 不是第一个被取出来的最小值，这与假设矛盾。所以第一个被取出的最小值一定是最优解。

假设 $dp[s][v]$ 是第 $t$ 次被取出来的最小值，如果此时 $dp[s][v]=\rho (s,v)$，说明接下来它不会被后续的点再更新。

设后续的点为 $x$，如果 $x$ 能更新 $v$，说明 $dp[s][v]>dp[s][x]+d(v,x)$，又因为后续出现的点 $dp[s][x]>dp[s][v]$，这与假设矛盾，所以 $x$ 必然是 $v$ 或者 $v$ 之前出现过的点即前 $t-1$ 个点。所以每次从最小堆中取出来的值，一定是最优解。

性质 $2$ 证毕。

根据性质 $2$，我们可以知道当 $Dijkstra$ 结束之后，$\forall i\in V,dp[s][i]=\rho (s,i)$。所以算法正确。

$ps$：现在是凌晨四点半，11点的时候喝了一杯咖啡，然后奋战到现在，妈呀真的战斗了个痛快。为什么写这一篇文章，主要是因为我实在看不懂网上的题解，有好多地方不清楚，然后又没有人细讲，所以干脆自己写了一篇，供大家参考。当然斯坦纳树还有许多的应用，我后续再补充，应该不会有第一次学这么难。