Introduction

1. Introduction

给定一个无向加权图 G = (V, E) 和一个整数 s，该整数将顶点集 V = [0, 1, ..., |V|-1] 划分为一组 必需 的顶点 R = [0, 1, ..., s-1] 和一组 Steiner 顶点 S = [s, s+1, ..., |V|-1]，通用 Steiner 树问题是找到 Steiner 顶点的子集 S' ⊆ S 和最小权重的生成树 T = (R ⋃ S', E) 的问题。树 T 的权重就是其边权重的总和。


这个通用 Steiner 树问题是更为人所知的 最小生成树问题 (MST) 的泛化。


与具有多项式解决方案的 MST（例如，O(E log V) Kruskal's/Prim's 算法）不同，这个通用 Steiner-Tree 问题是一个 NP-hard 组合优化问题。

1-1. 其他斯坦纳树问题变体

这个一般的 Steiner-Tree 问题有几个其他的变体，例如，Euclidean-Steiner-Tree 和 Metric-Steiner-Tree 问题。


在Euclidean-Steiner-Tree 问题中，有 V 个不同的点（集合 R）在一个欧几里得（Euclidean, 二维）平面上，任务是找到一个（可能为空的附加）Steiner 点集 S（可以在二维平面的任何地方）和一个生成树 T = (R ⋃ S, E)，使得 T 的权重最小。任何两点的权重就是这两点的欧几里得距离。


在Metric-Steiner-Tree 问题中，它类似于Euclidean-Steiner-Tree，但这次附加的 Steiner 点是作为一组 S 提前给出的。任何两点的权重必须满足度量空间的属性。


Euclidean-Steiner-Tree，Metric-Steiner-Tree，以及在这个网站上可视化的一般 Steiner-Tree，都是 NP-hard 优化问题。

2. 可视化

在这里查看所选 Steiner-Tree 算法的可视化。


最初，输入图中的所有顶点和边都用标准黑色轮廓着色。随着可视化的进行，颜色浅蓝色将被用来表示一组必需的顶点R，颜色橙色将被用来显示当前正在使用的 Steiner 顶点。


在所选 Steiner-Tree 算法的最后，我们展示最佳生成树 = Steiner 树T。

3. 输入

有两种不同的方式来指定输入图：

  1. 编辑图：您可以将当前显示的无向加权图编辑为任何其他无向加权图。
  2. 示例图：您可以从无向加权图的示例列表中选择，以便您开始。

有一天，我们将提供一种简单的方式来重新标记任何当前加载的图中的顶点，以便所需顶点集R始终以[0, 1, ..., s-1]编号（因此其余的是潜在的斯坦纳顶点S）。

4. 精确算法

一般Steiner-Tree问题有3种特殊情况，它们的解决方案是多项式的：

  1. s = 2，这意味着只需要顶点R = [0, 1]，我们可以简单地运行 O((V+E) log V) 迪杰斯特拉算法来找到连接源顶点0和目标顶点1（或反之）的最短路径生成树。这个生成树也将是所需的Steiner Tree。
  2. s = |V|，这意味着所有的|V|顶点，即R = [0, 1, ..., |V|-1]都是必需的，我们可以简单地运行 O(E log V) Kruskal或Prim算法来找到整个图的完整最小生成树 (MST)。这个MST也将是所需的Steiner Tree。
  3. 如果G是一棵树：详细信息待补充。

4-1. 精确算法 - 完全搜索

But when s = [3, 4, ..., |V|-2], we have no choice but to run exponential algorithms as these cases fall into general cases of the NP-hard general Steiner-Tree problem.


One possible way is to try all possible subsets of the |V|-s vertices that can be part of the optimal Steiner Tree. Each time, we combine vertices in R = [0, 1, ..., s-1] with the currently chosen subset of potential Steiner vertices, run an O(E) Kruskal's algorithm (without re-sorting the edge list by weight anymore) for each of the 2|V|-s possible subsets, and report the best Steiner Tree. This is an exponential algorithm and this visualization page shows this algorithm.

4-2. 精确算法 - 动态规划

有一种更优化的指数算法，叫做 Dreyfus-Wagner 动态规划 (DP) 算法，它避免了子问题的重复计算。


遗憾的是，这部分还没有被数字化/可视化，正在进行中。

5. 近似

请查看CS4234的讲义以获取详细信息。