20220116-Steiner树
Steiner树
斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。
- 最小生成树是在给定的点集和边中寻求最短网络使所有点连通。
- 最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。
1. 问题引入
- 将三个村庄用总长为极小的道路连接起来。数学表述为：在平面内给定三个点 A、B、C找出平面内第四个点P，使得和数$a+b+c$为最短，这里$a、b、c$ 分别表示从P 到A、B、C的距离。
- 【问题推广】斯坦纳树问题：给定$n$个点 ，试求连接此$n$个点$A_1,A_2,…, A_n$，总长最短的直线段连接系统，并且任意两点都可由系统中的直线段组成的折线连接起来
https://oi-wiki.org/graph/steiner-tree/