斯坦纳树 Steiner Tree

前言：
以前在看学姐blog的时候，发现在动态规划中有一个叫斯坦纳树的部分

前辈的blog
论文

斯坦纳树

斯坦纳树问题是组合优化问题，是最短网络的一种
其实最小生成树是最小斯坦纳树的一种特殊情况
最小生成树是在给定的点集和边中寻求最短网络使所有点连通
而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小

问题的提出

平原上的三个城镇间要兴建一个公用的煤气供应站，在选址问题上，要考虑的主要问题是使由供应站到三个城镇的输送管道的总长最短。如何去寻找合适地点？

假若要建的是一个垃圾处理站，要修建三条公路将垃圾站与三个城镇连起来
这时，因为三个城镇的居民的数目或工业性质等的不同，每天运送垃圾使用的车辆数目 各不相同，运输的费用也就各异。因此，选取地点时，如果仍考虑使三条公路的总长最小，就不合理了
这时应该考虑：先计算出三个城镇单位时间内生产的垃圾数量的百分比（或每日运输费用的百分比），如何选取地点，使得每个城镇垃圾运输数量与公路里程的乘积之和为最小

1638年，法国数学家费马在他所写的一本关于求极值的书中就有了第一个问题，称为费马问题
第二个问题则到了18世纪中叶才由辛普森（A.R.Simpson）提出来

性质

$Pollak-Gilbert$猜想：
平面上任意n点集，斯坦纳最小树长与最小生成树之长的比值的最小值是$sqrt(3) \over 2$

求解

这个问题比较现实，没有太多需要解释的地方
我们直接看解决方法：

首先我们知道，最优解必然是一棵树，这棵树又是由若干棵子树合并成的，
于是我们可以状态压缩，把$k$个节点的连通状态用一个二进制数j表示
$dp[i][j]$表示以i为根，与对应状态为$j$的节点连通的子树的最小权值

有两种转移方法：

• 枚举子树的形态：$dp[ i ][ j ]=min(dp[ i ][ j ]，dp[ i ][ k ]+dp[ i ][ l ])$，其中$k$和$l$是对j的一个划分
  • 按照边进行松弛：$dp[ i ][ j ]=min(dp[ i ][ j ]，dp[ i'][ j ]+w[ i ][ i'] )$，其中$i$和$i'$之间有边相连

  • 对于第一种转移，我们直接枚举子集就行了
    对于第二种转移，我们仔细观察可以发现这个方程和最短路的约束条件是很类似的，于是我们可以用spfa或者dijkstra来进行状态转移

    枚举子集的复杂度$=n*\sum{ C(k，i)*2^i } =n*3^k$，spfa的复杂度为$n*2^k$
    所以总复杂度为$O(n*3^k)$

    流程

    枚举状态集S 
    { 
         枚举S的子集s 
         { 
             更新f[S][1~n] 
         } 
         将 f[S][x]<inf 的x入队 
         spfa(S) 
    }
    

    LET US SEE THE CODE

    
    int f[1<<M][N];
    queue<int> q;
    bool in[N];
    
    void spfa(int S)
    {
        while (!q.empty())
        {
            int now=q.front(); q.pop();
            in[now]=0;
            for (int i=st[now];i;i=way[i].nxt)
            {
                int y=way[i].y;
                if (f[S][y]>f[S][now]+val[y])
                {
                    f[S][y]=f[S][now]+val[y];
                    if (!in[y]) q.push(y),in[y]=1;
                }
            }
        }
    }
    
    void work()
    {
        int cnt=0;
        memset(f,0x7f,sizeof(f));
    
        for (int i=1;i<=n;i++)
            if (!val[i]) f[1<<cnt][i]=0,cnt++;
        for (int S=1;S<(1<<cnt);S++)
        {
            for (s=(S-1)&S;s;s=(s-1)&S) 
                for (int i=1;i<=n;i++)
                    f[S][i]=min(f[S][i],f[s][i]+f[S^s][i]-val[i]);
            for (int i=1;i<=n;i++)
                if (f[S][i]<INF&&!in[i])
                    q.push(i),in[i]=1;
            spfa(S);
        }
    
        int ans=INF;
        for (int i=1;i<=n;i++) ans=min(ans,f[(1<<cnt)-1][i]);
        printf("%d\n",ans);
    }