斯坦纳树
斯坦纳树
对于图G=(V,E),存在子集K⊂V,K中的点称为关键点。斯坦纳树表示总边权最小的树,仅包含来自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。
考虑到对于某一株树的根结点,根结点下有三种情况:
- 根结点没有子结点
- 根结点有一个子结点
- 根结点有多个子结点
因此我们也可以根据三种情况建立状态转移公式。
- dp(i,s)=s==i.mask?0:inf
- dp(i,s|i.mask)=min(dp(i,s|i.mask),dp(j,s)+(i,j).w)
- dp(i,s)=min(dp(i,s),dp(i,s′|i.mask)+dp(i,(s−s′)|i.mask))
其中(i,j).w表示从i到j边的权重。
这里稍微说明一下复杂度。总共有V⋅2K个dp状态,而每个状态根据状态转移公式,时间复杂度如下:
- O(1)
- 可以通过在拥有相同状态的dp点上跑SPFA。时间复杂度摊还为O(E),如果边权非负,你还可以利用Dijkstra来将摊还时间复杂度降低到O(V)。
- s的子集数目为2B(s),其中B(s)表示s中1的数目。由于∑Ki=0(Ki)2i=(1+2)K,因此摊还时间复杂度为O(1.5K)。
因此对于任意一个dp状态所需的时间复杂度为O(V+1.5K),总共有V⋅2K个dp状态,因此总的时间复杂度为O(V(V⋅2K+3K))。
斯坦纳森林
斯坦纳森林是由若干斯塔纳树组成的。我们修改一下问题,对于图G=(V,E),存在多个不想交子集K1,K2,…,Km,我们称Ki中的点称为i类关键点。斯坦纳森林是一个总边权最小森林,满足同一类关键点落在相同的树中。
斯坦纳森林可以通过上面的斯坦纳树的动态规划求法获得。假设我们已经获得了上面动态规划结果——dp函数。
我们定义一个新的函数g,g(Ki1,Ki2,…)表示包含Ki1,Ki2,…中所有点,但是不包含K1,K2,…,Km−Ki1,Ki2,…中任意点,且同类关键点落在相同树中的最小边权森林的边权。
我们可以为g按照子集关系建立类似递推关系,这里不再赘述,这部分的时间复杂度为O(3m+2K)。