构造覆盖特定顶点子集的最小生成树
我有一个无向正边权图(V,E)，我想要一个最小生成树覆盖顶点V的子集k em>（斯坦纳树问题）。
我没有将生成树的大小限制为 k 个顶点；相反，我确切地知道 MST 中必须包含哪些 k 个顶点。
从整个 MST 开始，我可以削减边缘/节点，直到获得包含所有 k 的最小 MST。
我可以使用Prim的算法得到整个MST，并在子集k的MST不被破坏的情况下开始删除边/节点；或者，我可以使用 Floyd-Warshall 来获取所有对的最短路径，并以某种方式合并路径。有更好的方法来解决这个问题吗？
I have an undirected, positive-edge-weight graph (V,E) for which I want a minimum spanning tree covering a subset k of vertices V (the Steiner tree problem).
I'm not limiting the size of the spanning tree to k vertices; rather I know exactly which k vertices must be included in the MST.
Starting from the entire MST I could pare down edges/nodes until I get the smallest MST that contains all k.
I can use Prim's algorithm to get the entire MST, and start deleting edges/nodes while the MST of subset k is not destroyed; alternatively I can use Floyd-Warshall to get all-pairs shortest paths and somehow union the paths. Are there better ways to approach this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这里有很多混乱。根据OP所说：
这是图上的 Steiner 树问题。 这不是 k-MST 问题。 Steiner 树问题定义如下：
正如其他人提到的，这个问题是 NP 困难的。因此，您可以使用近似算法。
早期/简单近似算法
两种著名的方法是Takahashi 方法和Kruskal 方法（两者均已由 Rayward-Smith 扩展/改进）：
Takahashi 的最短路径近似（由 Rayward-Smith 修改）
Kruskal 近似算法（修改为雷沃德-史密斯）
现代/更高级的近似算法
在生物学中，最近的方法使用空腔方法来处理该问题，这导致了“改进的信念传播”方法在大数据集上表现出了良好的准确性：
在搜索引擎问题的背景下，方法重点关注可以在某种程度上进行预处理的大型数据集的效率。
There's a lot of confusion going on here. Based on what the OP says:
This is the Steiner tree problem on graphs. This is not the k-MST problem. The Steiner tree problem is defined as such:
As others have mentionned, this problem is NP-hard. Therefore, you can use an approximation algorithm.
Early/Simple Approximation Algorithms
Two famous methods are Takahashi's method and Kruskal's method (both of which have been extended/improved by Rayward-Smith):
Shortest path approximation by Takahashi (with modification by Rayward-Smith)
Kruskal's approximation algorithm (with modification by Rayward-Smith)
Modern/More Advanced Approximation Algorithms
In biology, more recent approaches have treated the problem using the cavity method, which has led to a "modified belief propagation" method that has shown good accuracy on large data sets:
In the context of search engine problems, approaches have focused on efficiency for very large data sets that can be pre-processed to some degree.
你所说的问题是一个著名的NP难题，称为图中的Steiner树。多项式时间内没有已知的解，许多人认为不存在这样的解。
The problem you stated is a famous NP-hard problem, called Steiner tree in graphs. There are no known solutions in polynomial time and many believe no such solutions exist.
在受限图 (k, E') 上运行 Prim 算法，其中 E' = {(x, < em>y) ε V : x ε k 且 y ε k< /em>}）。构建该图需要 O(|E|)。
Run Prim's algorithm on the restricted graph (k, E') where E' = {(x, y) ∈ V : x ∈ k and y ∈ k}). Constructing that graph takes O(|E|).