algorithm - 构造覆盖特定顶点子集的最小生成树

我有一个无向的正边权重图(V，E)，为此我想要一个最小的生成树，该生成树覆盖顶点V的子集k(Steiner树问题)。

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

从整个MST开始，我可以削减边缘/节点，直到获得包含所有k的最小MST。

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

最佳答案

这里有很多困惑。根据操作说明:



这是图形上的Steiner树问题。 这不是k-MST问题。 Steiner树问题的定义如下:



正如其他人提到的那样，这个问题很难解决。因此，您可以使用一种近似算法。

早期/简单近似算法

两种著名的方法是 Takahashi的方法和的Kruskal的方法(这两种方法均已由Rayward-Smith扩展/改进):

松山，高桥H，答:图中Steiner问题的近似解。数学。 Jap 1980，24:573-577。

Kruskal JB:在图的最短生成树和旅行商问题上。在《美国数学学会学报》第7卷中。 1956:48-50。

Rayward-Smith VJ，克莱尔(Clare)A:在查找Steiner顶点时。网络1986，16:283-294。

高桥最短路径近似(由雷沃德·史密斯修改)



Kruskal的近似算法(由Rayward-Smith修改)



现代/更多高级近似算法

在生物学中，最近的方法使用腔方法解决了该问题，这导致了“修改后的信念传播”方法，该方法在大数据集上显示出良好的准确性:

Bayati，M.，Borgs，C.，Braunstein，A.，Chayes，J.，Ramezanpour，A.，Zecchina，R .:斯坦纳树的统计力学。物理牧师101(3)，037208(2008)15.

对于一个应用程序:用于最佳子网识别的Steiner树方法:实证研究。 BMC生物信息学。 BMC生物信息学2013 30; 14:144。 EPUB 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树近似。在ICDE’09中，第868–879页，2009年

关于algorithm - 构造覆盖特定顶点子集的最小生成树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7685291/