斯坦纳树

Published: by Creative Commons Licence

  • Tags:

斯坦纳树

对于图G=(V,E),存在子集KVK中的点称为关键点。斯坦纳树表示总边权最小的树,仅包含来自G(V,E)中的顶点和边,并包含所有关键点。

如果V=K,那么问题就变成了熟悉的最小生成树问题,这时候可以采用kruskal或prim算法来解决,时间复杂度为O(Elog2V)

如何计算斯坦纳树是一个NP问题,即你无法在多项式时间内求解。但是如果已知K非常小,我们可以在关联于3K的一个时间复杂度内利用动态规划解决这个问题。

首先,我们需要意识到斯坦纳树,也是一株树,树必然有根,我们可以枚举根来进行计算。并且由于我们仅关心关键点是否包含在树中,因此我们对关键点进行状态压缩,共2K种状态,我们可以利用二进制来表示。

我们记dp(i,s)表示以i为根,i可以是普通点也可以是关键点,满足s代表状态的子树。我们记结点u的掩码为u.mask,如果u是关键点,则u.mask表示u在二进制中对应的比特位,否则u.mask为0。

考虑到对于某一株树的根结点,根结点下有三种情况:

  1. 根结点没有子结点
  2. 根结点有一个子结点
  3. 根结点有多个子结点

因此我们也可以根据三种情况建立状态转移公式。

  1. dp(i,s)=s==i.mask?0:inf
  2. dp(i,s|i.mask)=min(dp(i,s|i.mask),dp(j,s)+(i,j).w)
  3. dp(i,s)=min(dp(i,s),dp(i,s|i.mask)+dp(i,(ss)|i.mask))

其中(i,j).w表示从ij边的权重。

这里稍微说明一下复杂度。总共有V2Kdp状态,而每个状态根据状态转移公式,时间复杂度如下:

  1. O(1)
  2. 可以通过在拥有相同状态的dp点上跑SPFA。时间复杂度摊还为O(E),如果边权非负,你还可以利用Dijkstra来将摊还时间复杂度降低到O(V)
  3. s的子集数目为2B(s),其中B(s)表示s1的数目。由于Ki=0(Ki)2i=(1+2)K,因此摊还时间复杂度为O(1.5K)

因此对于任意一个dp状态所需的时间复杂度为O(V+1.5K),总共有V2Kdp状态,因此总的时间复杂度为O(V(V2K+3K))

斯坦纳森林

斯坦纳森林是由若干斯塔纳树组成的。我们修改一下问题,对于图G=(V,E),存在多个不想交子集K1,K2,,Km,我们称Ki中的点称为i类关键点。斯坦纳森林是一个总边权最小森林,满足同一类关键点落在相同的树中。

斯坦纳森林可以通过上面的斯坦纳树的动态规划求法获得。假设我们已经获得了上面动态规划结果——dp函数。

我们定义一个新的函数gg(Ki1,Ki2,)表示包含Ki1,Ki2,中所有点,但是不包含K1,K2,,KmKi1,Ki2,中任意点,且同类关键点落在相同树中的最小边权森林的边权。

我们可以为g按照子集关系建立类似递推关系,这里不再赘述,这部分的时间复杂度为O(3m+2K)