斯坦纳树


斯坦纳树问题是组合优化问题,与最小生成树相似,是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点,使生成的最短网络开销最小。

问题引入

19 世纪初叶,柏林大学几何方面的著名学者斯坦纳,研究了一个非常简单却很有启示性的问题:将三个村庄用总长为极小的道路连接起来。从数学上说,就是在平面内给定三个点 找出平面内第四个点 ,使得和数 为最短,这里 分别表示从 的距离。

问题的答案是:如果三角形 的每个内角都小于 ,那么 就是使边 对该点所张的角都是 的点。如果三角形 的有一个角,例如 角,大于或等于 ,那么点 与顶点 重合。

问题推广

  1. 在斯坦纳问题中,给定了三个固定点 。很自然地可以把这个问题推广到给定 个点 的情形;我们要求出平面内的点 ,使距离和 为极小,其中 是距离

  2. 考虑到点的其他相关因素,加入了权重的表示。 个点的其他相关因素可以换算成一个权重表示,求出平面内的点 ,使距离与权重的乘积的总和 为极小,其中 是每个点的权重。

  3. 库朗(R.Courant)和罗宾斯(H.Robbins)提出第一个定义的推广是肤浅的。为了求得斯坦纳问题真正有价值的推广,必须放弃寻找一个单独的点 ,而代之以具有最短总长的"道路网"。数学上表述成:给定 个点 ,试求连接此 个点,总长最短的直线段连接系统,并且任意两点都可由系统中的直线段组成的折线连接起来。他们将此新问题称为 斯坦纳树问题。在给定 个点的情形,最多将有 个复接点(斯坦纳点)。过每一斯坦纳点,至多有三条边通过。若为三条边,则它们两两交成 角;若为两条边,则此斯坦纳点必为某一已给定的点,且此两条边交成的角必大于或等于

连接三个以上的点的最短网络

steiner-tree1

在第一种情形,解是由五条线段组成的,其中有两个斯坦纳点(红色 ),在那里有三条线段相交且相互间的交角为 。第二种情形的解含有三个斯坦纳点。第三种情形,一个或几个斯坦纳点可能退化,或被一个或几个给定的点所代替。

我们将斯坦纳树的问题模型以图论形式呈现。

steiner-tree2

对于形式一,如果令关键点为 ,可以发现若直接将这四个关键点相连的最小边权和是 12,显然这不是最优的。如果考虑使用 5 号节点那么最小边权和就会是 9,得到一个更优的答案。

对于形式二,如果令关键点为 ,可以发现这四个关键点中的一些点甚至没有直接相连的边,必须考虑使用复接点(斯坦纳点)。这时将 5 号考虑进去可以得到最小边权和 9。

并且我们可以发现在两张图中 1 号和 4 号的斯坦纳点是退化的,被 1 号或 4 号代替了。

例题

首先以一道模板题来带大家熟悉最小斯坦纳树问题。见 【模板】最小斯坦纳树

题意已经很明确了,给定连通图 中的 个点与 个关键点,连接 个关键点,使得生成树的所有边的权值和最小。

结合上面的知识我们可以知道直接连接这 个关键点生成的权值和不一定是最小的,或者这 个关键点不会直接(相邻)连接。所以应当使用剩下的 个点。

我们使用状态压缩动态规划来求解。用 表示以 为根的一棵树,包含集合 中所有点的最小边权值和。

考虑状态转移:

  • 首先对连通的子集进行转移,

  • 在当前的子集连通状态下进行边的松弛操作,。在下面的代码中用一个 tree[tot] 来记录两个相连节点 的相关信息。

另外一道经典例题 [WC2008]游览计划

这道题是求点权和最小的斯坦纳树,用 表示以 为根的一棵树,包含集合 中所有点的最小点权值和。 表示点权。

考虑状态转移:

  • 。由于此处合并时同一个点 ,会被加两次,所以减去。

可以发现状态转移与上面的模板题是类似的,麻烦的是对答案的输出,在 DP 的过程中还要记录路径。

pre[i][s] 记录转移到 为根,连通状态集合为 时的点与集合的信息。在 DP 结束后从 pre[root][S] 出发,寻找与集合里的点相连的那些点并逐步分解集合 ,用 ans 数组来记录被使用的那些点,当集合分解完毕时搜索也就结束了。

习题

贡献者:@Zirnc@邵晨恒@kenlig@Nathan@mgt

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组