构建一个涵盖特定顶点集的最小生成树。

Question

我有一个无向的、正边权重图(V,E)，我想要覆盖顶点子集k的最小生成树（史泰纳树问题）。

我不限制生成树的大小为k个顶点；相反，我知道需要在MST中准确地包含哪些k个顶点。

从整个MST开始，我可以逐渐缩减边和节点，直到得到包含所有k的最小MST。

我可以使用Prim算法获得整个MST，并开始删除边/节点，同时不破坏子集k的MST；或者我可以使用Floyd-Warshall获得所有顶点间的最短路径，然后将这些路径合并。有更好的方法来解决这个问题吗？

- atp

---

如果我删除了不必要的顶点，也可能会失去连接远离的 k 个顶点的中间边。例如，如果我有这样一条路径：k--o--o--o--k，其中 o 表示一个不必要的顶点，k 则代表一个我需要的顶点，如果我删除中间的 o，便没有办法构建出 k 顶点之间的最小生成树。 - atp

所以你对最小生成树感兴趣，它不一定跨越所有顶点，只有k个顶点是跨越的？ - aioobe

没错。最小生成树至少包括所有的 k，然后尽可能少地包括其他节点。 - atp

你好，你能解决你的问题吗？如果可以的话，你能帮忙提供伪代码/代码吗？我有类似的问题，但是图是无权的。 - phoenix

这个问题不清楚 k 是一个数字还是一个集合。您可以请明确一下吗？ - Palec

Answer 1

这里存在很多混淆。根据发帖人所说：

我不会将生成树的大小限制为 k 个顶点；相反，我确切地知道在 MST 中必须包含哪些 k 个顶点。

这是图上斯坦纳树问题。 这不是 k-MST 问题。 斯坦纳树问题的定义如下：

给定加权图 G=(V,E)，顶点集 S ⊆ V 和一个根 r ∈ V，我们要找到连接 S 中所有顶点到 r 的最小权重树。1

正如其他人提到的，这个问题是 NP-hard。因此，您可以使用近似算法。

早期/简单的近似算法

两种著名的方法是 Takahashi 的方法 和 Kruskal 的方法（都被 Rayward-Smith 扩展/改进）：

• Takahashi H, Matsuyama A: An approximate solution for the Steiner problem in graphs. Math. Jap 1980, 24:573–577.
• Kruskal JB: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. In Proceedings of the American Mathematical Society, Volume 7. ; 1956:48–50.
• Rayward-Smith VJ, Clare A: On finding Steiner vertices. Networks 1986, 16:283–294.

---

Takahashi（经 Rayward-Smith 修改后的）最短路径近似

---

Kruskal（通过Rayward-Smith的修改）近似算法

---

现代/更高级的近似算法

在生物学中，最近的方法使用空穴方法来处理问题，导致了一种“修正置信传播”方法，对大数据集显示出较好的准确性：

• Bayati，M.，Borgs，C.，Braunstein，A.，Chayes，J.，Ramezanpour，A.，Zecchina，R.：Steiner树的统计力学。Phys. Rev. Lett. 101(3)，037208 (2008) 15。
• 应用案例：Steiner树方法用于最佳子网络标识：一项实证研究。BMC生物信息学。BMC Bioinformatics 2013年30日;14:144。电子版2013年4月30日。

在搜索引擎问题的背景下，方法侧重于对可以进行某种程度的预处理的非常大的数据集的效率。

• G. Bhalotia，A. Hulgeri，C. Nakhe，S. Chakrabarti和S. Sudarshan。使用BANKS在数据库中进行关键字搜索和浏览。在ICDE中，页431-440。
• G. Kasneci，M. Ramanath，M. Sozio，F. M. Suchanek和G. Weikum。STAR:关系图中的Steiner-tree近似。在ICDE'09上，页868-879，2009年

- user2398029

---

非常感谢您的帮助。这篇文章让我找到了一个很好的R实现，它在“SteinerNet”包中。 - Jeff Bezos

Answer 2

您提出的问题是一个著名的NP难题，称为在图中的斯坦纳树问题。目前没有已知的多项式时间解决方案，并且许多人认为不存在这样的解决方案。

- meh

---

实际上，图中的斯坦纳树具有固定的k个顶点作为输入，而OP只给出k并让算法找到该集合。这个问题被称为k-MST，也是NP难问题。请参见维基百科上与MST相关的问题。 - Palec

@Palec，实际上那是错误的。“我没有将生成树的大小限制为k个顶点；相反，我确切地知道MST中必须包含哪些k个顶点。”这个问题就是斯坦纳树问题。 - user2398029

此外，对 @meh 扣除一分，因为问题是 NP 难并不意味着我们不能使用近似算法得到有用的解决方案。这个答案没有帮助 OP 解决他的问题。 - user2398029

Answer 3

在受限图(k, E')上运行Prim算法，其中E' = {(x, y) ∈ V : x ∈ k and y ∈ k})。构建该图需要O（|E|）的时间。

- Fred Foo

---

这可能有时可以正常工作，但甚至不能保证 E' 是连接的 - 即使它是连接的，通过引入 Steiner 点（即不在 k 中的顶点）可能可以节省任意多的距离。 （如果距离遵循三角不等式，则少于“任意多”，但没有什么说它们必须这样做。） - j_random_hacker

@j_random_hacker有兴趣发布另一种解决方案吗？ - user2398029

@user2398029：我给meh的回答点了赞（我不知道为什么“蜥蜴比尔”删除了adi更早的说基本一样的答案）。基本上，这是一个NP难问题，要想最优解需要使用近似算法，如果你在谷歌上搜索“Steiner树近似”，你可能会得到一些可行的算法。 - j_random_hacker

@user2398029：看一下adi的回答中链接的第3章可能会有所帮助：http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf。（我在这里重新发布，因为我可以看到已删除的帖子，但我不确定那个声望截止点是什么。） - j_random_hacker