构建覆盖顶点特定子集的最小生成树

 

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

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

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

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

你所说的问题是一个着名的NP难题，在图中称为Steiner树。 多项式时间没有已知的解，许多人都认为没有这种解决方案。

这里有很多混乱。 根据OP的说法：

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

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

给定一个加权图G =（V，E），顶点的一个子集S⊆V和一个根r V，我们想要找到一个最小权重树，它将S中所有顶点连接到r。 1

正如其他人所说的，这个问题是NP难的。 因此，您可以使用近似算法。

早期/简单近似算法

两种着名的方法是高桥方法和克鲁斯卡尔方法 （这两种方法都由Rayward-Smith进行了扩展/改进）：

  • Takahashi H，Matsuyama A：图中Steiner问题的近似解。 数学。 Jap 1980,24：573-577。
  • Kruskal JB：关于图的最短跨度子树和旅行推销员问题。 在Proceedings of the American Mathematical Society，第7卷; 1956年：48-50。
  • Rayward-Smith VJ，Clare A：找到Steiner顶点。 Networks 1986,16：283-294。

    • 高桥的最短路径近似（由Rayward-Smith修改）

    在这里输入图像描述

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

    在这里输入图像描述

    现代/更高级的近似算法

    在生物学中，最近的方法已经使用腔体方法处理了这个问题，这导致了“修正的置信传播”方法，该方法在大型数据集上显示出良好的准确性：

  • Bayati，M.，Borgs，C.，Braunstein，A.，Chayes，J.，Ramezanpour，A.，Zecchina，R .:斯坦纳树的统计力学。 物理学。 Rev. Lett。 101（3），037208（2008）15。
  • 对于一个应用：斯坦纳树方法用于最优子网络识别：一项实证研究。 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，FM Suchanek和G. Weikum。 STAR：关系图中的Steiner-tree近似。 在ICDE'09，第868-879页，2009年

    • 在限制图（k，E'）上运行Prim算法，其中E'= {（x，y）∈V：x∈k且y∈k}）。 构造该图需要O（| E |）。

    链接地址: http://www.djcxy.com/p/35259.html

    上一篇: Construct a minimum spanning tree covering a specific subset of the vertices

    下一篇: Variation of Kruskal's algorithm