斯坦纳树

斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。平原上的三个城镇间要兴建一个公用的煤气供应站，在选址问题上，要考虑的主要问题是使由供应站到三个城镇的输送管道的总长最短。