构造覆盖顶点的特定子集的最小生成树
atp*_*atp 40 algorithm tree graph-theory graph-algorithm
我有一个无向的正边缘权重图(V,E),我想要一个覆盖顶点V的子集k的最小生成树(Steiner树问题).
我不是将生成树的大小限制为k个顶点; 而且我确切地知道MST中必须包含哪些 k个顶点.
从整个MST开始,我可以削减边缘/节点,直到我得到包含所有k的最小MST .
我可以使用Prim算法来获取整个MST,并开始删除边缘/节点,同时不破坏子集k的MST; 或者我可以使用Floyd-Warshall获得所有对最短路径并以某种方式结合路径.有没有更好的方法来解决这个问题？
use*_*029 14
这里有很多混乱.根据OP的说法:
我不是将生成树的大小限制为k个顶点; 而且我确切地知道MST中必须包含哪些k个顶点.
这是图上的Steiner树问题. 这不是k-MST问题.Steiner树问题定义如下:
给定加权图G =(V,E),顶点的子集S⊆V和根r∈V,我们想要找到将S中的所有顶点连接到r的最小权重树. 1
正如其他人所提到的,这个问题是NP难的.因此,您可以使用近似算法.
早/简近似算法
两个着名的方法是Takahashi的方法和Kruskal的方法(两者都由Rayward-Smith扩展/改进):
- Takahashi H,Matsuyama A:图中Steiner问题的近似解.数学.Jap 1980,24:573-577.
- Kruskal JB:关于图的最短跨越子树和旅行商问题.在"美国数学学会学报"第7卷; 1956年:48-50.
- Rayward-Smith VJ,Clare A:找到Steiner顶点.Networks 1986,16:283-294.
Takahashi的最短路径近似(由Rayward-Smith修改)
Kruskal的近似算法(由Rayward-Smith修改)
现代/更高级的近似算法
在生物学中,最近的方法使用腔体方法处理了这个问题,这导致了一种"修正的信念传播"方法,该方法在大数据集上表现出良好的准确性:
- Bayati,M.,Borgs,C.,Braunstein,A.,Chayes,J.,Ramezanpour,A.,Zecchina,R.:steiner trees的统计力学.物理学.莱特牧师.101(3),037208(2008)15.
- 对于应用:用于最佳子网识别的Steiner树方法:实证研究.BMC生物信息学.BMC Bioinformatics 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,FM Suchanek和G. Weikum.STAR:关系图中的Steiner树近似.在ICDE'09,第868-879页,2009年
在受限图 ( k , E' )上运行 Prim 算法，其中E' = {( x , y ) \xe2\x88\x88 V : x \xe2\x88\x88 k和y \xe2\x88\x88 k }) 。构建该图需要 O(| E |)。
\n