Steiner Tree是一个经典的NP-hard问题，问题定义不在这里重复了，主要介绍几种近年来典型的解法思路。
Steiner Forest扩展了Tree的定义，设置一组起始点集，一组终点集，要求任意一对起点-终点在Steiner Forest上有路径。
Steiner Forest并不真的是一个森林的形态，应该称之为一个子图。
最简单的启发式解法是遍历所有起点算Steiner Tree做合并（结果像是一个森林因此得名），但这显然是启发式贪婪算法，并非最优解。

1. Directed Steiner Tree Problem

1.1 精确解

1.1.1 整数线性规划ILP

• 线性规划有一个优化目标，同时有若干关于决策变量的限制条件，求解最优的决策变量（一个或多个）。
• 整数线性规划要求决策变量均为整数，没有高效的解法，但可以借用一些LP solver。

1.1.1.1 基于流的模型

image.png

• 图中的每一条边（即），都对应一个决策变量，1代表选进斯坦纳树，0代表未选进。
  a. 优化目标即为总边权重最小，因为结果是树，所以如果是无权图，这也等价于树中点的数量最少。
  b. 代表边a是否在root到终点x的路上。对于每一个终点x，有且只有一条边从root出发，且在到达x的路上。
  c. 对于每一个终点x，有且只有一条入边是在root到x的路上的。
  d. 从x出发的所有边，不能再返回x。（但可以去其他终点）
  e. 给定一个终点x，对于某一个中间点q，入边携带的到x的流和出边携带的到x的流总是相等的。【这里的流是说边是不是在root到x的路上】
  然而实际上这个流的值要么是1，要么是0。这样来保证没有环。
  f. 任意一个中间点，对于一个终点x来说，要么是一个root到x路径上的点，要么不是。
  到此为止的这些限制条件可以满足root到x一定有且仅有一条路径。
  g. 限制的取值范围：没有进树的边不能负载流。
  h. 如果一个边被选入Tree，那一定要负载流

1.1.1.2 基于路径的模型

此模型需要首先把从root到所有终点的所有路径全部找出来，然后建立规划模型。
a. 总权重最小。
b. 每个终点至少有一条路。
c. 如果一条边没有被选，那么不能有通过这条边的路径被选。

image.png

1.1.2 Dreyfus-Wagner算法

速度较差，暂略过。

1.2 近似解

1.2.1 基于最短路的算法

当终点只有一个的时候，Steiner Tree问题变成最短路问题，因此可从最短路算法补充边

1.2.1.1 最短路合并

找所有的最短路，合并之。
很简单，但是存在一个问题，如下图，过于贪婪导致不会使用已有树中边。

image.png

1.2.1.2 最短束

一个束是root到某一个中间节点v，然后v到所有的终点的最短路。
中间节点v需要遍历去寻找，只要root到v有路径，v到所有终点有路径，就可以尝试构造束。
然后选最短束即可。

• 如下图，解决了最短路方法的一些问题，可以利用一些中间信息，当然代价是复杂度增加了。

  
  image.png

• 最短束也有问题，如下图，如果没有合适的可达所有终点的中间节点，仍然无法利用中间信息。

  
  image.png

1.2.2 基于最小生成树的算法

当整个图的点全都是终点的时候，Steiner Tree问题变成最小生成树问题（有向，从root可达其它所有点），因此可从最小生成树删除边得到近似解。

1.2.2.1 贪婪算法

从root开始使用Prim算法， 逐一加入与已加入点距离最近的点，直到所有终点都加入进来。
然后只保留到终点的路径其它点和边全部去掉。

1.2.3 近似算法的总结

image.png

• 最短路算法虽然简单，但是快，在小图上表现已经很不错了；
• 其它最短路算法复杂度提高较多，但是近似系数上没有提升，实际近似质量上有时不比最短路强很多；
• 最小生成树速度不慢，但是近似系数是最大的，代表没有近似比例保证，但实际近似质量居中。