寻找斯坦纳森林的近似算法
考虑一个加权图 G=(V,E,w)。我们给出了一系列顶点子集 V_i。
Steiner 森林是一个森林，对于每个顶点子集 V_i 将该子集中的所有顶点与一棵树连接起来。
示例：只有一个子集 V_1 = V。在这种情况下，斯坦纳森林是整个图的生成树。
示例：图 P4（具有 4 个顶点的路径）和两个子集：V_1 = {v1, v4} 和 V_2 = {v2, v3}。此示例的斯坦纳树是整个图。
足够的理论。找到这样一个权重最小的森林是很困难的（NP完全）。你知道有什么更快的近似算法来找到这样一个权重非最佳的森林吗？
Consider a weighted graph G=(V,E,w). We are given a family of subsets of vertices V_i.
A Steiner Forest is a forest that for each subset of vertices V_i connects all of the vertices in this subset with a tree.
Example: only one subset V_1 = V. In this case a Steiner forest is a spanning tree of the whole graph.
Example: a graph P4 (path with 4 vertices) and two subsets: V_1 = {v1, v4} and V_2 = {v2, v3}. The Steiner tree for this example is the whole graph.
Enough theory. Finding such a forest with minimal weight is difficult (NP-complete). Do you know any quicker approximate algorithm to find such a forest with non-optimal weight?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
Vijay Vazirani 的《近似算法》第 20 章描述了生成斯坦纳森林的模式。该分析使用 LP 对偶性，他用它来确定算法的因子：（
这是一个因子 2 算法，但在实践中它可能表现得很好）
近似算法< /a>
另外：请参阅 22.5 中的注释，其中描述了三篇论文供进一步阅读，包括对该主题的调查。
Chapter 20 of Approximation Algorithms by Vijay Vazirani describes a schema for generating a Steiner Forest. The analysis uses LP-duality, which he uses to determine the factor of the algorithm:
(This is a factor-2 algorithm but in practice it probably fares quite well)
Approximation Algorithms
Also: see the note in 22.5 that describes three papers for further reading, including a survey of the topic.
也许您可以将这个问题重述为其他 NP 完全问题，您知道任何次优算法吗？
不过，这只是一个猜测——我无法以我非常有限的数学技能找到这样的映射:)
Maybe you can restate this problem as other NP-complete, for which you know any suboptimal algorithms?
This is just a guess, though -- I can't find such mapping with my very limited math skills :)